Stochastic Dynamics through Hierarchically Embedded Markov Chains

Vítor V. Vasconcelos, Fernando P. Santos, Francisco C. Santos, and Jorge M. Pacheco

Phys. Rev. Lett. 118, 058301 – Published 1 February 2017

Abstract

Studying dynamical phenomena in finite populations often involves Markov processes of significant mathematical and/or computational complexity, which rapidly becomes prohibitive with increasing population size or an increasing number of individual configuration states. Here, we develop a framework that allows us to define a hierarchy of approximations to the stationary distribution of general systems that can be described as discrete Markov processes with time invariant transition probabilities and (possibly) a large number of states. This results in an efficient method for studying social and biological communities in the presence of stochastic effects—such as mutations in evolutionary dynamics and a random exploration of choices in social systems—including situations where the dynamics encompasses the existence of stable polymorphic configurations, thus overcoming the limitations of existing methods. The present formalism is shown to be general in scope, widely applicable, and of relevance to a variety of interdisciplinary problems.

Received 27 July 2016

DOI:https://doi.org/10.1103/PhysRevLett.118.058301

Physics Subject Headings (PhySH)

Complex systems Evolutionary & population dynamics

Collective dynamics Population dynamics Social dynamics

Game theory models Markovian processes

Nonlinear DynamicsInterdisciplinary Physics

Authors & Affiliations

Vítor V. Vasconcelos^1,2,3, Fernando P. Santos^1,3, Francisco C. Santos^1,3, and Jorge M. Pacheco^2,4,3,*

¹INESC-ID and Instituto Superior Técnico, Universidade de Lisboa, 2744-016 Porto Salvo, Portugal
²Centro de Biologia Molecular e Ambiental da Universidade do Minho, 4710-057 Braga, Portugal
³ATP-group, P-2744-016 Porto Salvo, Portugal
⁴Departamento de Matemática e Aplicações da Universidade do Minho, 4710-057 Braga, Portugal

^*jmpacheco@math.uminho.pt

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 118, Iss. 5 — 3 February 2017

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Stationary distributions associated with a coexistence game ( $f = 0.7$ , $g = 0.3$ ). The gradient of selection is represented by the black curves, whereas the exact stationary distribution, computed for $μ = 10^{- 10}$ , is depicted by the solid (blue) bars. Two levels of approximation are considered: (i) zeroth order, $H 0$ or SMA (the dashed gray bars) and (ii) first order, $H 1$ (the crossed red bars). In (a), we compare the exact solution with $H 0$ (SMA). In $H 0$ , the COIs include only the configurations $i = 0$ and $i = Z$ , and the most probable transitions between the COIs—indicated by the red arrows—suggest why the full strength is concentrated at $i = Z$ . Clearly, $μ = 10^{- 10}$ in a population of size $Z = 50$ is not small enough to bring the exact result into the SMA domain of validity. In (b), the crossed red bars represent the stationary distribution yielded by $H 1$ , where $i^{*}$ was added to the COIs. The other parameters are $Z = 50$ , $β = 10$ .
Reuse & Permissions
Figure 2
Same system as Fig. 1. (a) We compare the results of $H 0$ and $H 1$ with the exact solution. (b) We add one, three, and five homogeneously distributed points to the $H 0$ COIs, assuming a flat distribution around each COI. With five equidistant points, we reproduce the full distribution, disregarding any information about the dynamics and its fixed points. The vertical line indicates the value of $μ$ employed in Fig. 1.
Reuse & Permissions
Figure 3
COIs at different levels of the hierarchical approximation. The arrows represent the most likely direction of evolution of the system (the gradient of selection, $G$ , with warm colors representing larger magnitudes), whereas the background gray shading represents the stationary distribution (darker areas correspond to states with higher probability). As mutation increases, the population explores configurations deviating gradually from the vertices. For the dynamics and parameters specified below, this trend starts (a) at $μ = 10^{- 4}$ , exploration of the phase space extending mostly along the edges (b) up to $μ = 10^{- 2}$ , to finally explore the interior of the simplex for higher values of $μ$ [ $μ = 10^{- 1}$ in (c)]. The probabilities of updates from strategies $σ_{i}$ to $σ_{j}$ are given by $T_{(σ_{i} \to σ_{j})} = [Z / (Z - 1)] x_{i} x_{j} (1 - μ) {(1 + e^{(Δ f_{(σ_{i} σ_{j})})})}^{- 1} + x_{i} (μ / d)$ , with $Δ f_{σ_{i} σ_{j}} = β_{i j x} (x_{1} - x_{1}^{*}) + β_{i j y} (x_{2} - x_{2}^{*})$ , with $x_{i}$ being the frequency of strategy $σ_{j}$ and $d$ the number of accessible strategies, given the restriction of the phase space considered. The parameters are $Z = 50$ , $β_{12 x} = 2$ , $β_{12 y} = β_{13 x} = 10$ , $β_{23 y} = - 10$ , $β_{13 y} = β_{23 x} = 0$ , $x_{1}^{*} = 2 / 10$ , and $x_{2}^{*} = 3 / 10$ .
Reuse & Permissions
Figure 4
We plot the average of the stationary distributions as a function of mutation probability for the system depicted in Fig. 3, and at different levels of the hierarchical approximation. At the $H 0$ level (SMA), accurate average values are obtained whenever $μ < 10^{- 5}$ . As mutation increases, the polymorphic configurations attract higher probabilities, requiring the inclusion of COIs along the edges of the simplex ( $H 1$ ) and in its interior ( $H 2$ )—see the text for details.
Reuse & Permissions

Physical Review Letters