Stochastic dynamics in finite populations: Difference between revisions

Line 11:

==~~From finite to infinite populations~~==

==Rock-Paper-Scissors game==

[[Image:Stochastic dynamics - noise term Cxx, no mutations.png|300px|thumb|Blabla.]]

~~<!--~~ <math>

Payoff matrix:

\~~bordermatrix~~{

<math>\begin{matrix}~&\begin{matrix}\ \ R\quad & S\quad & P\quad\end{matrix} \\

& R & S & P \cr

\begin{matrix}R\\S\\P\end{matrix}&

R & 0 & \frac{s}{2} & -1 \cr

\begin{pmatrix}0 & \frac{s}{2} & -1 \\

~~S &~~ -1 & 0 & 2+s \cr

-1 & 0 & 2+s \\

~~P &~~ \frac{1+s}{3} & -1 & 0 \cr

\frac{1+s}{3} & -1 & 0\end{pmatrix}\end{matrix}

},

</math>

</math~~> --~~>

Fixed point:

<math>\hat{\mathbf x} = \left(\frac12,\frac13,\frac16\right)</math>

Line 61:

Line 63:

</div>

==From finite to infinite populations==

[[Image:SDE vs IBS Performance|300px|thumb|Performance comparison of individual based simulations (IBS) versus stochastic differential equations (SDE). '''a''' ratio of the CPU times <math>CPU_\text{SDE}/CPU_\text{IBS}</math> as a function of the population size, <math>N</math>, and the number of strategic types, <math>d</math>. The bold contour indicates equal performance.

For small <math>N</math> and large <math>d</math> IBS are faster (red region), but for larger <math>N</math> and smaller <math>d</math> SDE are faster (blue region).

Each contour indicates a performance difference of one order of magnitude.

'''b''' computational time with <math>d=10</math> as a function of <math>N</math> for IBD (red) and SDE (blue). As a reference for the scaling <math>N^2</math> (red) and a constant (blue) are shown. '''c''' computational time with <math>N=5000</math> as a function of <math>d</math> for IBD (red) and SDE (blue). As a reference for the scaling <math>d^{1/2}</math> (red) and <math>d^3</math> (blue) are shown. For a proper scaling argument much larger <math>d</math> are required but already <math>d=100</math> far exceeds typical evolutionary models and hence is only of limited relevance in the current context. All comparisons use a constant payoff matrix and the local update process (such that <math>{\mathcal A}_k(\mathbf x)=0</math> and <math>\gamma(\pi_j, \pi_k)=1/2</math>), a mutation rate of <math>1/N</math> and are based on at least <math>1000</math> time steps as well as at least one minute running time. CPU time is measured in milliseconds required to calculate <math>1000</math> time steps. The time increment for the SDE is <math>dt=0.01</math>.]]

In unstructured, finite populations of constant size, <math>N</math>, consisting of <math>d</math> distinct strategic types and with a mutation rate, <math>\mu</math>, evolutionary changes can be described by the following class of birth-death processes: In each time step, one individual of type <math>j</math> produces a single offspring and displaces another randomly selected individual of type <math>k</math>. With probability <math>1-\mu</math>, no mutation occurs and <math>j</math> produces an offspring of the same type. But with probability <math>\mu</math>, the offspring of an individual of type <math>i</math> (<math>i\neq j</math>) mutates into a type <math>j</math> individual. This results in two distinct ways to increase the number of <math>j</math> types by one at the expense of decreasing the number of <math>k</math> types by one, hence keeping the population size constant. Biologically, keeping <math>N</math> 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 <math>k</math> individual with a type <math>j</math> individual is denoted by <math>T_{kj}</math> and is a function of the state of the population <math>\mathbf X=(X_1, X_2, \ldots X_d)</math>, with <math>X_n</math> indicating the number of individuals of type <math>n</math> such that <math>\textstyle\sum_{n=1}^d X_n = N</math>.

For such processes we can easily derive a Master equation:

:<math>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}))</math>

where <math>P^\tau({\mathbf X})</math> denotes the probability of being in state <math>\mathbf X</math> at time <math>\tau</math> and <math>{\mathbf X}_j^k=(X_1, \ldots X_j-1, \ldots X_k+1, \ldots X_d)</math> represents a state adjacent to <math>\mathbf X</math>. For large but finite <math>N</math> the Kramers-Moyal expansion yields a convenient approximation in the form of a Fokker-Planck equation:

