Leanamics is a collection of Lean 4 + Mathlib formalizations of classical
results on opinion dynamics and related distributed processes, each paired
with a leanblueprint page
connecting the paper proof to the Lean code statement-by-statement. The
developments are sorry-free. Probability is finite: randomness lives on finite types and
expectations are finite sums (no measure theory, no PMF/ENNReal), and the concentration
bounds and martingale arguments are proved within this layer.
This page gives a short overview of each area; the blueprint of each package has the precise statements, the proofs and the links to the Lean code.
RESULTS.md lists every
formalized result with its scope, source, main Lean theorems and roadmap ID;
ROADMAP.md lists what we
would like to formalize next; and
PROVENANCE.md records
proof routes, explicit constants and authorship. Where a statement deviates from its source, the
package’s FORMALIZATION_DIFFERENCES.md lists the deviations. Many statements make “for
sufficiently large $n$” explicit, with thresholds that can be astronomically large.
The same processes under different names
The same few Markov chains are studied under different names in distributed computing, population genetics and evolutionary biology, epidemiology, chemistry, statistical physics, and the social sciences. Each entry of this dictionary is one correspondence: what the process is called in each field (or why a field has no counterpart), what kind of correspondence it is and under which conditions it holds, and what Leanamics proves about it. The conditions matter: two processes can be the same chain on the complete graph and differ on other graphs, or agree only up to a time change or in the limit of a large population.
How to read the dictionary: relations, chemistry, time and formal status
- same chain
- Same chain: The same transition kernel, on configurations or, where stated, on counts.
- CTMC
- Same continuous-time chain: The same continuous-time Markov chain, possibly after scaling time by a constant.
- jump chain
- Same jump chain: The same chain once idle steps are removed (lazy steps, or the holding times of a continuous-time chain); the processes differ by a random time change, so absorption probabilities agree but running times need not.
- coupling
- Pathwise coupling: Built on the same randomness, the processes agree path by path.
- dual
- Duality: An exact identity between probabilities of one process and of a dual process run backwards in time.
- limit
- Large-population limit: One process, or its scaled counts, converges to the other as the population size tends to infinity.
- same recursion
- Same deterministic recursion: Both are the same deterministic dynamical system.
- mean field
- Same mean-field map: The expected one-step change, or the deterministic infinite-population recursion, coincides; the stochastic processes may differ.
Relations. Two processes are the same chain when they have the same transition kernel. They have the same jump chain when they agree once idle steps are removed (a lazy step, or the holding times of a continuous-time chain): they differ by a random time change, so they have the same absorption and fixation probabilities but not the same running times. Duality and pathwise coupling are exact identities between two different processes. A limit holds only as the population size tends to infinity, and a common mean-field map says nothing about fluctuations. In Lean, four kinds are definitions about finite kernels in the shared library (dynamics/Dynamics/Relations.lean): the same chain on counts is a lumping (Dynamics.Kernel.Lumps), the same jump chain is Dynamics.Kernel.SameJumpChain (kernels with the same jump chain have the same absorption probabilities), duality is Dynamics.Kernel.Dual, and a common mean-field map is Dynamics.Kernel.MeanField.
Chemistry. A stochastic chemical reaction network (CRN) with mass-action kinetics is a continuous-time Markov chain on molecule counts in a well-mixed solution. It fires one reaction at a time, so synchronous-round dynamics, in which every individual is updated at once, have no CRN counterpart (their sequential versions may have one); and since the solution is well mixed, a dynamics on a graph has a CRN counterpart only on the complete graph $K_n$. Propensities follow Gillespie: $k\,x_A x_B$ for $A + B$ and $k\binom{x_A}{2}$ for $A + A$, with $k$ the rate constant (the volume absorbed in $k$).
Statistical physics. The column holds the interacting particle systems of probability theory and the models of sociophysics, opinion models proposed in physics journals (Galam's majority rule, the $q$-voter and Sznajd models, kinetic exchange). Interacting particle systems run in continuous time, every site acting at the times of its own Poisson clock, usually on $\mathbb Z^d$; on a finite graph the chain observed at the clock rings is the sequential chain (see Time), and simulations that count $N$ updates as one unit of time change no chain. Rules that differ on irregular graphs coincide on $\mathbb Z^d$ and on every regular graph (pull and push copying, the forms of the biased voter model), so a name from this column fixes the chain on other graphs only when the rule is stated for every graph.
Social sciences. The column holds models from sociology, social psychology, economics, marketing and the statistics of opinion pooling. Many are deterministic recursions for proportions or opinions (French and DeGroot, Granovetter, Bass), so they share with a stochastic chain only a recursion or a mean field; individual-level versions are compared where their authors define them. Cultural evolution, which models cultural transmission with the methods of population genetics, stays in the population-genetics column (rows wright-fisher and three-majority), and sociophysics in the physics column.
Time. Sequential dynamics draw one ordered pair of distinct agents per step. If instead every agent acts at the times of its own rate-1 Poisson clock, the chain observed at its event times is the sequential chain; population protocols count $n$ interactions as one unit of parallel time, which corresponds to mass-action time in a volume proportional to $n$.
Formal status. proved: the correspondence itself is a Lean theorem. partial: part of it is a Lean theorem, and the summary says which part. definitional: the library defines the process once and names it after both fields, so every result proved for it holds under both names, but no theorem compares two definitions; part of a row can be definitional in this sense (for example, neutral push is the Birth–death Moran kernel with $r = 1$). results: the library proves results about some of the columns, not the correspondence. roadmap: a target of the roadmap, not formalized yet. not formalized: neither in the library nor a target of the roadmap.
Blueprint links point to the section of a package's blueprint that contains the result; where that section has no label, they point to the label of the theorem itself. References were checked against Crossref, DataCite, arXiv or Open Library. Where a source states a correspondence only for a special case, or where the identification is an elementary computation not found in the sources, the relation says so. Some classic sources could not be read in full (Wright 1931, Moran 1958 beyond its first page, Bartlett 1949, Abbey 1952, Kingman 1982, Daley and Kendall 1965, Kurtz 1970 and 1972, Maki and Thompson 1973, DeGroot 1974, and for the physics and social-science columns Broadbent and Hammersley 1957, French 1956, Bass 1969, Clifford and Sudbury 1973, Richardson 1973, Holley and Liggett 1975, Chalupa, Leath and Reich 1979, Bramson and Griffeath 1981, and Goldenberg, Libai and Muller's Marketing Letters paper); what the dictionary says about them follows later sources that restate them, cited in the same row. One marketing paper has no identifier and was read in a copy on a university website.
Correspondence
Distributed computing
Population genetics
Epidemiology
Chemistry (CRN)
Statistical physics
Social sciences
Neutral copying
Distributed computing
Synchronous pull voter on $K_n$ with self-loops
Population genetics
Neutral Wright–Fisher model
Epidemiology
no counterpart
Chemistry (CRN)
no counterpart
Statistical physics
Voter model with parallel updates
Social sciences
no counterpart
Details, conditions and references
Relation
Same chain
The same chain: node $v$ takes the type of node $r(v)$, where $r$ is a uniformly random map $V \to V$, so the two processes have the same kernel on labelled configurations and the same binomial chain on counts. The voter model on the complete graph is "referred to as the Moran model or the Fisher-Wright model (depending on whether continuous-time asynchronous or discrete-time parallel updates are considered)" (Avena et al.). In cultural evolution the same chain is unbiased oblique transmission: "Each new individual of each new generation picks a member of the previous generation at random and copies their cultural trait" (Acerbi, Mesoudi and Smolla, who sample with replacement from the whole previous generation). [6, 7]
Conditions
- Complete graph with self-loops (every node samples among all $n$ nodes, itself included).
- Neutral (no selection).
- Without self-loops the offspring numbers are still exchangeable but not multinomial, so the chains differ, although a colour still fixes with probability equal to its initial frequency (for $n \ge 3$).
- On other graphs the synchronous voter has no documented population-genetics name; no source defining a "Wright–Fisher model on graphs" with neighbour-restricted parents was found.
Distributed computing
Synchronous pull voter on $K_n$ with self-loops [1, 2]
In every round each of the $n$ nodes copies the opinion of a node drawn uniformly from all $n$ nodes, itself included, independently of the other nodes. On a general graph each node copies a random neighbour (Hassin and Peleg's synchronous voter).
Population genetics and evolutionary biology
Neutral Wright–Fisher model [3, 4, 5]
Haploid, non-overlapping generations of constant size $N$: each individual of the next generation chooses its parent independently and uniformly at random from the current generation, so the number of copies of an allele evolves as $X_{t+1} \sim \mathrm{Bin}(N, X_t/N)$ and fixes with probability $X_0/N$.
Epidemiology
No counterpart: neutral copying is symmetric between the types, while an epidemic has a distinguished infectious state.
Chemistry (chemical reaction networks)
No counterpart: Synchronous rounds replace every individual at once, while a stochastic CRN fires one reaction at a time.
Statistical physics and interacting particle systems
Voter model with parallel updates [6]
All sites update at once, each copying the type of a uniformly random neighbour: the discrete-time parallel version of the voter model, which itself runs in continuous time (next row). On the complete graph probabilists call this version the Fisher–Wright model (relation).
Social sciences
No counterpart found in sociology or economics. Unbiased cultural transmission, the same chain on cultural traits, belongs to cultural evolution and is listed with population genetics (relation).
In Leanamics
Lean: proved The synchronous voter model on $K_n$ with self-loops (Wright–Fisher sampling, Voter.wfKernel) lumps to the Wright–Fisher chain on allele counts, defined from the binomial law alone ($X_{t+1} \sim \mathrm{Bin}(n, X_t/n)$, Voter.wfCountKernel), under the number of vertices of any colour (Voter.transition_wfKernel_lumps, a lumping Dynamics.Kernel.Lumps); on labelled configurations the two processes coincide by definition. Neutral fixation $c_a/n$ follows from Hassin and Peleg's proportionate agreement and transfers to the count chain through the lumping, and consensus within $2n\log n$ rounds follows from the duality with coalescing walks (row coalescing).
- Correspondence:
Voter.wfKernel, Voter.wfCountKernel, Voter.transition_wfKernel_lumps
- Results:
Voter.wrightFisher_fixation, Voter.wfCountKernel_fixation, Voter.consensus_probability_of_selfLoop, Voter.voter_consensus_whp
- Blueprint: voter, sec:hassin-peleg · voter, thm:wright-fisher · voter, thm:wf-counts
- Roadmap: VOT-1, VOT-2, VOT-3
References
- Y. Hassin, D. Peleg (2001). Distributed probabilistic polling and applications to proportionate agreement. Information and Computation 171(2):248–268. doi:10.1006/inco.2001.3088
- L. Becchetti, A. Clementi, E. Natale (2020). Consensus dynamics: an overview. ACM SIGACT News 51(1):58–104. doi:10.1145/3388392.3388403
- S. Wright (1931). Evolution in Mendelian populations. Genetics 16(2):97–159. doi:10.1093/genetics/16.2.97
- A. Etheridge (2011). Some Mathematical Models from Population Genetics. Lecture Notes in Mathematics 2012, Springer. doi:10.1007/978-3-642-16632-7
- R. Durrett (2008). Probability Models for DNA Sequence Evolution (2nd ed.). Springer. doi:10.1007/978-0-387-78168-6
- L. Avena, R. Baldasso, R. S. Hazra, F. den Hollander, M. Quattropani (2024). Discordant edges for the voter model on regular random graphs. ALEA Latin American Journal of Probability and Mathematical Statistics 21:431ff. doi:10.30757/ALEA.v21-18
- A. Acerbi, A. Mesoudi, M. Smolla (2022). Individual-Based Models of Cultural Evolution: A Step-by-Step Guide Using R. Routledge. doi:10.4324/9781003282068
Distributed computing
Sequential pull voter (the voter model in discrete time)
Population genetics
Neutral Moran process with death–Birth (dB) updating; on $K_n$ with self-loops, Moran's model
Epidemiology
no counterpart
Chemistry (CRN)
On $K_n$: $X + Y \to 2X$, $X + Y \to 2Y$ with a common rate constant
Statistical physics
Voter model
Social sciences
On $K_n$: Kirman's ant (recruitment) model with $\varepsilon = \delta = 0$
Details, conditions and references
Relation
Same chain
Same jump chain
Same continuous-time chain
The same chain on every graph: the copier is the individual that dies and the copied neighbour is the parent. A neutral mutant set $S$ fixes with probability $\sum_{v\in S}\deg v/2m$, its reproductive value under death–Birth. On $K_n$ without self-loops the count moves up and down with the same probability $xy/(n(n-1))$, so its jump chain is that of the network (each reaction with probability $1/2$), and the continuous-time voter model in which every node copies at rate 1 is the network's chain with rate constant $1/(n-1)$; Moran's model (with self-loops) has the same jump chain. That continuous-time process is the voter model of interacting particle systems (physics column): on every graph, observed at the rings of its $n$ clocks, it is the sequential pull voter. [12, 13, 14, 15, 9, 7]
Conditions
- Neutral; uniform choice among the neighbours (with edge weights, the same weights on both sides).
- The CRN counterpart exists only on $K_n$.
- Kirman's model is the same chain (on counts) only when $\varepsilon = \delta = 0$; with $0 < \delta < 1$ and $\varepsilon = 0$ it is a lazy version with the same jump chain. With $\varepsilon > 0$, the case Kirman studies, spontaneous switching prevents absorption and the object of interest is the stationary distribution, which this row does not cover.
- On regular graphs, $K_n$ in particular, this row coincides with the next one: neutral push and pull are then the same chain.
- With selection the names diverge: the "biased voter model" of Antal, Redner and Sood puts selection on the death step (their remark that this is equivalent to random death and fitness-proportional replacement needs a minor correction), so it is death–Birth only in the neutral case, and "biased voter" denotes different chains in different communities.
Distributed computing
Sequential pull voter (the voter model in discrete time) [1]
"In each round one node is selected uniformly at random and it adopts the color of a neighbour sampled uniformly at random" (Becchetti, Clementi and Natale, Definition 3).
Population genetics and evolutionary biology
Neutral Moran process with death–Birth (dB) updating; on $K_n$ with self-loops, Moran's model [2, 3, 4, 5]
A uniformly random individual dies and its neighbours compete for the vacancy proportionally to fitness, so in the neutral case the parent is a uniformly random neighbour. Moran's model draws the reproducing and the dying individual independently and uniformly from the whole population, so the reproducer may be the one that dies (the complete graph with self-loops).
Epidemiology
No counterpart (neutral copying).
Chemistry (chemical reaction networks)
On $K_n$: $X + Y \to 2X$, $X + Y \to 2Y$ with a common rate constant [6]
The two copying reactions in a well-mixed solution, an instance of the correspondence between population protocols and bimolecular networks (row population-protocols).
Statistical physics and interacting particle systems
Voter model [7, 8, 9, 10]
The interacting particle system introduced independently by Clifford and Sudbury and by Holley and Liggett on $\mathbb Z^d$, and defined in the same way on any graph: "with rate 1, the organism living at a given site dies, and is replaced by a descendant chosen with equal probability from its neighbors"; in the reading that gave the model its name, a voter "asks a randomly chosen neighbor, and copies his/her opinion" (Swart).
Social sciences
On $K_n$: Kirman's ant (recruitment) model with $\varepsilon = \delta = 0$ [11]
In economics, $N$ ants (or traders) feed at a black or a white source: "Two ants meet at random ... The first is converted to the second's color with probability $(1 - \delta)$", and with probability $\varepsilon$ the first "will change his own color independently before meeting anyone"; the count of ants at the black source goes up with probability $(1 - k/N)(\varepsilon + (1-\delta)\,k/(N-1))$. Kirman names the special case $\varepsilon = \delta = 0$, in which "the first person always moves with certainty to the second's group", a martingale absorbed in $N$ with probability $k_0/N$.
In Leanamics
Lean: partial The pull kernel is defined as death–Birth (Moran.pullKernel), and a mutant set $S$ fixes with probability $\sum_{v\in S}\deg v/2m$ on every connected graph, exactly (Antal, Redner and Sood's degree laws with selection are mean-field approximations). On $K_n$ the library's kernel has no self-loops (a simple graph), and its number of mutants is the neutral Moran chain on counts that moves up and down with probability $xy/(n(n-1))$ (Moran.pullKernel_top_lumps), whose jump chain moves up or down with probability $1/2$ (Moran.pullCountKernel_jump); Moran's model, with self-loops and probability $xy/n^2$, has the same jump chain (Moran.moranCountKernel_sameJumpChain), and for $n \ge 2$ both fix with probability $x/n$. On every regular graph the pull kernel is neutral push (Moran.moranKernel_one_eq_pullKernel, next row). The network is an instance of CRN-1 (Crn.jumpKernel_eq_ppKernel), not stated for it, and the continuous-time chains are not formalized.
- Correspondence:
Moran.pullKernel, Moran.pullKernel_top_lumps, Moran.pullCountKernel_jump, Moran.moranCountKernel_sameJumpChain, Moran.moranKernel_one_eq_pullKernel, Crn.jumpKernel_eq_ppKernel
- Results:
Moran.pull_fixation, Moran.pull_value_invariant, Moran.pullCountKernel_fixation, Moran.moranCountKernel_fixation
- Blueprint: moran, sec:ars-push-pull · moran, sec:moran-counts · moran, sec:moran-selection-counts · crn, thm:crn1
- Roadmap: VOT-4, CRN-1
References
- L. Becchetti, A. Clementi, E. Natale (2020). Consensus dynamics: an overview. ACM SIGACT News 51(1):58–104. doi:10.1145/3388392.3388403
- H. Ohtsuki, C. Hauert, E. Lieberman, M. A. Nowak (2006). A simple rule for the evolution of cooperation on graphs and social networks. Nature 441:502–505. doi:10.1038/nature04605
- L. Hindersin, A. Traulsen (2015). Most undirected random graphs are amplifiers of selection for Birth-death dynamics, but suppressors of selection for death-Birth dynamics. PLOS Computational Biology 11(11):e1004437. doi:10.1371/journal.pcbi.1004437
- P. A. P. Moran (1958). Random processes in genetics. Mathematical Proceedings of the Cambridge Philosophical Society 54:60–71. doi:10.1017/S0305004100033193
- P. A. P. Moran (1959). The survival of a mutant gene under selection. Journal of the Australian Mathematical Society 1(1):121–126. doi:10.1017/S1446788700025155
- D. Doty (2014). Timing in chemical reaction networks. SODA 2014, 772–784. doi:10.1137/1.9781611973402.57 arXiv:1304.0872
- P. Clifford, A. Sudbury (1973). A model for spatial conflict. Biometrika 60(3):581–588. doi:10.1093/biomet/60.3.581
- R. A. Holley, T. M. Liggett (1975). Ergodic theorems for weakly interacting infinite systems and the voter model. Annals of Probability 3(4):643–663. doi:10.1214/aop/1176996306
- J. M. Swart (2017). A Course in Interacting Particle Systems. arXiv preprint, lecture notes (version 5, 2025). arXiv:1703.10007
- R. Durrett, S. Moseley (2015). Spatial Moran models I. Stochastic tunneling in the neutral case. Annals of Applied Probability 25(1):104–115. doi:10.1214/13-AAP989
- A. Kirman (1993). Ants, rationality, and recruitment. The Quarterly Journal of Economics 108(1):137–156. doi:10.2307/2118498
- V. Sood, T. Antal, S. Redner (2008). Voter models on heterogeneous networks. Physical Review E 77:041121. doi:10.1103/PhysRevE.77.041121
- T. Antal, S. Redner, V. Sood (2006). Evolutionary dynamics on degree-heterogeneous graphs. Physical Review Letters 96:188104. doi:10.1103/PhysRevLett.96.188104
- W. Maciejewski (2014). Reproductive value in graph-structured populations. Journal of Theoretical Biology 340:285–293. doi:10.1016/j.jtbi.2013.09.032
- D. Aldous (2013). Interacting particle systems as stochastic social dynamics. Bernoulli 19(4):1122–1149. doi:10.3150/12-BEJSP04
Distributed computing
Sequential push voter
Population genetics
Neutral Moran process with Birth–death (Bd) updating
Epidemiology
no counterpart
Chemistry (CRN)
On $K_n$: the network of the previous row
Statistical physics
Invasion process (reverse voter model)
Social sciences
no counterpart
Details, conditions and references
Relation
Same chain
Same jump chain
The same chain on every graph (pushing node = reproducing individual, target = replaced neighbour), called the invasion process in statistical physics (physics column). A neutral mutant set $S$ fixes with probability $\sum_{v\in S}1/\deg v \,\big/ \sum_{v}1/\deg v$, its reproductive value under Birth–death, against $\sum_{v\in S}\deg v/2m$ for pull: the push/pull asymmetry of distributed computing is the Birth–death/death–Birth asymmetry of evolutionary graph theory. The two agree on regular graphs; with selection, most random graphs amplify selection under Birth–death and suppress it under death–Birth (Hindersin and Traulsen). [4, 6, 2, 5]
Conditions
- Neutral; uniform choice of the target among the neighbours.
- The CRN counterpart exists only on $K_n$, where push and pull coincide.
Distributed computing
Sequential push voter
At each step a uniformly random node pushes its opinion to a uniformly random neighbour.
Population genetics and evolutionary biology
Neutral Moran process with Birth–death (Bd) updating [1, 2, 3]
An individual chosen proportionally to fitness (uniformly in the neutral case) reproduces, and its offspring replaces a uniformly random neighbour; called the invasion process in statistical physics.
Epidemiology
No counterpart (neutral copying).
Chemistry (chemical reaction networks)
On $K_n$: the network of the previous row
On $K_n$, neutral push and pull have the same chain.
Statistical physics and interacting particle systems
Invasion process (reverse voter model) [4, 5]
"(i) pick a random node (an invader); (ii) the invader exports its state to a random neighbor", time advancing by $1/N$ per update (Sood, Antal and Redner); Castellano introduced it as the reverse voter model and notes that it coincides with the voter model when all degrees are equal.
Social sciences
No counterpart found.
In Leanamics
Lean: partial Neutral push is defined as the Birth–death Moran kernel with $r = 1$ (Moran.moranKernel), so the same chain holds on every graph by definition; its fixation probability is proved exactly on every connected graph, and $k/n$ on regular graphs. On every regular graph neutral push and pull are the same kernel (Moran.moranKernel_one_eq_pullKernel), and on $K_n$ the number of mutants under push is the neutral chain on counts without self-loops of the previous row (Moran.moranKernel_top_one_lumps), whose jump chain is that of the network. The network is an instance of CRN-1, not stated for it.
References
- E. Lieberman, C. Hauert, M. A. Nowak (2005). Evolutionary dynamics on graphs. Nature 433:312–316. doi:10.1038/nature03204
- L. Hindersin, A. Traulsen (2015). Most undirected random graphs are amplifiers of selection for Birth-death dynamics, but suppressors of selection for death-Birth dynamics. PLOS Computational Biology 11(11):e1004437. doi:10.1371/journal.pcbi.1004437
- T. Antal, S. Redner, V. Sood (2006). Evolutionary dynamics on degree-heterogeneous graphs. Physical Review Letters 96:188104. doi:10.1103/PhysRevLett.96.188104
- V. Sood, T. Antal, S. Redner (2008). Voter models on heterogeneous networks. Physical Review E 77:041121. doi:10.1103/PhysRevE.77.041121
- C. Castellano (2005). Effect of network topology on the ordering dynamics of voter models. Modeling Cooperative Behavior in the Social Sciences, AIP Conference Proceedings 779, 114–120. doi:10.1063/1.2008600 arXiv:cond-mat/0504522
- W. Maciejewski (2014). Reproductive value in graph-structured populations. Journal of Theoretical Biology 340:285–293. doi:10.1016/j.jtbi.2013.09.032
Selection
Distributed computing
Push voter with fitness-biased senders
Population genetics
Moran process with Birth–death updating and mutant fitness $r$
Epidemiology
no counterpart
Chemistry (CRN)
On $K_n$: $M + W \to 2M$ (rate $r$), $M + W \to 2W$ (rate $1$)
Statistical physics
Biased voter (Williams–Bjerknes) model
Social sciences
no counterpart
Details, conditions and references
Relation
Same chain
Same jump chain
Same continuous-time chain
The same chain on every graph. On $K_n$ every mixed state moves up with probability $r/(1+r)$ among its moves, as the jump chain of the network, so the fixation probabilities agree; the continuous-time process in which each individual reproduces at rate equal to its fitness is the network's chain with rate constants $r/(n-1)$ and $1/(n-1)$ (on $\mathbb Z^d$, and on every regular graph, it is the biased voter, or Williams–Bjerknes, model of probability theory; on irregular graphs that model's per-edge rates give a different chain). [5, 2, 7, 9, 10, 8]
Conditions
- Parent chosen proportionally to fitness among all individuals, target uniform among its neighbours.
- The CRN counterpart exists only on $K_n$.
- Death–Birth with selection on $K_n$ without self-loops has a state-dependent up/down ratio, so no network of two copying reactions with constant rates has its jump chain; with self-loops (Moran's independent draws) it coincides with Birth–death.
- The isothermal theorem's informal "only if" needs a minor correction (Galanis et al., Proposition 12: a non-isothermal weighted graph on three vertices on which a uniformly placed mutant fixes with the Moran probability); its formal statement in Lieberman, Hauert and Nowak's supplement is correct.
- "Biased voter" names three chains. (i) In probability (Bramson and Griffeath; Durrett and Moseley; Swart), defined on $\mathbb Z^d$: births at rate equal to fitness onto a uniform neighbour, or equivalently there rates per ordered pair of neighbours or proportional to neighbour frequencies. Read on any graph, the birth form is the continuous-time version of this row (observed at its births it is this row's chain); the other two forms have the jump chain of this row on regular graphs, and on irregular graphs they differ from each other and from this row. (ii) Antal, Redner and Sood: death with probability inversely proportional to fitness, the parent a uniform neighbour; on regular graphs it has the jump chain of this row, so a uniformly placed mutant fixes with the Moran probability, but not on irregular graphs. (iii) Durocher et al.: death–Birth with the parent drawn proportionally to fitness among the neighbours, which they attribute to Antal, Redner and Sood; a different chain, also on regular graphs and on $K_n$ without self-loops (third condition), which coincides with this row on $K_n$ with self-loops and, on $\mathbb Z$, up to a time change while the mutants form an interval of at least two sites (Durrett and Moseley, who compare this death-driven rule with the biased voter model). The comparisons on finite graphs are our computation.
Distributed computing
Push voter with fitness-biased senders [1, 2]
The sender is drawn with probability proportional to its fitness ($r$ for mutants, $1$ for residents) and pushes its type to a uniformly random neighbour. There is no distributed computing name; algorithmic work studies it under its biological name.
Population genetics and evolutionary biology
Moran process with Birth–death updating and mutant fitness $r$ [3, 4, 5, 2]
"At each time step an individual is chosen for reproduction with a probability proportional to its fitness"; its offspring replaces a neighbour (Lieberman, Hauert and Nowak). On regular graphs, as on $K_n$, $k$ mutants fix with probability $(1 - r^{-k})/(1 - r^{-n})$ from every initial set (the "if" direction of the isothermal theorem). Moran's 1958 model is neutral; on the complete graph with self-loops, with selection by fecundity, Moran (1959) found this fixation probability as a gambler's ruin.
Epidemiology
No counterpart.
Chemistry (chemical reaction networks)
On $K_n$: $M + W \to 2M$ (rate $r$), $M + W \to 2W$ (rate $1$)
Mutant and wild-type molecules converting each other, with rate constants in ratio $r$.
Statistical physics and interacting particle systems
Biased voter (Williams–Bjerknes) model [6, 7, 8]
On $\mathbb Z^d$, "Cells give birth at a rate equal to their fitness, and the offspring replaces a nearest neighbor chosen at random" (Durrett and Moseley, after Bramson and Griffeath); equivalently, with bias $s = r - 1$, a site switches $0 \to 1$ at rate $(1+s) f_1$ and $1 \to 0$ at rate $f_0$, where $f_i$ is the fraction of its neighbours of type $i$ (Swart). The name also denotes other chains (relation).
Social sciences
No counterpart found.
In Leanamics
Lean: partial The Birth–death kernel (Moran.moranKernel) is the push voter with fitness-biased senders, by definition. On $K_n$ the library's kernel has no self-loops (the offspring replaces another vertex), and its number of mutants is the chain on counts that moves from $k$ up with probability $rk(n-k)/((rk+n-k)(n-1))$ and down with probability $k(n-k)/((rk+n-k)(n-1))$ (Moran.moranKernel_top_lumps). Moran's chain on counts, in which the dying individual is drawn among all $n$ (self-loops), has the same jump chain (Moran.moranSelectionCountKernel_sameJumpChain): from every mixed state it moves up with probability $r/(1+r)$ (Moran.birthDeathCountKernel_jump, Moran.moranSelectionCountKernel_jump), and for $r \ne 1$ both chains fix from $k$ mutants with probability $(1 - r^{-k})/(1 - r^{-n})$, transferred from Moran's formula on $K_n$. The library also proves the "if" direction of the isothermal theorem and exact fixation on the star. Networks with unequal rate constants are not formalized (CRN-1 assumes a common rate constant), nor are the continuous-time chains.
- Correspondence:
Moran.moranKernel, Moran.moranKernel_top_lumps, Moran.moranSelectionCountKernel_sameJumpChain, Moran.birthDeathCountKernel_jump, Moran.moranSelectionCountKernel_jump
- Results:
Moran.isothermal, Moran.moran_formula, Moran.birthDeathCountKernel_fixation, Moran.moranSelectionCountKernel_fixation, Moran.star_fixation, Moran.star_amplifier, Moran.star_fixation_uniform_tendsto
- Blueprint: moran, sec:lhn-isothermal · moran, sec:moran-selection-counts · moran, sec:broom-rychtar
- Roadmap: MOR-1, MOR-2, MOR-3
References
- J. Díaz, L. A. Goldberg, G. B. Mertzios, D. Richerby, M. Serna, P. G. Spirakis (2014). Approximating fixation probabilities in the generalized Moran process. Algorithmica 69(1):78–91. doi:10.1007/s00453-012-9722-7
- A. Galanis, A. Göbel, L. A. Goldberg, J. Lapinskas, D. Richerby (2017). Amplifiers for the Moran process. Journal of the ACM 64(1). doi:10.1145/3019609
- P. A. P. Moran (1959). The survival of a mutant gene under selection. Journal of the Australian Mathematical Society 1(1):121–126. doi:10.1017/S1446788700025155
- E. Lieberman, C. Hauert, M. A. Nowak (2005). Evolutionary dynamics on graphs. Nature 433:312–316. doi:10.1038/nature03204
- L. Hindersin, A. Traulsen (2015). Most undirected random graphs are amplifiers of selection for Birth-death dynamics, but suppressors of selection for death-Birth dynamics. PLOS Computational Biology 11(11):e1004437. doi:10.1371/journal.pcbi.1004437
- M. Bramson, D. Griffeath (1981). On the Williams-Bjerknes tumour growth model I. Annals of Probability 9(2):173–185. doi:10.1214/aop/1176994459
- R. Durrett, S. Moseley (2015). Spatial Moran models I. Stochastic tunneling in the neutral case. Annals of Applied Probability 25(1):104–115. doi:10.1214/13-AAP989
- J. M. Swart (2017). A Course in Interacting Particle Systems. arXiv preprint, lecture notes (version 5, 2025). arXiv:1703.10007
- T. Antal, S. Redner, V. Sood (2006). Evolutionary dynamics on degree-heterogeneous graphs. Physical Review Letters 96:188104. doi:10.1103/PhysRevLett.96.188104
- L. Durocher, P. Karras, A. Pavlogiannis, J. Tkadlec (2022). Invasion dynamics in the biased voter process. IJCAI 2022, 265–271. doi:10.24963/ijcai.2022/38 arXiv:2201.08207
Duality and genealogy
Distributed computing
Duality of the voter model with coalescing random walks
Population genetics
Genealogy of a sample; Kingman's coalescent
Epidemiology
no counterpart
Chemistry (CRN)
Constant-kernel coagulation $A_i + A_j \to A_{i+j}$ (Marcus–Lushnikov)
Statistical physics
Coalescing random walks, dual of the voter model
Social sciences
no counterpart
Details, conditions and references
Relation
Duality
Large-population limit
Same continuous-time chain
The duality is exact and pathwise, on every graph and for every sampling kernel, in discrete and in continuous time; in continuous time it is the voter-model duality of interacting particle systems (physics column). The Wright–Fisher genealogy is exactly the coalescing walks on $K_N$ with self-loops (two lineages meet in a generation with probability $1/N$), and Kingman's coalescent is its large-population limit, with multiple and simultaneous mergers vanishing; for coalescing walks on $K_n$ in continuous time, and for the continuous-time Moran model, the number of lineages jumps $k \to k-1$ at a rate proportional to $\binom{k}{2}$, Kingman's coalescent up to a constant time change. The reading of the constant-kernel coalescent as the reaction $2A \to A$ is ours. [11, 6, 7, 8, 10]
Conditions
- Neutral copying; the duality needs no assumption on the graph or the kernel.
- Kingman's coalescent is exact only in continuous time (coalescing walks on $K_n$, or the Moran model), and a limit for Wright–Fisher.
Distributed computing
Duality of the voter model with coalescing random walks [1, 2, 3]
For every sampling kernel, the synchronous voter after rounds $r_1, \dots, r_T$ is the initial configuration read through $r_1 \circ \cdots \circ r_T$, whose point images are coalescing random walks run backwards in time; from $n$ distinct opinions, consensus time and coalescence time have the same law.
Population genetics and evolutionary biology
Genealogy of a sample; Kingman's coalescent [4, 5, 6, 7]
The ancestral lineages of a Wright–Fisher sample are coalescing random walks on $K_N$ with self-loops (each lineage picks a uniform parent). As $N \to \infty$, with time in units of $N$ generations, they converge to Kingman's coalescent, in which every pair of lineages merges at rate 1; the genealogy of the continuous-time Moran model is exactly a time-changed Kingman coalescent for every $N$.
Epidemiology
No counterpart found.
Chemistry (chemical reaction networks)
Constant-kernel coagulation $A_i + A_j \to A_{i+j}$ (Marcus–Lushnikov) [8, 9]
Clusters merge pairwise at a rate independent of their sizes. Kingman's coalescent is the stochastic coalescent with constant kernel, the Marcus–Lushnikov process up to a rescaling of time (Aldous); its number of clusters is the mass-action chain of $2A \to A$ with propensity $k\binom{a}{2}$.
Statistical physics and interacting particle systems
Coalescing random walks, dual of the voter model [10]
"The voter model $X$ is pathwise dual, with respect to the additive duality function ..., to a collection $Y$ of coalescing random walks", particles that jump at rate 1 to a uniform neighbour and merge when they meet; "duality is really the key to understanding the voter model", which on $\mathbb Z^d$ clusters for $d \le 2$ because such walks meet (Swart, Proposition 6.25).
Social sciences
No counterpart found.
In Leanamics
Lean: partial The pathwise duality for every sampling kernel (the configuration after $T$ rounds is the initial one composed with the backward map), its two-token form, and the duality of kernels (Dynamics.Kernel.Dual) between the voter model and coalescing walks on sets of vertices, $A \mapsto r(A)$, with the additive duality function of the physics column, $1\{\text{some vertex of } A \text{ has opinion } 1\}$, for every sampling kernel and at every time (Voter.transition_dual, Voter.transition_event_someTrue). On $K_n$ with self-loops, the exact probability $(1 - 1/n)^T$ that two backward walks have not met, i.e. that two Wright–Fisher lineages have not coalesced after $T$ generations. Kingman's coalescent and the coagulation reading are not formalized.
- Correspondence:
Voter.runRounds_eq_comp, Voter.disagreement_runRounds_eq_zero, Voter.coalescingKernel, Voter.transition_dual, Voter.transition_event_someTrue, Voter.iterate_transition_eq_leftRounds, Voter.iterate_disagreement_le_pairWalk, ThreeMajority.voter_dual
- Results:
Voter.expList_backward_ne, Voter.voter_consensus_whp, Voter.lazy_voter_consensus_whp, Voter.plain_voter_consensus_whp
- Blueprint: voter, lem:duality · voter, thm:coalescing-dual · voter, sec:kms-meeting-time · plurality, sec:bcekmn-any-start
- Roadmap: VOT-3, VOT-6, MAJ-6
References
- Y. Hassin, D. Peleg (2001). Distributed probabilistic polling and applications to proportionate agreement. Information and Computation 171(2):248–268. doi:10.1006/inco.2001.3088
- C. Cooper, R. Elsässer, H. Ono, T. Radzik (2013). Coalescing random walks and voting on connected graphs. SIAM Journal on Discrete Mathematics 27(4):1748–1758. doi:10.1137/120900368
- L. Becchetti, A. Clementi, E. Natale (2020). Consensus dynamics: an overview. ACM SIGACT News 51(1):58–104. doi:10.1145/3388392.3388403
- J. F. C. Kingman (1982). The coalescent. Stochastic Processes and their Applications 13(3):235–248. doi:10.1016/0304-4149(82)90011-4
- J. F. C. Kingman (1982). On the genealogy of large populations. Journal of Applied Probability 19(A):27–43. doi:10.2307/3213548
- A. Etheridge (2011). Some Mathematical Models from Population Genetics. Lecture Notes in Mathematics 2012, Springer. doi:10.1007/978-3-642-16632-7
- R. Durrett (2008). Probability Models for DNA Sequence Evolution (2nd ed.). Springer. doi:10.1007/978-0-387-78168-6
- D. J. Aldous (1999). Deterministic and stochastic models for coalescence (aggregation and coagulation): a review of the mean-field theory for probabilists. Bernoulli 5(1):3–48. doi:10.2307/3318611
- A. A. Lushnikov (1978). Coagulation in finite systems. Journal of Colloid and Interface Science 65(2):276–285. doi:10.1016/0021-9797(78)90158-3
- J. M. Swart (2017). A Course in Interacting Particle Systems. arXiv preprint, lecture notes (version 5, 2025). arXiv:1703.10007
- D. Aldous (2013). Interacting particle systems as stochastic social dynamics. Bernoulli 19(4):1122–1149. doi:10.3150/12-BEJSP04
Averaging
Distributed computing
Averaging dynamics
Population genetics
Migration between demes (without selection and drift)
Epidemiology
no counterpart
Chemistry (CRN)
no counterpart
Statistical physics
Averaging process
Social sciences
French–DeGroot model of opinion formation; Deffuant's pairwise model
Details, conditions and references
Relation
Same deterministic recursion
Same continuous-time chain
Same jump chain
The same linear recursion when $M = P$, i.e. when every deme draws its individuals in equal proportions from the neighbouring demes; on a connected non-bipartite graph both converge to the average weighted by the stationary distribution, $\sum_v \deg(v)\, x_0(v)/2m$. In population genetics the recursion is the deterministic (infinitely large demes) part of migration; the same recursion is DeGroot's model of consensus in the social sciences, and the expected configuration of the synchronous voter model follows it too. DeGroot's model with $W = P$ is exactly the averaging dynamics, and French's model is the averaging dynamics of the graph with a self-loop added at every node (social column). The random sequential version is the averaging process of interacting particle systems (physics column): Boyd et al.'s asynchronous gossip, in which a node ticks at rate 1, contacts $j$ with probability $P_{ij}$, and "both nodes set their values equal to the average of their current values", is the averaging process with $\nu_{ij} = P_{ij} + P_{ji}$, and Aldous remarks that "the only place I have seen the basic process itself is in the 'gossip algorithms' literature". Deffuant et al.'s model with $\mu = 1/2$ and $d$ above the range of the opinions averages a uniformly random pair at every step: the averaging process on $K_n$, with equal rates, observed at its meetings. [3, 6, 7, 5, 2, 4, 8]
Conditions
- Deterministic recursions; no drift (infinitely large demes) and no selection.
- The identification compares the two equations; no source stating it was found.
- The averaging process, asynchronous gossip and Deffuant et al.'s model are random sequential processes; their expected configurations solve a linear differential equation (or, step by step, a different recursion), not $x \mapsto Px$.
- The identifications with French's model, asynchronous gossip and Deffuant et al.'s model compare the definitions (our computation).
Distributed computing
Averaging dynamics [1, 2]
Synchronous: every node replaces its value by the average of its neighbours' values, $x(t+1) = P x(t)$ with $P = D^{-1}A$. The random sequential version is gossip averaging (a random edge averages its endpoints).
Population genetics and evolutionary biology
Migration between demes (without selection and drift) [3]
The allele frequencies of the demes follow $p' = M p$, where $m_{\alpha\beta}$ is the probability that an individual of deme $\alpha$ immigrated from deme $\beta$ (the backward migration matrix, row stochastic).
Epidemiology
No counterpart found.
Chemistry (chemical reaction networks)
No counterpart found.
Statistical physics and interacting particle systems
Averaging process [4]
"Initially each agent has some (real-valued) amount of money. Whenever two agents meet, they divide their money equally", every pair $\{i, j\}$ meeting at the times of a rate-$\nu_{ij}$ Poisson process; the expected configuration solves $\dot x = \frac12 N x$, with $N$ the generator of the random walk with rates $\nu$ (Aldous, Proposition 4.1).
Social sciences
French–DeGroot model of opinion formation; Deffuant's pairwise model [5, 6, 7, 8]
Opinions follow $x(k+1) = W x(k)$ with $W$ a stochastic matrix of influence weights (Proskurnikov and Tempo). In French's model every agent has a self-loop and "uniformly distributes influence between itself and the other nodes connected to it"; DeGroot's iterative opinion pooling allows any stochastic $W$ and vector opinions (subjective probability distributions). In the model of Deffuant et al., "any two randomly chosen agents meet" and, if their opinions differ by less than a threshold $d$, each moves towards the other by a fraction $\mu \le 1/2$ of the difference.
In Leanamics
Lean: results Convergence to the degree-weighted average on connected non-bipartite graphs, its spectral rate, and the expected step of sequential averaging; migration is not defined in the library.
References
- L. Becchetti, A. Clementi, E. Natale (2020). Consensus dynamics: an overview. ACM SIGACT News 51(1):58–104. doi:10.1145/3388392.3388403
- S. Boyd, A. Ghosh, B. Prabhakar, D. Shah (2006). Randomized gossip algorithms. IEEE Transactions on Information Theory 52(6):2508–2530. doi:10.1109/TIT.2006.874516
- R. Bürger (2014). A survey of migration-selection models in population genetics. Discrete and Continuous Dynamical Systems B 19(4):883–959. doi:10.3934/dcdsb.2014.19.883
- D. Aldous (2013). Interacting particle systems as stochastic social dynamics. Bernoulli 19(4):1122–1149. doi:10.3150/12-BEJSP04
- J. R. P. French Jr. (1956). A formal theory of social power. Psychological Review 63(3):181–194. doi:10.1037/h0046123
- M. H. DeGroot (1974). Reaching a consensus. Journal of the American Statistical Association 69(345):118–121. doi:10.1080/01621459.1974.10480137
- A. V. Proskurnikov, R. Tempo (2017). A tutorial on modeling and analysis of dynamic social networks. Part I. Annual Reviews in Control 43:65–79. doi:10.1016/j.arcontrol.2017.03.002
- G. Deffuant, D. Neau, F. Amblard, G. Weisbuch (2000). Mixing beliefs among interacting agents. Advances in Complex Systems 3(1–4):87–98. doi:10.1142/S0219525900000078
Majority-type dynamics
Distributed computing
3-Majority dynamics
Population genetics
Conformist transmission with three models (cultural evolution)
Epidemiology
no counterpart
Chemistry (CRN)
no counterpart
Statistical physics
Galam's majority-rule model with groups of three
Social sciences
no counterpart
Details, conditions and references
Relation
Same chain
Same mean-field map
With $D = 1$ the conformist recursion is $p' = 3p^2 - 2p^3$, the expected one-round map of binary 3-Majority with samples drawn with replacement. In a population of $N$ with non-overlapping generations in which every new individual samples its three models with replacement from the whole previous generation, $D = 1$ gives exactly synchronous binary 3-Majority on $K_N$ with self-loops; for $0 \le D \le 1$ the rule adopts the majority of the three with probability $D$ and otherwise copies one of them uniformly (the voter rule). Galam's majority rule of sociophysics (physics column), with groups of three, has the same map but updates whole groups at once, so only the mean-field maps agree. [3, 5, 6]
Conditions
- Two variants (opinions); sampling with replacement from the whole population; $D = 1$.
- No source in either field cites the other; the identification compares the rules, and the reading of Boyd and Richerson's table as "majority with probability $D$, otherwise copy" is ours.
Distributed computing
3-Majority dynamics [1, 2]
Synchronous rounds: every node samples three nodes uniformly at random, with replacement and possibly itself, and adopts the majority opinion of the three samples, ignoring its own opinion.
Population genetics and evolutionary biology
Conformist transmission with three models (cultural evolution) [3, 4, 5]
Each naive individual samples three models from the previous generation and acquires a variant held by 3, 2, 1, 0 of them with probability $1$, $\frac23 + \frac D3$, $\frac13 - \frac D3$, $0$, so the variant's frequency follows $p' = p + Dp(1-p)(2p-1)$ (Boyd and Richerson, Eq. 7.1). Individual-based versions sample the three models with replacement from the whole previous generation.
Epidemiology
No counterpart found.
Chemistry (chemical reaction networks)
No counterpart: Synchronous rounds. The sequential version updates one agent from three others, an interaction of four agents rather than a standard reaction; Condon et al. call synchronous 3-Majority "quite similar" to their trimolecular network with three or more species (next row).
Statistical physics and interacting particle systems
Galam's majority-rule model with groups of three [6]
Agents meet in randomly formed discussion groups and every group adopts its local majority at once (in a group of even size a tie makes the whole group adopt the status-quo opinion); with groups of three only, the proportion $P$ of one opinion follows $P \mapsto P^3 + 3P^2(1 - P)$ (Galam, Eq. 4 with $a_3 = 1$).
Social sciences
No counterpart found in sociology or economics; conformist transmission of cultural evolution is in the population-genetics column, and Galam's majority rule of sociophysics in the physics column.
In Leanamics
Lean: proved Conformist transmission is defined on counts, as population genetics defines Wright–Fisher: every new individual samples three models with replacement from the whole previous generation, so from $k$ carriers the next generation has $\mathrm{Bin}(N, p + Dp(1-p)(2p-1))$ carriers, $p = k/N$ (Plurality.conformistCountKernel; Boyd and Richerson's Eq. 7.1 follows from their table, Dynamics.conformistMap_eq_expect, and the table is the majority with probability $D$, otherwise a copy, Dynamics.conformistTable_eq). Synchronous binary 3-Majority on $K_N$ with self-loops lumps to it with $D = 1$ under the number of nodes holding opinion 1 (Plurality.binKernel_lumps); on labelled configurations the two coincide by definition. Its mean-field map is $3x^2 - 2x^3$ (Plurality.binKernel_meanField, from the exact one-round expectation $\mathbb E[X_{t+1}] = n(3x^2 - 2x^3)$), which is conformist transmission with $D = 1$ (Dynamics.conformistMap_one) and Galam's map with groups of three (Dynamics.galamMap_eq); Galam's process, which updates whole groups at once, is not formalized. Consensus theorems for 3-Majority.
- Correspondence:
Plurality.conformistCountKernel, Plurality.binKernel_lumps, Plurality.binKernel_meanField, Plurality.conformistCountKernel_meanField, Dynamics.conformistMap_eq_expect, Dynamics.conformistTable_eq, Dynamics.conformistMap_one, Dynamics.galamMap_eq
- Results:
ThreeMajority.avg_card_step, ThreeMajority.majority3_consensus_whp, Plurality.majority3_vanishing_bias, Plurality.majority3_any_start, Plurality.theorem_3_8
- Blueprint: plurality, sec:mean_field · dynamics, sec:relations · plurality, sec:map · plurality, sec:main-statement · plurality, sec:upper · plurality, sec:any_start
- Roadmap: MAJ-2, MAJ-7, MAJ-8
References
- L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, L. Trevisan (2014). Simple dynamics for plurality consensus. SPAA 2014, 247–256. doi:10.1145/2612669.2612677
- L. Becchetti, A. Clementi, E. Natale (2020). Consensus dynamics: an overview. ACM SIGACT News 51(1):58–104. doi:10.1145/3388392.3388403
- R. Boyd, P. J. Richerson (1985). Culture and the Evolutionary Process. University of Chicago Press (Chapter 7, Eq. 7.1, Table 7.1). ISBN 978-0-226-06931-9
- J. Henrich, R. Boyd (1998). The evolution of conformist transmission and the emergence of between-group differences. Evolution and Human Behavior 19(4):215–241. doi:10.1016/S1090-5138(98)00018-X
- A. Acerbi, A. Mesoudi, M. Smolla (2022). Individual-Based Models of Cultural Evolution: A Step-by-Step Guide Using R. Routledge. doi:10.4324/9781003282068
- S. Galam (2002). Minority opinion spreading in random geometry. European Physical Journal B 25(4):403–406. doi:10.1140/epjb/e20020045
Distributed computing
2-Choices; with two values, the median rule
Population genetics
no counterpart
Epidemiology
no counterpart
Chemistry (CRN)
Trimolecular approximate majority $2X + Y \to 3X$, $X + 2Y \to 3Y$
Statistical physics
Nonlinear $q$-voter model with $q = 2$, $\varepsilon = 0$; on $K_n$, the Sznajd model and the majority-rule model with groups of three
Social sciences
no counterpart
Details, conditions and references
Relation
Same chain
Same jump chain
Same mean-field map
Condon et al. note that the binary median rule "involves rules that are identical to the interactions" of this network. In the sequential version on $K_n$, where the activated node samples two distinct other nodes, a node of opinion $j$ switches to $i$ at a rate proportional to $x_j\binom{x_i}{2}$, the propensity of $2Z_i + Z_j \to 3Z_i$: the same jump chain. With samples drawn with replacement the rates are proportional to $x_j x_i^2$ instead, a difference of order $1/n$. The synchronous dynamics shares only the mean-field map $3p^2 - 2p^3$ with 3-Majority. The $q$-voter model with $q = 2$ and $\varepsilon = 0$ (physics column) is, rule for rule, sequential 2-Choices with the two neighbours sampled with replacement, on every graph; its authors note that it "practically coincides" with the Sznajd model in Slanina and Lavička's formulation. On $K_n$ that formulation draws a uniformly random ordered triple of distinct agents, so it is exactly sequential 2-Choices with two distinct samples other than the updating node, the version with the jump chain of the network. Krapivsky and Redner's majority rule with groups of three (a uniformly random group of three distinct agents adopts its majority) changes the configuration exactly when that version does, with three times its probability: the two have the same jump chain, and Slanina and Lavička note that on the complete graph their process differs from the majority model only by "rescaling certain variables". [4, 5, 6, 7]
Conditions
- Complete graph; sequential updates; two distinct samples other than the updating node.
- The exact identity is an elementary computation, not stated in the sources.
- The $q$-voter identity holds on every graph, with the two neighbours sampled with replacement; on a graph the Sznajd model of Slanina and Lavička draws the updated agent among the common neighbours of an agreeing pair, a different rule, so its identity with 2-Choices is stated for $K_n$ only.
- The identities with the $q$-voter, Sznajd and majority-rule models compare the rules (our computation); Slanina and Lavička's printed transition probabilities are first-order expansions in $1/N$ of the exact ones.
Distributed computing
2-Choices; with two values, the median rule [1, 2, 3]
A node samples two nodes and adopts their opinion if they agree, otherwise keeps its own: the majority of its own and two sampled opinions (the median of three values). Studied synchronously and sequentially (one activated node per step).
Population genetics and evolutionary biology
No counterpart found; conformist transmission uses three models and ignores the learner's own variant (previous row).
Epidemiology
No counterpart found.
Chemistry (chemical reaction networks)
Trimolecular approximate majority $2X + Y \to 3X$, $X + 2Y \to 3Y$ [4]
Common rate constant; with $k$ species, $2Z_i + Z_j \to 3Z_i$ for all $i \ne j$.
Statistical physics and interacting particle systems
Nonlinear $q$-voter model with $q = 2$, $\varepsilon = 0$; on $K_n$, the Sznajd model and the majority-rule model with groups of three [5, 6, 7]
"Choose one spin at random", then "$q$ neighbors (with possible repetition)"; "If all the $q$ neighbors are in the same state, the original spin takes the value of the $q$ neighbors", otherwise it flips with probability $\varepsilon$, and time advances by $1/N$ (Castellano, Muñoz and Pastor-Satorras). In Slanina and Lavička's formulation of the Sznajd model on the complete graph, agents $i$, then $j \ne i$, then $k \notin \{i, j\}$ are drawn and $k$ takes the opinion of $i$ and $j$ if they agree, "schematically as reactions $AAB \to AAA$, $BBA \to BBB$". In Krapivsky and Redner's majority rule, in its mean-field form, a random group of $G$ agents ($G$ odd) is picked and "The spins in the group all adopt the state of the local majority".
Social sciences
No counterpart found; the Sznajd model of opinion formation is in the physics column.
In Leanamics
Lean: partial The mean-field part: synchronous binary 2-Choices, which is the binary median rule as a kernel (Median.TwoChoices.kernel_bool), has the mean-field map $p \mapsto 3p^2 - 2p^3$ (Median.kernel_meanField, from the expected one-round map $n(3p^2 - 2p^3)$), Dynamics.majorityMap, which is also the mean-field map of binary 3-Majority (Plurality.binKernel_meanField, previous row). Consensus from a gap and from any configuration, with an adversary, on expanders and with many colours. The sequential version, the network and the physics models are not formalized, so the jump-chain and same-chain identities are not.
- Correspondence:
Median.kernel_meanField, Median.TwoChoices.kernel_bool
- Results:
Median.expected_ones, Median.consensus_whp, Median.binary_any_start, Median.median_consensus_any, Median.binary_almost_stable, Median.two_choices_expander, Median.TwoChoices.plurality_whp
- Blueprint: median, thm:mean-field · median, sec:dgmss-median · median, thm:binary-adv · median, sec:cer-two-choices · median, sec:efkmt-plurality
- Roadmap: MAJ-1, MAJ-3, MAJ-4, MAJ-5, MAJ-8
References
- B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, C. Scheideler (2011). Stabilizing consensus with the power of two choices. SPAA 2011, 149–158. doi:10.1145/1989493.1989516
- L. Becchetti, A. Clementi, E. Natale (2020). Consensus dynamics: an overview. ACM SIGACT News 51(1):58–104. doi:10.1145/3388392.3388403
- C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, T. Shiraga (2025). Asynchronous 3-Majority dynamics with many opinions. SODA 2025, 4095–4131. doi:10.1137/1.9781611978322.140
- A. Condon, M. Hajiaghayi, D. Kirkpatrick, J. Maňuch (2020). Approximate majority analyses using tri-molecular chemical reaction networks. Natural Computing 19(1):249–270. doi:10.1007/s11047-019-09756-4
- C. Castellano, M. A. Muñoz, R. Pastor-Satorras (2009). Nonlinear $q$-voter model. Physical Review E 80(4):041129. doi:10.1103/PhysRevE.80.041129 arXiv:0907.1775
- F. Slanina, H. Lavička (2003). Analytical results for the Sznajd model of opinion formation. European Physical Journal B 35(2):279–288. doi:10.1140/epjb/e2003-00278-0 arXiv:cond-mat/0305102
- P. L. Krapivsky, S. Redner (2003). Dynamics of majority rule in two-state interacting spin systems. Physical Review Letters 90(23):238701. doi:10.1103/PhysRevLett.90.238701 arXiv:cond-mat/0303182
Distributed computing
Sequential undecided-state dynamics, i.e. the approximate-majority population protocol
Population genetics
no counterpart
Epidemiology
no counterpart
Chemistry (CRN)
Approximate-majority network $X + Y \to X + B$, $X + Y \to Y + B$, $B + X \to 2X$, $B + Y \to 2Y$
Statistical physics
Three-state kinetic exchange opinion model without negative interactions
Social sciences
no counterpart
Details, conditions and references
Relation
Same chain
Same jump chain
Same continuous-time chain
The ordered pairs that change the configuration have weights $xy$, $yx$, $xb$, $yb$ out of $n(n-1)$, proportional to the mass-action propensities, so the protocol's count chain has the jump chain of the network; when every ordered pair interacts at rate $1/(n-1)$ it is the network's continuous-time chain with rate constant $1/(n-1)$. Angluin, Aspnes and Eisenstat consider "the Population-Protocol model which is, in our specific context, equivalent to the sequential PULL model" (Clementi et al.). In the kinetic exchange model (physics column) $\mathrm{sgn}(o_i + o_j)$ is the protocol's rule for all nine pairs of states, with $i$ the responder and $j$ the initiator, so with a uniformly random ordered pair of distinct agents per step it is the same chain as the approximate-majority protocol. If both agents update, as for Biswas, Chatterjee and Sen, two opposite opinions both become $0$: the count chain has the jump chain of $X + Y \to 2B$, $B + X \to 2X$, $B + Y \to 2Y$, the variant built by Chen et al. [2, 3, 9, 7, 8, 6]
Conditions
- Complete graph (well mixed), sequential.
- The synchronous undecided-state dynamics is a different chain (for instance, it can make every node undecided) and has no CRN counterpart; on other interaction graphs the protocol is a graph population protocol, without CRN counterpart.
- The identities with the kinetic exchange models compare the rules (our computation); no source relating them to approximate majority was found.
Distributed computing
Sequential undecided-state dynamics, i.e. the approximate-majority population protocol [1, 2, 3, 4]
One uniformly random ordered pair (initiator, responder) of distinct agents per step; a decided responder becomes undecided if the initiator holds the other opinion, and an undecided responder adopts the initiator's opinion. In the undecided-state dynamics the node that samples is the responder. Perron, Vasudevan and Vojnović study the continuous-time version.
Population genetics and evolutionary biology
No counterpart found.
Epidemiology
No counterpart found.
Chemistry (chemical reaction networks)
Approximate-majority network $X + Y \to X + B$, $X + Y \to Y + B$, $B + X \to 2X$, $B + Y \to 2Y$ [5, 6]
Common rate constant. Cardelli and Csikász-Nagy argue that the cell-cycle switch computes it; a variant with $X + Y \to 2B$ was built with DNA strand displacement (Chen et al.).
Statistical physics and interacting particle systems
Three-state kinetic exchange opinion model without negative interactions [7, 8]
Opinions $+1$, $-1$ and $0$ (undecided) on the complete graph; a random agent $i$ meets another agent $j$, "in a way that $j$ will influence $i$", and $o_i(t+1) = \mathrm{sgn}[o_i(t) + o_j(t)]$ (Crokidakis, the case of no independent behaviour), which he presents as the model of Biswas, Chatterjee and Sen with no negative interactions; in theirs both agents of the pair update.
Social sciences
No counterpart found.
In Leanamics
Lean: partial The network's jump chain equals the population protocol of the network conditioned on reacting (Crn.ApproxMajority.network_jumpKernel_eq_ppKernel, a protocol that also draws a uniform reaction): the protocol on count vectors and the network have the same jump chain (Crn.ApproxMajority.network_sameJumpChain, a Dynamics.Kernel.SameJumpChain). The sequential undecided-state dynamics is defined as Angluin, Aspnes and Eisenstat's protocol, and its convergence and correctness are proved. That the two protocols have the same count chain is not formalized.
- Correspondence:
Crn.ApproxMajority.network_jumpKernel_eq_ppKernel, Crn.ApproxMajority.network_sameJumpChain, Undecided.Sequential.step
- Results:
Undecided.Sequential.consensus_whp, Undecided.Sequential.majority_whp, Undecided.Sequential.approximate_majority, Crn.ApproxMajority.winProb_minority_le_majority, Crn.ApproxMajority.half_le_absorbProb_majority
- Blueprint: undecided, sec:aae-approx-majority · crn, thm:am · crn, thm:crn1-jump · crn, sec:mnrs-graph-majority
- Roadmap: UND-2, CRN-1, CRN-4
References
- D. Angluin, J. Aspnes, D. Eisenstat (2008). A simple population protocol for fast robust approximate majority. Distributed Computing 21(2):87–102. doi:10.1007/s00446-008-0059-z
- L. Becchetti, A. Clementi, E. Natale (2020). Consensus dynamics: an overview. ACM SIGACT News 51(1):58–104. doi:10.1145/3388392.3388403
- A. Clementi, M. Ghaffari, L. Gualà, E. Natale, F. Pasquale, G. Scornavacca (2018). A tight analysis of the parallel undecided-state dynamics with two colors. MFCS 2018, LIPIcs 117, 28. doi:10.4230/LIPIcs.MFCS.2018.28
- E. Perron, D. Vasudevan, M. Vojnović (2009). Using three states for binary consensus on complete graphs. IEEE INFOCOM 2009, 2527–2535. doi:10.1109/INFCOM.2009.5062181
- L. Cardelli, A. Csikász-Nagy (2012). The cell cycle switch computes approximate majority. Scientific Reports 2:656. doi:10.1038/srep00656
- Y.-J. Chen, N. Dalchau, N. Srinivas, A. Phillips, L. Cardelli, D. Soloveichik, G. Seelig (2013). Programmable chemical controllers made from DNA. Nature Nanotechnology 8(10):755–762. doi:10.1038/nnano.2013.189
- N. Crokidakis (2014). Phase transition in kinetic exchange opinion models with independence. Physics Letters A 378(24–25):1683–1686. doi:10.1016/j.physleta.2014.04.028 arXiv:1404.4356
- S. Biswas, A. Chatterjee, P. Sen (2012). Disorder induced phase transition in kinetic models of opinion dynamics. Physica A: Statistical Mechanics and its Applications 391(11):3257–3265. doi:10.1016/j.physa.2012.01.046 arXiv:1102.0902
- D. Doty (2014). Timing in chemical reaction networks. SODA 2014, 772–784. doi:10.1137/1.9781611973402.57 arXiv:1304.0872
Population protocols and reaction networks
Distributed computing
Population protocols
Population genetics
no counterpart
Epidemiology
no counterpart
Chemistry (CRN)
Stochastic CRNs whose reactions have two reactants and two products
Statistical physics
no counterpart
Social sciences
no counterpart
Details, conditions and references
Relation
Same jump chain
Same continuous-time chain
The uniformly random pair model "coincides precisely with the model of stochastic chemical kinetics, so long as the CRN's reactions each have two reactants and two products" (Doty). A uniformly random ordered pair of distinct agents has species $\{A, B\}$ with probability $x_A x_B/\binom{n}{2}$, or $\binom{x_A}{2}/\binom{n}{2}$ if $A = B$, proportional to the propensity, so the protocol conditioned on the pair reacting is the jump chain of the network, on count vectors; unequal rate constants correspond to a weighted scheduler. Population protocols stably compute exactly the semilinear predicates, hence so do these networks. [7, 9, 11, 1, 2]
Conditions
- Common rate constant; Gillespie's propensity $k\binom{x_A}{2}$ for $A + A$.
- Several reactions with the same reactants (or probabilistic outcomes) need a randomized or initiator/responder protocol; deterministic one-way protocols such as approximate majority use the asymmetry of the pair.
- Complete interaction graph; protocols on other graphs have no CRN counterpart.
Distributed computing
Population protocols [1, 2, 3, 4, 5, 6]
Anonymous finite-state agents; one ordered pair of distinct agents interacts per step (uniformly at random in the probabilistic model) and both update by a transition function. Examples formalized here: exact majority with four states on any connected graph (the ambassador protocol, which on $K_n$ has the count chain of binary interval consensus) and deterministic plurality protocols.
Population genetics and evolutionary biology
No general counterpart; individual protocols on $K_n$ are Moran-type models (the copying rows).
Epidemiology
No general counterpart; the SI epidemic and the Daley–Kendall and Maki–Thompson rumour models are instances (spreading rows), while the removal $I \to R$ of the SIR epidemic involves a single agent.
Chemistry (chemical reaction networks)
Stochastic CRNs whose reactions have two reactants and two products [7, 8, 9, 10]
Mass-action kinetics with a common rate constant, in a volume proportional to $n$.
Statistical physics and interacting particle systems
No general counterpart beyond the chemistry column: on $K_n$ a population protocol is a well-mixed system of pairwise reactions; the kinetic exchange model of row approximate-majority is one instance.
Social sciences
No counterpart found.
In Leanamics
Lean: proved The jump chain of mass-action kinetics equals the protocol conditioned on reacting (CRN-1): the protocol on count vectors and the network have the same jump chain (Crn.ppStepKernel_sameJumpChain, a Dynamics.Kernel.SameJumpChain). The easy direction of stable computation (CRN-3): Boolean combinations of threshold and remainder predicates are stably computable, hence stably decided by such networks. Majority on connected graphs with four states, optimal (CRN-4), and deterministic exact majority and plurality (CRN-5) in the same framework.
- Correspondence:
Crn.jumpKernel_eq_ppKernel, Crn.condStep_eq_jumpKernel, Crn.pair_prob_eq_propensity, Crn.ppStepKernel_sameJumpChain
- Results:
Crn.IsSemilinearPred.stablyComputable, Crn.IsSemilinearPred.exists_network, Crn.ambassador_graphStablyComputes, Crn.rank_majority_eq_four, Crn.absoluteMajority_stablyComputes, Crn.relativeMajority_stablyMarks
- Blueprint: crn, thm:crn1 · crn, thm:crn1-jump · crn, sec:aadfp-stable · crn, sec:mnrs-graph-majority · crn, sec:ghmss-exact-majority
- Roadmap: CRN-1, CRN-3, CRN-4, CRN-5
References
- D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, R. Peralta (2006). Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4):235–253. doi:10.1007/s00446-005-0138-3
- D. Angluin, J. Aspnes, D. Eisenstat, E. Ruppert (2007). The computational power of population protocols. Distributed Computing 20(4):279–304. doi:10.1007/s00446-007-0040-2
- G. B. Mertzios, S. E. Nikoletseas, C. L. Raptopoulos, P. G. Spirakis (2014). Determining majority in networks with local interactions and very small local memory. ICALP 2014, LNCS 8572, 871–882 (Distributed Computing 30(1):1–16, 2017). doi:10.1007/978-3-662-43948-7_72
- F. Bénézit, P. Thiran, M. Vetterli (2009). Interval consensus: from quantized gossip to voting. IEEE ICASSP 2009, 3661–3664. doi:10.1109/ICASSP.2009.4960420
- D. Alistarh, J. Aspnes, R. Gelashvili (2018). Space-optimal majority in population protocols. SODA 2018, 2221–2239. doi:10.1137/1.9781611975031.144
- L. Gąsieniec, D. Hamilton, R. Martin, P. G. Spirakis, G. Stachowiak (2016). Deterministic population protocols for exact majority and plurality. OPODIS 2016, LIPIcs 70, 14. doi:10.4230/LIPIcs.OPODIS.2016.14
- D. Doty (2014). Timing in chemical reaction networks. SODA 2014, 772–784. doi:10.1137/1.9781611973402.57 arXiv:1304.0872
- H.-L. Chen, D. Doty, D. Soloveichik (2014). Deterministic function computation with chemical reaction networks. Natural Computing 13(4):517–534. doi:10.1007/s11047-013-9393-6
- D. Doty, M. Eftekhari (2021). A survey of size counting in population protocols. Theoretical Computer Science 894:91–102. doi:10.1016/j.tcs.2021.08.038
- D. Soloveichik, M. Cook, E. Winfree, J. Bruck (2008). Computation with finite stochastic chemical reaction networks. Natural Computing 7(4):615–633. doi:10.1007/s11047-008-9067-y
- D. T. Gillespie (1977). Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry 81(25):2340–2361. doi:10.1021/j100540a008
Spreading processes
Distributed computing
Push, pull and push–pull rumor spreading
Population genetics
no counterpart
Epidemiology
SI epidemic (Bailey's simple stochastic epidemic)
Chemistry (CRN)
$S + I \to 2I$
Statistical physics
First-passage percolation with exponential passage times (Richardson's growth model)
Social sciences
Bass model of new-product diffusion with imitation only
Details, conditions and references
Relation
Same continuous-time chain
Same mean-field map
On $K_n$, asynchronous push and asynchronous pull have exactly the same law: every informed–uninformed pair transmits at rate $1/(n-1)$, so the number of informed nodes is Bailey's simple epidemic with $\beta = 1/(n-1)$, the chain of $S + I \to 2I$ with rate constant $1/(n-1)$; push–pull is the same process at twice the speed. The synchronous protocols are discrete-time SI models with one call per node per round; their spreading times differ ($\log_2 n + \ln n$ for push, $\log_2 n + \log_2 \ln n$ for pull, $\log_3 n + \log_2 \ln n$ for push–pull, up to $O(1)$) and they have no CRN counterpart. Physics column: with independent exponential passage times of rate $\nu$, the first-passage ball around the initial set grows as the SI epidemic with rate $\nu$ per edge, by the memoryless property; Aldous calls this epidemic the Pandemic process and notes that from a given initial agent its infection times have the law of the first-passage distances, although the two models differ as arrays over all pairs of agents. On $K_n$, asynchronous push or pull is therefore first-passage percolation with rate $1/(n-1)$, Janson's model with rate 1 slowed down by a factor $n - 1$; on regular graphs "the asynchronous push&pull protocol, Richardson's model, and first-passage percolation are essentially the same process, assuming appropriate parameters are chosen" (Acan et al.). Social column: for $P = 0$ the Bass equation is the logistic equation, the mean field of Bailey's epidemic with $Q = \beta N$ ($N$ the population size). Goldenberg, Libai and Muller's model with $p = 0$ is a discrete-time SI epidemic on $K_N$ in which every informed–uninformed pair transmits with probability $q$ in each period; for $q = 1/n$ a node is informed with the same probability as in synchronous push with calls to oneself, but the two chains differ (push informs at most as many new nodes as there are callers). [6, 5, 7, 11, 9, 10, 12, 13, 14]
Conditions
- Complete graph; the identity with the network is for the asynchronous protocols.
- The jump chain of $S + I \to 2I$ is deterministic (one more infected per reaction), so the correspondence is in the timing, between continuous-time chains.
- Calls to oneself: Frieze and Grimmett and Karp et al. allow them, as the library
Epidemics does; the library RumorSpread (also in epidemics/) does not. The identification above is an elementary computation, not stated in the sources.
- The first-passage description holds on every graph, for the infected set grown from a given initial set; with other passage-time distributions the growth is not a Markov chain.
- The Bass model is deterministic and shares only the mean field; the comparisons with the Bass equation and with Goldenberg, Libai and Muller's rule are our computation.
Distributed computing
Push, pull and push–pull rumor spreading [1, 2, 3, 4, 5, 6]
On $K_n$ every node calls a uniformly random node; the rumor goes from caller to callee (push), from callee to caller (pull), or both (push–pull). Synchronously, in rounds, push informs everybody in $\log_2 n + \ln n + O(1)$ rounds; asynchronously, every node calls at the times of a rate-1 Poisson clock. Demers et al. call anti-entropy, in which sites reconcile their databases with random sites by push, pull or push–pull, a "simple epidemic".
Population genetics and evolutionary biology
No counterpart.
Epidemiology
SI epidemic (Bailey's simple stochastic epidemic) [7]
Susceptible and infected individuals, no removal; in continuous time, new infections occur at rate $\beta S I$ (Bailey writes $\beta y(n - y + 1)$, with $y$ the number of susceptibles).
Chemistry (chemical reaction networks)
$S + I \to 2I$ [8]
Autocatalytic conversion with mass-action kinetics.
Statistical physics and interacting particle systems
First-passage percolation with exponential passage times (Richardson's growth model) [9, 10, 11, 12]
Every edge gets an independent passage time and the infection crosses it in that time; with exponential times "the memoryless property of the distribution implies that the growth of the infected/colonized region is equal in distribution to a time change of a type of Eden process", and for general times the growth "is called a 1-type Richardson model" (Auffinger, Damron and Hanson). Richardson's original model of 1973 is in discrete time: every healthy site with an infected neighbour is infected with probability $p$ at each step.
Social sciences
Bass model of new-product diffusion with imitation only [13, 14]
The adopted fraction $F$ has hazard $f/(1 - F) = P + QF$, with $P$ the external influence (advertising) and $Q$ the internal one (word of mouth), so for $P = 0$ it is the logistic equation $F' = QF(1 - F)$. In Goldenberg, Libai and Muller's individual-level version a non-adopter adopts in a period with probability $1 - (1-p)(1-q)^{k(t)}$, "where $k(t)$ is the number of previous adopters": every adopter keeps influencing in every period.
In Leanamics
Lean: results Synchronous push, pull and push–pull on $K_n$: all nodes informed within $O(\log n)$ rounds w.h.p. without calls to oneself (library RumorSpread of epidemics/), and the sharp times with matching lower bounds with calls to oneself (library Epidemics, Doerr and Kostrygin); the two models are different processes, and neither development uses the other. The asynchronous protocols and the network are not formalized.
- Results:
RumorPush.push_informs_all_whp, RumorPush.pull_informs_all_whp, RumorPush.pushPull_informs_all_whp, Epidemics.Revisited.push_spreading_tail, Epidemics.Revisited.push_spreading_lower_tail, Epidemics.Revisited.pull_spreading_tail, Epidemics.Revisited.pushPull_spreading_tail
- Blueprint: epidemics, sec:main-statement · epidemics, sec:pull · epidemics, sec:doerr-kostrygin · epidemics, sec:doerr-kostrygin-lower
- Roadmap: EPI-5, EPI-8
References
- A. M. Frieze, G. R. Grimmett (1985). The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics 10(1):57–77. doi:10.1016/0166-218X(85)90059-9
- B. Pittel (1987). On spreading a rumor. SIAM Journal on Applied Mathematics 47(1):213–223. doi:10.1137/0147013
- R. Karp, C. Schindelhauer, S. Shenker, B. Vöcking (2000). Randomized rumor spreading. FOCS 2000, 565–574. doi:10.1109/SFCS.2000.892324
- B. Doerr, A. Kostrygin (2017). Randomized rumor spreading revisited. ICALP 2017, LIPIcs 80, 138. doi:10.4230/LIPIcs.ICALP.2017.138
- A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, D. Terry (1987). Epidemic algorithms for replicated database maintenance. PODC 1987, 1–12. doi:10.1145/41840.41841
- H. Acan, A. Collevecchio, A. Mehrabian, N. Wormald (2017). On the push&pull protocol for rumor spreading. SIAM Journal on Discrete Mathematics 31(2):647–668. doi:10.1137/15M1033113
- N. T. J. Bailey (1950). A simple stochastic epidemic. Biometrika 37(3/4):193–202. doi:10.1093/biomet/37.3-4.193
- O. Kahramanoğulları (2019). On quantitative comparison of chemical reaction network models. EPTCS 296:14–27. doi:10.4204/EPTCS.296.5
- A. Auffinger, M. Damron, J. Hanson (2017). 50 Years of First-Passage Percolation. University Lecture Series 68, American Mathematical Society. doi:10.1090/ulect/068 arXiv:1511.03262
- D. Richardson (1973). Random growth in a tessellation. Mathematical Proceedings of the Cambridge Philosophical Society 74(3):515–528. doi:10.1017/S0305004100077288
- D. Aldous (2013). Interacting particle systems as stochastic social dynamics. Bernoulli 19(4):1122–1149. doi:10.3150/12-BEJSP04
- S. Janson (1999). One, two and three times log n/n for paths in a complete graph with random weights. Combinatorics, Probability and Computing 8(4):347–361. doi:10.1017/S0963548399003892
- F. M. Bass (1969). A new product growth for model consumer durables. Management Science 15(5):215–227. doi:10.1287/mnsc.15.5.215
- J. Goldenberg, B. Libai, E. Muller (2001). Using complex systems analysis to advance marketing theory development: modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review 2001(9). (no DOI (online journal); Academy of Marketing Science Review 2001, no. 9)
Distributed computing
Independent Cascade model
Population genetics
no counterpart
Epidemiology
Reed–Frost chain-binomial SIR epidemic (on a graph)
Chemistry (CRN)
no counterpart
Statistical physics
Bond percolation; the general epidemic process with a fixed infectious period
Social sciences
no counterpart
Details, conditions and references
Relation
Same chain
Pathwise coupling
Independent Cascade with $p_{v,w} = p$ on an undirected graph is the Reed–Frost epidemic on that graph (Draief, Ganesh and Massoulié call this rule "the Reed-Frost model"). Both are coupled pathwise with bond percolation (physics column): "A node $x$ ends up active if and only if there is a path from some node in $A$ to $x$ consisting entirely of live edges" (Kempe, Kleinberg and Tardos, Claim 2.3), and with one coin per edge the nodes infected in round $t$ are those at distance $t$ from the initial set in the graph of open edges. This is exact because the infectious period is fixed: Grassberger shows that a fixed period gives "precisely the problem of bond percolation" while exponential periods give "neither site nor bond percolation"; Newman's 2002 claim of an exact isomorphism for random infectious periods needs a major correction (Kenah and Robins: the mapping gives the right threshold and final size, but not the distribution of outbreak sizes or the probability of an epidemic). [1, 6, 9, 10, 11, 8, 3, 12]
Conditions
- Each edge is tried at most once (after its coin is seen from an infected endpoint, that endpoint is removed), so one coin per edge has the same law as fresh coins.
- With asymmetric $p_{v,w}$ the coupling is with directed percolation.
- Of the two marketing papers that Kempe, Kleinberg and Tardos cite for Independent Cascade, the AMS Review paper of Goldenberg, Libai and Muller has adopters influence in every period (a discrete-time SI process, row si-rumor); the Marketing Letters paper, on strong and weak ties, could not be read.
Distributed computing
Independent Cascade model [1, 2, 3]
Synchronous rounds; "When node $v$ first becomes active in step $t$, it is given a single chance to activate each currently inactive neighbor $w$; it succeeds with a probability $p_{v,w}$" (Kempe, Kleinberg and Tardos, who note its study in marketing by Goldenberg, Libai and Muller); used for influence maximization.
Population genetics and evolutionary biology
No counterpart.
Epidemiology
Reed–Frost chain-binomial SIR epidemic (on a graph) [4, 5, 6]
Discrete generations; each infective infects each susceptible neighbour independently with probability $p$, and the infectives of a generation are removed at its end (a fixed infectious period).
Chemistry (chemical reaction networks)
No counterpart: Generations are synchronous and the infectious period is fixed. The mass-action SIR network (row sir-kermack-mckendrick) has exponentially distributed infectious periods: a different epidemic, which shares only the large-population final-size equation.
Statistical physics and interacting particle systems
Bond percolation; the general epidemic process with a fixed infectious period [7, 8, 9]
In Bernoulli bond percolation, introduced by Broadbent and Hammersley, "each edge is open with probability $p$ ... independently of the state of other edges" (Duminil-Copin); the final set of the epidemic is the set of vertices joined to the initial set by open paths. Grassberger studies the SIR epidemic on lattices as the general epidemic process, which with a fixed infectious period is bond percolation (relation).
Social sciences
No counterpart found. Kempe, Kleinberg and Tardos place Independent Cascade in the marketing work of Goldenberg, Libai and Muller, but in the homogeneous model of their AMS Review paper every previous adopter influences each non-adopter in every period, not once (row si-rumor).
In Leanamics
Lean: proved The pathwise coupling with one coin per edge, and the equality of infection and connection probabilities with i.i.d. coins (EPI-1); subcritical and supercritical outbreaks through percolation (EPI-2, EPI-3, EPI-6). The identity in law between one coin per edge and fresh coins in every round is not formalized.
- Correspondence:
Epidemics.infected_iff, Epidemics.final_recovered_iff, Epidemics.prob_infected_eq_prob_connected
- Results:
Epidemics.reedFrost_subcritical, Epidemics.reedFrost_large_outbreak, Epidemics.swg_reedFrost_subcritical, Epidemics.swg3_reedFrost_subcritical
- Blueprint: epidemics, sec:kkt-live-edge · epidemics, sec:bcdptz-small-world · epidemics, sec:krivelevich-sudakov
- Roadmap: EPI-1, EPI-2, EPI-3, EPI-6
References
- D. Kempe, J. Kleinberg, É. Tardos (2003). Maximizing the spread of influence through a social network. KDD 2003, 137–146. doi:10.1145/956750.956769
- D. Kempe, J. Kleinberg, É. Tardos (2015). Maximizing the spread of influence through a social network. Theory of Computing 11:105–147. doi:10.4086/toc.2015.v011a004
- J. Goldenberg, B. Libai, E. Muller (2001). Talk of the network: a complex systems look at the underlying process of word-of-mouth. Marketing Letters 12(3):211–223. doi:10.1023/A:1011122126881
- H. Abbey (1952). An examination of the Reed-Frost theory of epidemics. Human Biology 24(3):201–233. PubMed 12990130
- T. Britton (2010). Stochastic epidemic models: a survey. Mathematical Biosciences 225(1):24–35. doi:10.1016/j.mbs.2010.01.006
- M. Draief, A. Ganesh, L. Massoulié (2008). Thresholds for virus spread on networks. Annals of Applied Probability 18(2):359–378. doi:10.1214/07-AAP470
- S. R. Broadbent, J. M. Hammersley (1957). Percolation processes: I. Crystals and mazes. Mathematical Proceedings of the Cambridge Philosophical Society 53(3):629–641. doi:10.1017/S0305004100032680
- H. Duminil-Copin (2019). Sixty years of percolation. Proceedings of the International Congress of Mathematicians (ICM 2018), 2829–2856. doi:10.1142/9789813272880_0162 arXiv:1712.04651
- P. Grassberger (1983). On the critical behavior of the general epidemic process and dynamical percolation. Mathematical Biosciences 63(2):157–172. doi:10.1016/0025-5564(82)90036-0
- M. E. J. Newman (2002). Spread of epidemic disease on networks. Physical Review E 66:016128. doi:10.1103/PhysRevE.66.016128
- E. Kenah, J. M. Robins (2007). Second look at the spread of epidemics on networks. Physical Review E 76:036113. doi:10.1103/PhysRevE.76.036113
- J. Goldenberg, B. Libai, E. Muller (2001). Using complex systems analysis to advance marketing theory development: modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review 2001(9). (no DOI (online journal); Academy of Marketing Science Review 2001, no. 9)
Distributed computing
Linear Threshold model
Population genetics
no counterpart
Epidemiology
no counterpart
Chemistry (CRN)
no counterpart
Statistical physics
Bootstrap percolation
Social sciences
Threshold models of collective behavior
Details, conditions and references
Relation
Same deterministic recursion
Given the thresholds, the three models are the same deterministic dynamics: an inactive node becomes active, for good, once the weight of its active neighbours reaches its threshold, and since activation is monotone the final set does not depend on the order of the updates. Granovetter's model is this dynamics on the complete graph with weight $1/N$ for every other member of a group of $N$ (members with threshold 0 act first), and his friendship weights give other weights. Bootstrap percolation with threshold $r$ is the case $b_{v,w} = 1/\deg v$, $\theta_v = r/\deg v$, and Watts's model with a common threshold fraction $\phi$ on a $d$-regular graph is bootstrap percolation with $r = \lceil \phi d \rceil$ (Watts updates the nodes in random asynchronous order, which changes the intermediate sets but not the final one). The models differ in what is random: Linear Threshold draws independent uniform thresholds and fixes the initial set, bootstrap percolation fixes the thresholds and draws the initial set, Granovetter takes both as given, and Watts draws both. With uniform thresholds, the final active set of Linear Threshold has the law of the set reached from $A$ by live-edge paths when every node $v$ keeps at most one incoming edge, from $w$ with probability $b_{v,w}$ (Kempe, Kleinberg and Tardos, Claim 2.6); their proof goes iteration by iteration, and indeed the whole sequence of active sets has the law of the sequence of sets reached within $t$ steps. Independent Cascade is reachability with independent live edges (row reed-frost); both are special cases of their triggering model, and their general threshold and general cascade models are equivalent. The two processes differ: a node with two active in-neighbours of weight $1/2$ becomes active surely under Linear Threshold, and with probability $3/4$ under Independent Cascade with $p = 1/2$. [1, 4, 5, 3]
Conditions
- Same dynamics given the thresholds and the initial set; weights $b_{v,w}$ are arbitrary in Linear Threshold, $1/N$ (or friendship weights) for Granovetter, $1/\deg v$ for bootstrap percolation.
- The live-edge representation needs independent uniform thresholds.
- The identifications of Granovetter's model, bootstrap percolation and Watts's model as threshold dynamics with fixed thresholds, and the identity in law of the whole sequences, are our computation; Kempe, Kleinberg and Tardos name Granovetter among the first to propose models with node-specific thresholds, Balogh et al. mention that sociologists (Granovetter, Watts) have studied the bootstrap process, and Watts contrasts his fractional thresholds with bootstrap percolation.
Distributed computing
Linear Threshold model [1]
"Each node $v$ chooses a threshold $\theta_v$ uniformly at random from the interval $[0, 1]$", and in every step a node becomes active, for good, once the total weight $\sum_w b_{v,w}$ of its active neighbours (with $\sum_w b_{v,w} \le 1$) is at least $\theta_v$ (Kempe, Kleinberg and Tardos, for influence maximization). The random thresholds model "our lack of knowledge of their values"; they contrast approaches that "hard-wire all thresholds at a known value like 1/2".
Population genetics and evolutionary biology
No counterpart found.
Epidemiology
No counterpart found.
Chemistry (chemical reaction networks)
No counterpart: once the thresholds are drawn the dynamics is deterministic, in synchronous rounds.
Statistical physics and interacting particle systems
Bootstrap percolation [2, 3]
In $r$-neighbour bootstrap percolation "a (typically random) set $A$ of initially 'infected' vertices spreads by infecting (at each time step) vertices with at least $r$ already-infected neighbours", the vertices of $A$ being usually chosen independently with density $p$; it "was introduced in 1979 by Chalupa, Leath and Reich in the context of disordered magnetic systems" (Balogh, Bollobás, Duminil-Copin and Morris).
Social sciences
Threshold models of collective behavior [4, 5]
A person's threshold is "the proportion of the group he would have to see join before he would do so", so the proportion of the group that has joined follows "$r(t + 1) = F[r(t)]$", with $F$ the distribution function of the thresholds; with social structure, friends count more than strangers in a weighted "perceived proportion" (Granovetter). On random networks with thresholds that are fractions of the neighbours, it is Watts's cascade model.
In Leanamics
Lean: not formalized Not formalized and not a target of the roadmap; the closest formal result is the live-edge coupling of Independent Cascade with bond percolation (row reed-frost, EPI-1).
References
- D. Kempe, J. Kleinberg, É. Tardos (2003). Maximizing the spread of influence through a social network. KDD 2003, 137–146. doi:10.1145/956750.956769
- J. Chalupa, P. L. Leath, G. R. Reich (1979). Bootstrap percolation on a Bethe lattice. Journal of Physics C: Solid State Physics 12(1):L31–L35. doi:10.1088/0022-3719/12/1/008
- J. Balogh, B. Bollobás, H. Duminil-Copin, R. Morris (2012). The sharp threshold for bootstrap percolation in all dimensions. Transactions of the American Mathematical Society 364(5):2667–2701. doi:10.1090/S0002-9947-2011-05552-2 arXiv:1010.3326
- M. Granovetter (1978). Threshold models of collective behavior. American Journal of Sociology 83(6):1420–1443. doi:10.1086/226707
- D. J. Watts (2002). A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences 99(9):5766–5771. doi:10.1073/pnas.082090499
Distributed computing
Rumor mongering with blind loss of interest
Population genetics
no counterpart
Epidemiology
General stochastic epidemic (Markovian SIR) and the Kermack–McKendrick equations
Chemistry (CRN)
$S + I \to 2I$ (rate $\beta/N$), $I \to R$ (rate $\gamma$)
Statistical physics
no counterpart
Social sciences
no counterpart
Details, conditions and references
Relation
Same continuous-time chain
Large-population limit
Same mean-field map
The Markovian SIR epidemic is the stochastic mass-action chain of the network, and the Kermack–McKendrick equations are its rate equations; by Kurtz's law of large numbers the scaled counts $(S, I, R)/N$ converge to their solution, uniformly on bounded time intervals. On $K_n$, the asynchronous blind–coin rule (calls at rate 1, removal with probability $1/k$ per call) has the infection rate $SI/(n-1)$ and the removal rate $I/k$ of the network with $\beta/N = 1/(n-1)$ and $\gamma = 1/k$, but it is not the same chain (one call can infect the callee and remove the caller); its mean field is Kermack–McKendrick with $R_0 = k$, consistent with the residues simulated by Demers et al. The Reed–Frost epidemic has the same large-population final-size equation $1 - z = e^{-R_0 z}$ but a different law (for instance, a different probability of a major outbreak). [8, 5, 9, 10]
Conditions
- Well mixed; mass action in volume $N$.
- The SIR reading of Demers et al.'s blind–coin variant and its mean field are ours; they do not call it SIR.
Distributed computing
Rumor mongering with blind loss of interest [1]
Demers et al.'s "blind" variant: an infective site calls a random site and, whatever the outcome, stops spreading with probability $1/k$ ("coin").
Population genetics and evolutionary biology
No counterpart.
Epidemiology
General stochastic epidemic (Markovian SIR) and the Kermack–McKendrick equations [2, 3, 4, 5]
Infection at rate $\beta SI/N$, removal at rate $\gamma I$; the deterministic model $s' = -\beta s i$, $i' = \beta s i - \gamma i$, $r' = \gamma i$, with $R_0 = \beta/\gamma$, has an epidemic ($i$ first increases) iff $R_0 s_0 > 1$, and, when $r_0 = 0$, the final size $s_\infty = s_0 e^{-R_0(1 - s_\infty)}$.
Chemistry (chemical reaction networks)
$S + I \to 2I$ (rate $\beta/N$), $I \to R$ (rate $\gamma$) [6, 7]
Stochastic mass-action kinetics; its deterministic rate equations are Kermack and McKendrick's.
Statistical physics and interacting particle systems
No separate counterpart: statistical physics studies the Markovian SIR epidemic on lattices as the general epidemic process, which with exponentially distributed infectious periods corresponds to neither site nor bond percolation (row reed-frost).
Social sciences
No counterpart found.
In Leanamics
Lean: partial Kermack–McKendrick (EPI-7): threshold, peak and final-size equation for every solution. Kurtz's law of large numbers (CRN-2) for the uniformized chain in discrete time, with natural-number rates; the continuous-time chain is not formalized.
- Correspondence:
Epidemics.Kurtz.law_of_large_numbers, Epidemics.Kurtz.tendsto_deviationProb
- Results:
Epidemics.KermackMcKendrick.IsSolution.initially_increasing_iff, Epidemics.KermackMcKendrick.IsSolution.final_size, Epidemics.KermackMcKendrick.IsSolution.final_size_unique, Epidemics.KermackMcKendrick.IsSolution.exists_peak
- Blueprint: epidemics, sec:kermack-mckendrick · epidemics, sec:kurtz
- Roadmap: EPI-7, CRN-2
References
- A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, D. Terry (1987). Epidemic algorithms for replicated database maintenance. PODC 1987, 1–12. doi:10.1145/41840.41841
- W. O. Kermack, A. G. McKendrick (1927). A contribution to the mathematical theory of epidemics. Proceedings of the Royal Society A 115(772):700–721. doi:10.1098/rspa.1927.0118
- M. S. Bartlett (1949). Some evolutionary stochastic processes. Journal of the Royal Statistical Society, Series B 11(2):211–229. doi:10.1111/j.2517-6161.1949.tb00031.x
- H. W. Hethcote (2000). The mathematics of infectious diseases. SIAM Review 42(4):599–653. doi:10.1137/S0036144500371907
- T. Britton, E. Pardoux (eds.) (2019). Stochastic Epidemic Models with Inference. Lecture Notes in Mathematics 2255, Springer. doi:10.1007/978-3-030-30900-8
- O. Kahramanoğulları (2019). On quantitative comparison of chemical reaction network models. EPTCS 296:14–27. doi:10.4204/EPTCS.296.5
- T. G. Kurtz (1972). The relationship between stochastic and deterministic models for chemical reactions. Journal of Chemical Physics 57(7):2976–2978. doi:10.1063/1.1678692
- T. G. Kurtz (1970). Solutions of ordinary differential equations as limits of pure jump Markov processes. Journal of Applied Probability 7(1):49–58. doi:10.2307/3212147
- T. Britton (2010). Stochastic epidemic models: a survey. Mathematical Biosciences 225(1):24–35. doi:10.1016/j.mbs.2010.01.006
- B. von Bahr, A. Martin-Löf (1980). Threshold limit theorems for some epidemic processes. Advances in Applied Probability 12(2):319–349. doi:10.2307/1426600
Distributed computing
Rumor mongering with feedback loss of interest
Population genetics
no counterpart
Epidemiology
Daley–Kendall and Maki–Thompson rumour models
Chemistry (CRN)
Daley–Kendall: $X + Y \to 2Y$, $2Y \to 2Z$, $Y + Z \to 2Z$
Statistical physics
no counterpart
Social sciences
no counterpart
Details, conditions and references
Relation
Same continuous-time chain
Same mean-field map
The Daley–Kendall model is the stochastic mass-action chain of its network, and the continuous-time Maki–Thompson model that of its own. Demers et al.'s feedback–coin rule with $k = 1$ is Maki–Thompson's rule (the calling spreader stops after reaching a site that already knows), and their mean-field residue $s = e^{-2(1-s)}$ has the root $0.2032$, the limit of both rumour models. [7, 6, 5, 1]
Conditions
- Well mixed.
- Demers et al. do not cite Daley–Kendall or Maki–Thompson; the identification of their rule with Maki–Thompson's is ours, and so is the writing of both models as reaction networks, from their transition rates (as tabulated by Lebensztayn and Rodriguez). The original Maki–Thompson model is in discrete time; the continuous-time chain is its modern restatement.
Distributed computing
Rumor mongering with feedback loss of interest [1]
Demers et al.'s rumor mongering: "When an active individual makes an unnecessary phone call (the recipient already knows the rumor), then with probability $1/k$ the active individual loses interest in sharing the rumor"; in their mean-field equations the residue (sites never reached) solves $s = e^{-(k+1)(1-s)}$, about 20% for $k = 1$ (their simulation on 1000 sites, in cycles, gives 18%).
Population genetics and evolutionary biology
No counterpart.
Epidemiology
Daley–Kendall and Maki–Thompson rumour models [2, 3, 4, 5]
Ignorants, spreaders and stiflers: a spreader meeting an ignorant makes it a spreader, a spreader meeting a stifler becomes a stifler, and when two spreaders meet both become stiflers (Daley–Kendall) or only the initiator does (Maki–Thompson). The fraction never hearing the rumour tends to $0.203$.
Chemistry (chemical reaction networks)
Daley–Kendall: $X + Y \to 2Y$, $2Y \to 2Z$, $Y + Z \to 2Z$ [6]
Common rate constant (propensities $XY$, $\binom{Y}{2}$, $YZ$); Maki–Thompson replaces $2Y \to 2Z$ by $2Y \to Y + Z$ with propensity $Y(Y-1)$.
Statistical physics and interacting particle systems
No counterpart found.
Social sciences
No separate counterpart found: the rumour models of the epidemiology column are themselves the classical models of this social phenomenon.
In Leanamics
Lean: roadmap Not formalized; the Daley–Kendall limit is listed as remaining work of CRN-2, whose law of large numbers covers the SIR network.
References
- A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, D. Terry (1987). Epidemic algorithms for replicated database maintenance. PODC 1987, 1–12. doi:10.1145/41840.41841
- D. J. Daley, D. G. Kendall (1964). Epidemics and rumours. Nature 204:1118. doi:10.1038/2041118a0
- D. J. Daley, D. G. Kendall (1965). Stochastic rumours. IMA Journal of Applied Mathematics 1(1):42–55. doi:10.1093/imamat/1.1.42
- D. P. Maki, M. Thompson (1973). Mathematical Models and Applications, with Emphasis on the Social, Life, and Management Sciences. Prentice-Hall. ISBN 978-0-13-561670-3
- A. Sudbury (1985). The proportion of the population never hearing a rumour. Journal of Applied Probability 22(2):443–446. doi:10.2307/3213787
- E. Lebensztayn, P. M. Rodriguez (2025). The maximum proportion of spreaders in stochastic rumor models. arXiv preprint. arXiv:2507.07914
- E. Lebensztayn, F. P. Machado, P. M. Rodríguez (2011). Limit theorems for a general stochastic rumour model. SIAM Journal on Applied Mathematics 71(4):1476–1486. doi:10.1137/100819588
Distributed computing
Coalescing-branching random walk (COBRA)
Population genetics
no counterpart
Epidemiology
BIPS (biased infection with persistent source)
Chemistry (CRN)
no counterpart
Statistical physics
no counterpart
Social sciences
no counterpart
Details, conditions and references
Relation
Duality
$\Pr(\text{COBRA from } C \text{ has not visited } v \text{ by time } t) = \Pr(C \cap A_t = \emptyset \mid A_0 = \{v\})$ for every set $C$, vertex $v$ and time $t$, where $A_t$ is BIPS with source $v$ (Cooper, Radzik and Rivera, Theorem 4, proved by induction on $t$); pathwise, the two events coincide along reversed rounds (the form proved in the library). [3]
Conditions
- Same $k$ and the same neighbour sampling in both processes.
- The source states it for connected regular graphs; neither hypothesis is needed, only a neighbour for every vertex to sample.
- The identity is about the BIPS state at time $t$; BIPS infection is not monotone, so it does not equate the COBRA hitting time with a first infection time of BIPS.
Distributed computing
Coalescing-branching random walk (COBRA) [1, 2, 3]
Synchronous: every vertex holding the token sends it to $k$ neighbours drawn uniformly with replacement; tokens arriving at the same vertex coalesce.
Population genetics and evolutionary biology
No counterpart.
Epidemiology
BIPS (biased infection with persistent source) [3]
"A discrete epidemic process of the SIS (Susceptible-Infected-Susceptible) type": the source $v$ stays infected, and every other vertex samples $k$ neighbours and is infected in the next round iff one of them is infected now.
Chemistry (chemical reaction networks)
No counterpart: Synchronous rounds.
Statistical physics and interacting particle systems
No exact counterpart: Cooper, Radzik and Rivera call COBRA "a discrete version of the contact process", the continuous-time SIS model of interacting particle systems, but "a contact process can die out, whereas the COBRA one does not", and no identity between the two is stated.
Social sciences
No counterpart found.
In Leanamics
Lean: proved The duality on every finite graph without isolated vertices and for every $k$, pathwise and by time reversal of i.i.d. rounds (EPI-4). As a duality of kernels (Dynamics.Kernel.Dual), COBRA stopped when it visits $v$ and BIPS with source $v$, on the sets that contain $v$, are dual with respect to $1\{C \cap A = \emptyset\}$ (Epidemics.cobra_bips_dual), which gives the theorem again by the Markov property, as in the source's induction on $t$. The COBRA cover time and the BIPS infection time on regular expanders.
References
- C. Dutta, G. Pandurangan, R. Rajaraman, S. Roche (2013). Coalescing-branching random walks on graphs. SPAA 2013, 176–185. doi:10.1145/2486159.2486197
- C. Dutta, G. Pandurangan, R. Rajaraman, S. Roche (2015). Coalescing-branching random walks on graphs. ACM Transactions on Parallel Computing 2(3). doi:10.1145/2817830
- C. Cooper, T. Radzik, N. Rivera (2016). The coalescing-branching random walk on expanders and the dual epidemic process. PODC 2016, 461–467. doi:10.1145/2933057.2933119 arXiv:1602.05768
Majority dynamics: 3-Majority and plurality consensus
Every round, each node adopts the majority colour among three random nodes. Formalized: consensus
from a 3/5 majority in $O(\log n)$ rounds (proof); plurality
consensus with $k$ colours from a bias of order $\sqrt{\lambda n \log n}$ (Becchetti et al., SPAA
2014) and its lower bounds; with two colours,
consensus from any start, even a balanced one (details); with
$k \le n^{1/3-\varepsilon}$ colours, consensus in $O((k^2 \sqrt{\log n} + k \log n)(k + \log n))$ rounds (Becchetti et al., SODA
2016); and, with any number of colours, consensus from any start
within $O(n^{3/4} \log^{7/8} n)$ rounds (Berenbrink et al., PODC 2017).
Blueprint · PDF · Dependency graph · API docs · Source
Every round, each node adopts the median of its own value and two random values; with two values
this is 2-Choices. Formalized: consensus within $O(\log n)$ rounds from any configuration and
almost stable consensus against an adaptive adversary (Doerr et al., SPAA 2011);
two-sample voting on expanders (Cooper, Elsässer and Radzik, ICALP 2014), also from a
small initial imbalance on any regular graph (details);
and, for 2-Choices with any number of colours, plurality consensus (Elsässer et al.)
and an $\Omega(n/\log n)$ lower bound (Berenbrink et al., PODC 2017).
Blueprint · PDF · Dependency graph · API docs · Source
Undecided-state dynamics
A node that sees the other opinion becomes undecided; an undecided node adopts the opinion it
sees. Formalized: majority consensus from a bias of order $\sqrt{n \log n}$ within $O(\log n)$
rounds (Clementi et al., MFCS 2018); plurality consensus with $k$
colours (Becchetti et al., SODA 2015) and its lower bound; and the sequential
approximate-majority protocol (Angluin, Aspnes and Eisenstat, 2008).
Blueprint · PDF · Dependency graph · API docs · Source
Voter model
Every round, each node copies the opinion of a random neighbour. Formalized: the consensus
probabilities on connected graphs and neutral Wright–Fisher fixation (Hassin and
Peleg); consensus within $O(n^3 \log n)$ rounds on every connected graph
(details), also without laziness on
non-bipartite graphs (Hassin and Peleg); and consensus times via conductance, also on dynamic
graphs (Berenbrink et al., ICALP 2016).
Blueprint · PDF · Dependency graph · API docs · Source
The Moran process and the isothermal theorem
An individual chosen proportionally to its fitness places a copy of itself on a random neighbour.
Formalized: the isothermal theorem on regular graphs (Lieberman, Hauert and Nowak,
2005); neutral fixation of push and pull processes on every graph
(details); and exact fixation on the star, which amplifies selection
(Broom and Rychtář, 2008).
Blueprint · PDF · Dependency graph · API docs · Source
Epidemics and rumor spreading
Formalized: push, pull and push–pull rumor spreading on $K_n$ inform all nodes within $O(\log n)$
rounds (push, pull and push–pull), with
sharp upper bounds from a general analysis (Doerr and Kostrygin, ICALP 2017) and the matching lower bounds;
Reed–Frost epidemics as percolation, with small outbreaks below the threshold, also on small-world
networks (Becchetti et al.), and a giant component above it
(Krivelevich and Sudakov, 2013); the COBRA–BIPS duality
(Cooper, Radzik and Rivera, PODC 2016) and the COBRA cover time
$O(\log n/(1-\lambda)^3)$ on regular expanders (details); and the SIR equations
(Kermack–McKendrick) with their law of large numbers
(Kurtz).
Blueprint · PDF · Dependency graph · API docs · Source
Chemical reaction networks and population protocols
Formalized: the stochastic mass-action kinetics of a bimolecular network has the same jump
chain as the population protocol on the same reactions, and population protocols stably compute every
threshold and remainder predicate and their Boolean combinations (Angluin et al.,
2006); on every connected interaction graph, 4 states suffice and are needed
for exact majority, and approximate majority from a random placement favours the majority
(Mertzios et al., ICALP 2014); deterministic protocols with O(log C)-bit states find
the absolute majority among C colours, if any, and mark the agents of the plurality colour (Gąsieniec et al.,
OPODIS 2016).
Blueprint · PDF · Dependency graph · API docs · Source
Averaging dynamics
Every round, each node replaces its value by the average of its neighbours’ values. Formalized:
convergence and its spectral rate (after Lovász), sequential averaging
(details), and community detection by averaging
(Becchetti et al., SODA 2017; ESA
2018).
Blueprint · PDF · Dependency graph · API docs · Source
Shared finite dynamics library
Finite probability (expectations that agree with Mathlib’s Finset.expect, kernels, absorption)
and the tools the dynamics share: Chernoff, Hoeffding and Bernstein bounds, optional stopping,
drift theorems and a hitting-time lemma.
Blueprint · PDF · Dependency graph · API docs · Source
How to cite
If you use Leanamics, please cite it. Every release is archived on Zenodo
with its own DOI, and 10.5281/zenodo.23265329 always resolves to the latest release; the
metadata are in
CITATION.cff. Please cite
the version you used (here v0.2.0):
@software{leanamics,
author = {Kumar, Aakash and Bucarelli, Maria Sofia and D'Archivio, Niccol{\`o} and Natale, Emanuele},
title = {Leanamics: {Lean} 4 formalizations of opinion dynamics and related distributed processes},
year = {2026},
version = {0.2.0},
doi = {10.5281/zenodo.23334909},
url = {https://github.com/formal-dynamics/leanamics}
}
Each project is a separate Lean package (its own lakefile.toml and toolchain) living in its own
subdirectory of the repository. The shared dynamics/ package is used by every other package:
plurality/ (libraries Plurality and ThreeMajority), median/, undecided/, voter/,
moran/, epidemics/ (libraries Epidemics and RumorSpread), crn/ and averaging/. This
page is the shared landing page linking to each development; see each subdirectory’s own
README.md for build instructions.