Stochastic dynamics in finite populations: Difference between revisions

Revision as of 13:37, 9 March 2012

Stochastic differential equations (SDE) provide a general framework to describe the evolutionary dynamics of an arbitrary number of types in finite populations, which results in demographic noise, and to incorporate mutations. For large, but finite populations this allows to include demographic noise without requiring explicit simulations. Instead, the population size only rescales the amplitude of the noise. Moreover, this framework admits the inclusion of mutations between different types, provided that mutation rates, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} , are not too small compared to the inverse population size Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/N} . This ensures that all types are almost always represented in the population and that the occasional extinction of one type does not result in an extended absence of that type. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu N\ll1} this limits the use of SDE’s, but in this case well established alternative approximations are available based on time scale separation. We illustrate our approach by a Rock-Scissors-Paper game with mutations, where we demonstrate excellent agreement with simulation based results for sufficiently large populations. In the absence of mutations the excellent agreement extends to small population sizes.

This tutorial complements a series of research articles by Arne Traulsen, Jens Christian Claussen & Christoph Hauert

Rock-Paper-Scissors game

Comparisons between the deterministic dynamics in infinite populations, the stochastic dynamics in finite populations and individual based simulations focus on the Rock-Paper-Scissors game with a generic payoff

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix}~&\begin{matrix}\ \ R\quad & S\quad & P\quad\end{matrix} \\ \begin{matrix}R\\S\\P\end{matrix}& \begin{pmatrix}0 & \frac{s}{2} & -1 \\ -1 & 0 & 2+s \\ \frac{1+s}{3} & -1 & 0\end{pmatrix}\end{matrix} }

According to the replicator equation the game exhibits saddle node fixed points at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = 1, y = 1} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z = 1-x-y = 1} as well as an interior fixed point at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\hat{\mathbf x} = \left(\frac12,\frac13,\frac16\right)} independent of the parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} . For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s > 1} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat x} is a stable focus and an unstable focus for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s<1} . In the non-generic case Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=1} the dynamics exhibits closed orbits.

Deterministic Dynamics

Replicator dynamics

Replicator-Mutator dynamics

Stochastic Dynamics

Stochastic differential equations

Stochastic differential equations, with mutations

Individual Based Simulations

Individual based simulations

Individual based simulations, with mutations

From finite to infinite populations

In unstructured, finite populations of constant size, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} , consisting of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} distinct strategic types and with a mutation rate, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} , evolutionary changes can be described by the following class of birth-death processes: In each time step, one individual of type Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} produces a single offspring and displaces another randomly selected individual of type Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . With probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-\mu} , no mutation occurs and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} produces an offspring of the same type. But with probability $\mu$ , the offspring of an individual of type $i$ ( $i\neq j$ ) mutates into a type $j$ individual. This results in two distinct ways to increase the number of $j$ types by one at the expense of decreasing the number of $k$ types by one, hence keeping the population size constant. Biologically, keeping $N$ constant implies that the population has reached a stable ecological equilibrium and assumes that this equilibrium remains unaffected by trait frequencies. The probability for the event of replacing a type $k$ individual with a type $j$ individual is denoted by $T_{kj}$ and is a function of the state of the population $\mathbf {X} =(X_{1},X_{2},\ldots X_{d})$ , with $X_{n}$ indicating the number of individuals of type $n$ such that $\textstyle \sum _{n=1}^{d}X_{n}=N$ .

For such processes we can easily derive a Master equation:

P^{\tau +1}({\mathbf {X} })=P^{\tau }({\mathbf {X} })+\!\sum _{j,k=1}^{d}\!P^{\tau }({\mathbf {X} }_{j}^{k})T_{kj}({\mathbf {X} }_{j}^{k})-P^{\tau }({\mathbf {X} })\ T_{jk}({\mathbf {X} }))

where $P^{\tau }({\mathbf {X} })$ denotes the probability of being in state $\mathbf {X}$ at time $\tau$ and ${\mathbf {X} }_{j}^{k}=(X_{1},\ldots X_{j}-1,\ldots X_{k}+1,\ldots X_{d})$ represents a state adjacent to $\mathbf {X}$ . For large but finite $N$ the Kramers-Moyal expansion yields a convenient approximation in the form of a Fokker-Planck equation:

{\dot {\rho }}({\mathbf {x} })=-\sum _{k=1}^{d-1}{\frac {\partial }{\partial x_{k}}}\rho ({\mathbf {x} }){\mathcal {A}}_{k}({\mathbf {x} })+{\frac {1}{2}}\sum _{j,k=1}^{d-1}{\frac {\partial ^{2}}{\partial x_{k}\partial x_{j}}}\rho ({\mathbf {x} }){\mathcal {B}}_{jk}({\mathbf {x} })

where ${\mathbf {x} }={\mathbf {X} }/N$ represents the state of the population in terms of frequencies of the different strategic types and $\rho ({\mathbf {x} })$ is the probability density in state $\mathbf {x}$ . The drift vector ${\mathcal {A}}_{k}({\mathbf {x} })$ is given by