:<math>\dot \rho({\mathbf x}) = -\sum_{k=1}^{d-1}\frac{\partial}{\partial x_k}\rho({\mathbf x}){\mathcal A}_{k}({\mathbf x})+\frac12\sum_{j,k=1}^{d-1}\frac{\partial^2}{\partial x_k\partial x_j}\rho({\mathbf x}){\mathcal B}_{jk}({\mathbf x})</math>

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

:<math>{\mathcal A}_{k}({\mathbf x}) = \sum_{j=1}^{d} \Big(T_{j k}({\mathbf x}) - T_{k j}({\mathbf x}) \Big) = -1+\sum_{j=1}^{d} T_{j k}({\mathbf x})</math>

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

The diffusion matrix <math>{\mathcal B}_{jk}({\mathbf x})</math> is defined as

:<math>\begin{align}{\mathcal B}_{jk}({\mathbf x}) &= - \frac{1}{N} \left[ T_{j k}({\mathbf x}) + T_{k j}({\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_{j l}({\mathbf x})+T_{l j}({\mathbf x}) \Big)\end{align}

</math>

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

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

:<math>\dot x_k = {\mathcal A}_k({\mathbf x}) + \sum_{j=1}^{d-1} {{\mathcal C}_{kj}({\mathbf x})} \xi_j(t) </math>

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

Anonymous

Search

Stochastic dynamics in finite populations: Difference between revisions

Namespaces

More

Page actions

Navigation

NAVIGATION

FEATURED TUTORIALS

Wiki tools

Wiki tools

@@ Line 11: / Line 11: @@
 {{-}}
-==From finite to infinite populations==
+==Rock-Paper-Scissors game==
 [[Image:Stochastic dynamics - noise term Cxx, no mutations.png|300px|thumb|Blabla.]]
-<!-- <math>
+Payoff matrix:
-	\bordermatrix{
+<math>\begin{matrix}~&\begin{matrix}\ \ R\quad & S\quad & P\quad\end{matrix} \\
-		  & R & S & P \cr
+\begin{matrix}R\\S\\P\end{matrix}&
-		R & 0 & \frac{s}{2} & -1 \cr
+\begin{pmatrix}0 & \frac{s}{2} & -1 \\
-		S & -1 & 0 & 2+s \cr
+-1 & 0 & 2+s \\
-		P & \frac{1+s}{3} & -1 & 0 \cr
+\frac{1+s}{3} & -1 & 0\end{pmatrix}\end{matrix}
-		},
+</math>
-</math> -->
+Fixed point:
+<math>\hat{\mathbf x} = \left(\frac12,\frac13,\frac16\right)</math>
 {{-}}
@@ Line 61: / Line 63: @@
 {{-}}
 </div>
+==From finite to infinite populations==
+[[Image:SDE vs IBS Performance|300px|thumb|Performance comparison of individual based simulations (IBS) versus stochastic differential equations (SDE). '''a''' ratio of the CPU times <math>CPU_\text{SDE}/CPU_\text{IBS}</math> as a function of the population size, <math>N</math>, and the number of strategic types, <math>d</math>. The bold contour indicates equal performance.
+ For small <math>N</math> and large <math>d</math> IBS are faster (red region), but for larger <math>N</math> and smaller <math>d</math> SDE are faster (blue region).
+ Each contour indicates a performance difference of one order of magnitude.
+'''b''' computational time with <math>d=10</math> as a function of <math>N</math> for IBD (red) and SDE (blue). As a reference for the scaling <math>N^2</math> (red) and a constant (blue) are shown. '''c''' computational time with <math>N=5000</math> as a function of <math>d</math> for IBD (red) and SDE (blue). As a reference for the scaling <math>d^{1/2}</math> (red) and <math>d^3</math> (blue) are shown. For a proper scaling argument much larger <math>d</math> are required but already <math>d=100</math> far exceeds typical evolutionary models and hence is only of limited relevance in the current context. All comparisons use a constant payoff matrix and the local update process (such that <math>{\mathcal A}_k(\mathbf x)=0</math> and <math>\gamma(\pi_j, \pi_k)=1/2</math>), a mutation rate of <math>1/N</math> and are based on at least <math>1000</math> time steps as well as at least one minute running time. CPU time is measured in milliseconds required to calculate <math>1000</math> time steps. The time increment for the SDE is <math>dt=0.01</math>.]]
+In unstructured, finite populations of constant size, <math>N</math>, consisting of <math>d</math> distinct strategic types and with a mutation rate, <math>\mu</math>, evolutionary changes can be described by the following class of birth-death processes: In each time step, one individual of type <math>j</math> produces a single offspring and displaces another randomly selected individual of type <math>k</math>. With probability <math>1-\mu</math>, no mutation occurs and <math>j</math> produces an offspring of the same type. But with probability <math>\mu</math>, the offspring of an individual of type <math>i</math> (<math>i\neq j</math>) mutates into a type <math>j</math> individual. This results in two distinct ways to increase the number of <math>j</math> types by one at the expense of decreasing the number of <math>k</math> types by one, hence keeping the population size constant. Biologically, keeping <math>N</math> 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 <math>k</math> individual with a type <math>j</math> individual is denoted by <math>T_{kj}</math> and is a function of the state of the population <math>\mathbf X=(X_1, X_2, \ldots X_d)</math>, with <math>X_n</math> indicating the number of individuals of type <math>n</math> such that <math>\textstyle\sum_{n=1}^d X_n = N</math>.
+For such processes we can easily derive a Master equation:
+:<math>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}))</math>
+where <math>P^\tau({\mathbf X})</math> denotes the probability of being in state <math>\mathbf X</math> at time <math>\tau</math> and <math>{\mathbf X}_j^k=(X_1, \ldots X_j-1, \ldots X_k+1, \ldots X_d)</math> represents a state adjacent to <math>\mathbf X</math>. For large but finite <math>N</math> the Kramers-Moyal expansion yields a convenient approximation in the form of a Fokker-Planck equation:
+:<math>\dot \rho({\mathbf x})  = -\sum_{k=1}^{d-1}\frac{\partial}{\partial x_k}\rho({\mathbf x}){\mathcal A}_{k}({\mathbf x})+\frac12\sum_{j,k=1}^{d-1}\frac{\partial^2}{\partial x_k\partial x_j}\rho({\mathbf x}){\mathcal B}_{jk}({\mathbf x})</math>
+where <math>{\mathbf x} = {\mathbf X}/N</math> represents the state of the population in terms of frequencies of the different strategic types and <math>\rho({\mathbf x})</math> is the probability density in state <math>\mathbf x</math>. The drift vector <math>{\mathcal A}_{k}({\mathbf x})</math> is given by
+:<math>{\mathcal A}_{k}({\mathbf x}) = \sum_{j=1}^{d} \Big(T_{j k}({\mathbf x}) - T_{k j}({\mathbf x}) \Big) = -1+\sum_{j=1}^{d} T_{j k}({\mathbf x})</math>
+For the second equality we have used <math>\textstyle\sum_{j=1}^d T_{kj}({\boldsymbol x})=1</math>, which simply states that a <math>k</math>-type individual transitions to some other type (including staying type <math>k</math>) with probability one. <math>{\mathcal A}_{k}({\mathbf x})</math> is bounded in <math>[-1, d-1]</math> because the <math>T_{jk}</math> are probabilities.
+The diffusion matrix <math>{\mathcal B}_{jk}({\mathbf x})</math> is defined as
+:<math>\begin{align}{\mathcal B}_{jk}({\mathbf x}) &= - \frac{1}{N} \left[  T_{j k}({\mathbf x}) + T_{k j}({\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_{j l}({\mathbf x})+T_{l j}({\mathbf x}) \Big)\end{align}
+</math>
+Note that the diffusion matrix is symmetric, <math>{\mathcal B}_{jk}({\mathbf x}) = {\mathcal B}_{kj}({\mathbf x})</math> and vanishes as <math>\sim 1/N</math> in the limit <math>N\to\infty</math>.
+The noise arising through demographic changes and mutations is uncorrelated in time and hence the It&ocirc; calculus can be applied to derive a Langevin equation
+:<math>\dot x_k = {\mathcal A}_k({\mathbf x}) + \sum_{j=1}^{d-1} {{\mathcal C}_{kj}({\mathbf x})} \xi_j(t) </math>
+where the <math>\xi_j(t)</math> represent uncorrelated Gaussian white noise with unit variance, <math>\langle \xi_k(t) \xi_j(t^\prime) \rangle = \delta_{kj} \delta(t-t^\prime)</math>. The matrix <math>{{\mathcal C}({\mathbf x})}</math> is defined by <math>{\mathcal C}^T({\mathbf x}) {\mathcal C}({\mathbf x}) =  {\mathcal B}({\mathbf x})</math> and its off-diagonal elements are responsible for correlations in the noise of different strategic types. In the limit <math>N\to\infty</math> the matrix <math>{\mathcal C}({\mathbf x})</math> vanishes with <math>\sim 1/\sqrt{N}</math> and we recover a deterministic replicator mutator equation.

Anonymous

Search

Stochastic dynamics in finite populations: Difference between revisions

Navigation

Wiki tools

Page tools