Independent scholarship · Open accessThe monthly digest

Indexed text attachment

evolutionary-game-theory-in-higher-categories.tex

Source for Evolutionary Game Theory in Higher Categories

View paper · Download original file

Lines 1909–2008 of 3949. Source text is displayed literally.

1909\section{Fixation probabilities retain the update law}1910 1911When mutation is absent, let \(h_i(n)\) be the probability of fixation at the monomorphic state of type \(i\). Conditioning on the first update makes \(h_i\) harmonic away from the absorbing states. Its boundary values are one at fixation of \(i\) and zero at fixation of any other type. These conditions characterize it. Indeed, a harmonic function with these boundary values has constant conditional mean until absorption, and the absorption argument above gives almost sure convergence to the boundary values. Boundedness on the finite state space permits taking expectations in the limit.1912 1913Under neutral reproduction all present reproductive weights are equal, so \(c(n)=x\) in the mutation-free process. Equation~\eqref{eq:birth-death-drift} gives harmonicity of \(n_i/N\), and the boundary values give \(h_i(n)=n_i/N\). For nonneutral reproduction these fixation probabilities depend on the transition law. The drift alone can be insufficient when different updates induce different hitting distributions, and a deterministic trajectory is a different observable from the absorption probability. The next chapter studies selection by rare mutation, in which fixation between departures from recurrent states supplies the effective transition information. Chapter~\ref{ch:mean-field} compares the frequency process with its deterministic limit on a fixed time interval.1914\par1915\chapter{Rare mutation and stochastic stability}1916\label{ch:stochastic-stability}1917 1918A small mutation probability changes the meaning of a long-run prediction. The mutation-free chain can have many recurrent classes. With positive mutation the chain can leave those classes, and its stationary law can weight them differently even when mutation tends to zero. The stationary limit first takes a long-time average at positive mutation and then decreases the mutation parameter. This order is intrinsic to the prediction.1919 1920\section{A theorem for stationary weights}1921 1922Let \(E\) be a nonempty finite state set and \(P\) an irreducible transition matrix on \(E\), with rows indexed by the starting state. An in-tree rooted at \(i\) assigns one outgoing edge to each vertex other than \(i\), such that repeated traversal of the edges brings any vertex to \(i\). The root has no outgoing edge. Define1923\[1924 W_i(P)=\sum_{\tau\text{ rooted at }i}1925      \prod_{(x,y)\in\tau}P(x,y).1926\]1927The one-state case uses the weight one for the empty tree. Each weight is positive because the support of \(P\) has a path from every vertex to \(i\). Choosing at each vertex an edge decreasing the shortest such path length gives a tree of positive weight.1928 1929\begin{theorem}[Markov chain tree formula]1930\label{thm:markov-trees}1931The unique stationary distribution of \(P\) is1932\(\pi(i)=W_i(P)/\sum_j W_j(P)\).1933\end{theorem}1934 1935\begin{proof}1936It suffices to show that the weighted inflow to \(i\) from distinct states equals the weighted outflow from \(i\):1937\[1938 \sum_{j\ne i}W_j(P)P(j,i)1939       =W_i(P)\sum_{k\ne i}P(i,k).1940\]1941A term on the left adds the edge \(j\to i\) to a tree rooted at \(j\). This produces a directed graph with one outgoing edge at every vertex and a unique directed cycle, of length at least two, containing \(i\). A term on the right adds \(i\to k\) to a tree rooted at \(i\). It gives a graph of the same kind. From such a graph, deleting the edge entering \(i\) on the cycle recovers the construction on the left. Deleting the outgoing edge at \(i\) recovers the construction on the right. The products are the same because they use all edges of the corresponding graph. The diagonal terms of stationarity cancel, so this bijection proves the displayed identity. Normalize and use uniqueness of the stationary law for a finite irreducible chain.1942\end{proof}1943 1944This is the rooted-tree form of the Markov chain tree theorem \cite{leighton-rivest}. It accounts for indirect paths between states. The stationary ranking can depend on several paths taken together and therefore need not coincide with a ranking of the individual edges leaving each state.1945 1946\section{Leading powers and stable states}1947 1948Suppose \(P^\epsilon\) is irreducible for every sufficiently small \(\epsilon>0\). Assume for each off-diagonal edge that its weight is either identically zero for small \(\epsilon\), or1949\[1950 P^\epsilon(x,y)1951   =c_{xy}\epsilon^{r_{xy}}+o(\epsilon^{r_{xy}}),1952 \qquad c_{xy}>0,\quad r_{xy}\geq 0 .1953\]1954Call \(r_{xy}\) the resistance. Omit identically zero edges and set1955\[1956 \gamma_i=\min_{\tau\text{ rooted at }i}1957               \sum_{(x,y)\in\tau}r_{xy}.1958\]1959For each root define \(a_i>0\) by summing \(\prod_{(x,y)\in\tau}c_{xy}\)1960over its minimizers. Each tree product has exponent given by the sum of its edge resistances. The tree sum is finite and its coefficients at the smallest exponent are positive. Hence1961\[1962 W_i(P^\epsilon)1963    =\epsilon^{\gamma_i}(a_i+o(1)).1964\]1965Writing \(\gamma_*=\min_i\gamma_i\), the stationary mass tends to zero for \(\gamma_i>\gamma_*\) and tends to \(a_i/\sum_{\gamma_j=\gamma_*}a_j\) for \(\gamma_i=\gamma_*\). A state with positive limiting mass is called stochastically stable. Thus the minimum resistance determines the stable set, and the coefficients determine the limiting weights within it. The leading powers depend on the revision and mutation mechanism. An ordering of payoffs alone does not provide them.1966 1967This argument is a direct finite-state counterpart to resistance and stochastic potential in Young's theory of regular perturbed Markov processes \cite{young-conventions}. Mutation mechanisms with weights decaying faster than all powers may require a different asymptotic scale. Aperiodicity is needed for general convergence from arbitrary initial laws along discrete time. The stationary weights in the tree theorem are defined for every irreducible kernel.1968 1969\section{Eliminating transient excursions}1970 1971The state set of a population chain can be large. An exact reduction separates states recurrent under no mutation from transient excursion states. Suppose \(P^\epsilon\to P^0\) and write \(E=K\amalg T\), where \(K\) is the set of recurrent states of \(P^0\) and \(T\) is the set of transient states. Define successive visits to \(K\) by counting each ordinary time step spent in \(K\), including consecutive time steps there. With matrix blocks indexed by the starting and ending sets, this trace kernel is1972\begin{equation}1973 \widehat P^\epsilon1974 = P^\epsilon_{KK}1975   + P^\epsilon_{KT}(I-P^\epsilon_{TT})^{-1}P^\epsilon_{TK}.1976 \label{eq:trace-kernel-egt}1977\end{equation}1978If \(T\) is empty, only the first term is needed. The geometric series for the inverse sums incomplete excursions according to the number of steps that stay in \(T\). For each \(m\geq0\) the term with \(m\) such steps follows the block sequence1979\[1980\begin{tikzcd}[column sep=large]1981 K \arrow[r,"P^\epsilon_{KT}"{above}] &1982 T \arrow[r,"(P^\epsilon_{TT})^m"{above}] &1983 T \arrow[r,"P^\epsilon_{TK}"{above}] &1984 K .1985\end{tikzcd}1986\]1987Transience makes the series converge at \(\epsilon=0\), since the probability of staying in \(T\) decays geometrically in a finite chain. The inverse therefore exists and is continuous for sufficiently small \(\epsilon\).1988 1989The stationary equation on \(T\) is1990\(\pi_T^\epsilon=\pi_K^\epsilon P^\epsilon_{KT}1991   +\pi_T^\epsilon P^\epsilon_{TT}\).1992Solving it and substituting into the equation on \(K\) gives1993\(\pi_K^\epsilon\widehat P^\epsilon=\pi_K^\epsilon\).1994Thus the trace stationary distribution is the normalized restriction of \(\pi^\epsilon\). The trace is irreducible for positive \(\epsilon\), since an original positive-probability path between visited states decomposes into consecutive trace steps. Moreover, \(P^0_{KT}=0\), because each recurrent class is closed at zero mutation. The same stationary identity then gives \(\pi_T^\epsilon\to0\). This permits computing stochastic stability using only the trace, when its transitions satisfy the requisite asymptotics. A trace records return events in the original chain. Its stationary probabilities describe fractions of visits, and the normalization accounts for the time omitted in excursions.1995 1996The error in dropping transient mass can be estimated before computing the trace stationary law. For a nonnegative matrix \(B\), let \(\|B\|_\infty\) be its maximum row sum. The stationary equation gives1997\[1998 \pi^\epsilon(T)1999 \leq \|P^\epsilon_{KT}\|_\infty2000        \big\|(I-P^\epsilon_{TT})^{-1}\big\|_\infty .2001\]2002The second factor bounds the expected duration of an excursion from any state in \(T\), and remains bounded as \(\epsilon\to 0\) at fixed population size. For example, when the probability of leaving \(K\) in one update is uniformly \(O(\epsilon)\), the total stationary time outside \(K\) is \(O(\epsilon)\).2003 2004\section{Rare steps and fixation}2005 2006If the recurrent classes of \(P^0\) are singleton absorbing states and \(P^\epsilon=P^0+\epsilon R+o(\epsilon)\) entrywise, formula~\eqref{eq:trace-kernel-egt} gives2007\[2008 \widehat P^\epsilon=I+\epsilon