{\mathcal {A}}_{k}({\mathbf {x} })=\sum _{j=1}^{d}{\Big (}T_{jk}({\mathbf {x} })-T_{kj}({\mathbf {x} }){\Big )}=-1+\sum _{j=1}^{d}T_{jk}({\mathbf {x} })

For the second equality we have used $\textstyle \sum _{j=1}^{d}T_{kj}({\boldsymbol {x}})=1$ , which simply states that a $k$ -type individual transitions to some other type (including staying type $k$ ) with probability one. ${\mathcal {A}}_{k}({\mathbf {x} })$ is bounded in $[-1,d-1]$ because the $T_{jk}$ are probabilities.

The diffusion matrix ${\mathcal {B}}_{jk}({\mathbf {x} })$ is defined as

{\begin{aligned}{\mathcal {B}}_{jk}({\mathbf {x} })&=-{\frac {1}{N}}\left[T_{jk}({\mathbf {x} })+T_{kj}({\mathbf {x} })\right]\quad {\rm {for}}\quad j\neq k\\{\mathcal {B}}_{jj}({\mathbf {x} })&={\frac {1}{N}}\sum _{l=1,l\neq j}^{d}{\Big (}T_{jl}({\mathbf {x} })+T_{lj}({\mathbf {x} }){\Big )}\end{aligned}}

Note that the diffusion matrix is symmetric, ${\mathcal {B}}_{jk}({\mathbf {x} })={\mathcal {B}}_{kj}({\mathbf {x} })$ and vanishes as $\sim 1/N$ in the limit $N\to \infty$ .

The noise arising through demographic changes and mutations is uncorrelated in time and hence the Itô calculus can be applied to derive a Langevin equation

{\dot {x}}_{k}={\mathcal {A}}_{k}({\mathbf {x} })+\sum _{j=1}^{d-1}{{\mathcal {C}}_{kj}({\mathbf {x} })}\xi _{j}(t)

where the $\xi _{j}(t)$ represent uncorrelated Gaussian white noise with unit variance, $\langle \xi _{k}(t)\xi _{j}(t^{\prime })\rangle =\delta _{kj}\delta (t-t^{\prime })$ . The matrix ${{\mathcal {C}}({\mathbf {x} })}$ is defined by ${\mathcal {C}}^{T}({\mathbf {x} }){\mathcal {C}}({\mathbf {x} })={\mathcal {B}}({\mathbf {x} })$ and its off-diagonal elements are responsible for correlations in the noise of different strategic types. In the limit $N\to \infty$ the matrix ${\mathcal {C}}({\mathbf {x} })$ vanishes with $\sim 1/{\sqrt {N}}$ and we recover a deterministic replicator mutator equation.

References

Traulsen, A., Claussen, J. C. & Hauert, C. (2012) Stochastic differential equations for evolutionary dynamics with demographic noise and mutations. Phys. Rev. E in print.
Traulsen, A., Claussen, J. C. & Hauert, C. (2006) Coevolutionary dynamics in large, but finite populations. Phys. Rev. E 74 011901 doi: 10.1103/PhysRevE.74.011901.
Traulsen, A., Claussen, J. C. & Hauert, C. (2005) Coevolutionary Dynamics: From Finite to Infinite Populations. Phys. Rev. Lett. 95 238701 doi: 10.1103/PhysRevLett.95.238701.

@@ Line 7: / Line 7: @@
 ==Rock-Paper-Scissors game==
-[[Image:Stochastic dynamics - noise term Cxx, no mutations.png|300px|thumb|Blabla.]]
+[[Image:Stochastic dynamics - noise term Cxx, no mutations.png|300px|thumb|Value of the element <math>\mathcal C_{xx}(x,y,z)</math> of the noise matrix <math>\mathcal C(\mathbf x)</math> for <math>d = 3</math> strategies and <math>\mu = 0</math>. <math>\mathcal C_{xx}(x,y,z)</math> determines how the noise in the <math>x</math>-direction affects the <math>x</math>-coordinate. In the case of <math>\mu = 0</math>, this noise vanishes for <math>x\to0</math>. For <math>y\to0</math> and <math>z\to0</math> we recover the usual multiplicative noise from one-dimensional evolutionary processes.]]
-Payoff matrix:
+Comparisons between the deterministic dynamics in infinite populations, the stochastic dynamics in finite populations and individual based simulations focus on the [[Rock-Paper-Scissors game]] with a generic payoff
 <math>\begin{matrix}~&\begin{matrix}\ \ R\quad & S\quad & P\quad\end{matrix} \\
 \begin{matrix}R\\S\\P\end{matrix}&
@@ Line 16: / Line 18: @@
 </math>
-Fixed point:
+According to the [[replicator equation]] the game exhibits saddle node fixed points at <math>x = 1, y = 1</math>, and <math>z = 1-x-y = 1</math> as well as an interior fixed point at <math>\textstyle\hat{\mathbf x} = \left(\frac12,\frac13,\frac16\right)</math> independent of the parameter <math>s</math>. For <math>s > 1</math>, <math>\hat x</math> is a stable focus and an unstable focus for <math>s<1</math>. In the non-generic case <math>s=1</math> the dynamics exhibits closed orbits.
-<math>\hat{\mathbf x} = \left(\frac12,\frac13,\frac16\right)</math>
 {{-}}