Finite Weighted Dynamics
1 Uniform expectations
For a finite type \(A\), set \(\operatorname {avg}(f)=\sum _{a\in A}f(a)/|A|\). When \(A\) is empty this is zero, following Lean’s division convention.
Uniform averages over a finite (dependent) product factor over its coordinates, each coordinate is uniform on its factor, disjoint blocks of coordinates are independent, and averages are invariant under bijections of the sample space.
The recursively defined expectation over \(T\) independent draws equals the uniform average over functions \(\{ 0,\ldots ,T-1\} \to A\).
Separate the first coordinate using the finite-function/product equivalence, then induct on \(T\). The empty sample space is handled separately.
Iterated uniform averages over two finite sets commute; in particular an outer average commutes with the trajectory expectation \(\mathrm{expList}\), which also commutes with finite sums and vanishes on the zero functional.
Exchange the order of finite summation; for \(\mathrm{expList}\), induct on \(T\).
The expectation over \(T\) draws only evaluates its functional on lists of length \(T\). For \(k\le T\), a functional of the first \(k\) draws has the same expectation over \(T\) draws as over \(k\) draws; for \(k{\lt}T\), the draw after them is a fresh uniform sample.
Induction on \(T\); split \(T=k+m\) and average out the last \(m\) draws.
2 Weighted distributions and kernels
A distribution consists of nonnegative real weights \(p_a\) with \(\sum _a p_a=1\). Its expectation is \(\sum _a p_a f(a)\), and an event probability is the expectation of its indicator. Such a distribution cannot exist on an empty type.
On a nonempty finite type the normalized uniform distribution agrees with the existing finite average.
Independent coordinates have product weights. Expectations of product observables factor, and transporting weights along a function commutes with expectation.
Distribute products over finite sums; for pushforward interchange the two sums and evaluate each fiber indicator.
Under an independent product, resampling one coordinate does not change the law, so the expectation can be conditioned on the value of one coordinate. Two distinct coordinates are independent, and so are functions of disjoint sets of coordinates; centred coordinate functions have additive second and third moments. If \(x\) and \(y\) are independent families, the family \((\varphi _i(x_i,y_i))_i\) is independent, with the coordinatewise laws.
Resampling: the bijection \((x,a)\mapsto (x[i\mapsto a],x_i)\) moves the weight of coordinate \(i\). Moments: expand the power of the sum and factor the mixed terms. Combination: expand the product weights of \((\varphi _i(x_i,y_i))_i\) as sums over the preimages.
The finite average is Mathlib’s finite expectation, \(\operatorname {avg}(f)=\mathbb {E}_{a\in A}f(a)\) (Finset.expect); both vanish on an empty type. On a nonempty type the independent product of uniform distributions on \(A\), indexed by a finite set \(I\), is the uniform distribution on \(A^I\). Hence \(\mathrm{expList}\) over \(T\) rounds is the expectation of \(F\) over \(T\) i.i.d. uniform draws, both as Mathlib’s \(\mathbb {E}_{\omega \colon \{ 0,\ldots ,T-1\} \to A}\) and under the product distribution.
Mathlib’s finite expectation is a sum divided by a cardinality. Every point of \(A^I\) has product weight \(|A|^{-|I|}=|A^I|^{-1}\). Combine both with Lemma 3.
A distribution \(p\) on a finite type is a probability mass function (Mathlib’s PMF); the uniform distribution, point masses and pushforward are PMF.uniformOfFintype, PMF.pure and PMF.map. Equip the type with a \(\sigma \)-algebra containing the singletons (hence every set). Under the induced measure \(\mu _p\), the expectation of \(f\) is \(\int f\, d\mu _p\) and the probability of an event \(S\) is \(\mu _p(S)\). The measure of an independent product is the product measure \(\bigotimes _i\mu _{p_i}\), so the coordinates \(x\mapsto Y_i(x_i)\) are independent random variables in Mathlib’s sense (iIndepFun).
All integrals are finite sums of weights. Two measures on a finite type agree when they agree on singletons, and a singleton of the product space has product weight on both sides; Mathlib’s iIndepFun_pi gives independence under the product measure.
A finite kernel assigns a distribution to every state. Its operator iterates compute expectations at finite times; trajectory functionals additionally record the history.
The matrix \(P_{ab}=K(a)(b)\) of a kernel is row stochastic, the transition operator is \(f\mapsto Pf\) and the expectation after \(n\) steps is \(P^nf\).
Unfold the expectation as a sum; induction on \(n\).
Ignoring history in a trajectory expectation recovers the iterated transition operator.
3 Stationarity and absorption
Every stochastic kernel on a nonempty finite type has a distribution \(p\) with \(pK=p\).
Average the first \(n+1\) evolved distributions. The stationarity defect of this Cesàro average is \((p_{n+1}-p_0)/(n+1)\), which tends to zero coordinatewise. Compactness of the finite probability simplex gives a convergent subsequence; continuity of finite sums implies that its limit is stationary.
Let \(f\) be a zero-one survival indicator with \(Kf\le f\). Suppose for each state \(a\) there is \(n_a\) with \((K^{n_a}f)(a){\lt}1\). There are \(m{\gt}0\) and \(0\le q{\lt}1\) such that \(K^m f\le qf\).
Take one plus the maximum of the finitely many access times. Antitonicity of survival probabilities puts every state below one at that time. Their finite maximum supplies \(q\). At states with \(f=0\), absorption keeps the expectation zero.
Let \(f\le 1\). If \(t_0\) is reachable from \(s\) along transitions \(a\to b\) with \(K(a,b){\gt}0\) and \(f(t_0)=0\), then \((K^n f)(s){\lt}1\) for some \(n\).
Induct on the chain. If \(K(s,t){\gt}0\) and \((K^n f)(t){\lt}1\), then \((K^{n+1}f)(s)\) is an average of values at most one with weight \(K(s,t){\gt}0\) on a value below one.
Under these hypotheses, \(K^{nm}f\le q^n f\), and \(K^t f(a)\to 0\) for every state \(a\).
Induct over blocks using positivity and linearity. The geometric bound tends to zero. For arbitrary \(t\), compare with \(m\lfloor t/m\rfloor \) by antitonicity.
Let \(\varphi \) equal \(\varphi _A\) on an event \(A\) and \(\varphi _B\) on an event \(B\), and let \(S\) be the event of lying in neither. If \(\mathbb {E}_{x_0}\varphi (X_T)=\varphi (x_0)\) and \(m\le \varphi -\varphi _B\le M\) on \(S\), then \(\varphi (x_0)-\varphi _B-(\varphi _A-\varphi _B)\Pr _{x_0}(X_T\in A)\) lies between \(m\Pr _{x_0}(X_T\in S)\) and \(M\Pr _{x_0}(X_T\in S)\). Hence, if \(\varphi _A\ne \varphi _B\), the conservation law holds for every \(T\) and \(\Pr _{x_0}(X_T\in S)\to 0\), then \(\Pr _{x_0}(X_T\in A)\to (\varphi (x_0)-\varphi _B)/(\varphi _A-\varphi _B)\); if moreover \(A\) is absorbing, this is the supremum of the finite-time probabilities.
Pointwise, \(\varphi -\varphi _B=(\varphi _A-\varphi _B)1_A+(\varphi -\varphi _B)1_S\) (on \(A\cap B\) both sides vanish). Take expectations at time \(T\) and bound the last term by monotonicity. For the limit, take \(M=-m=\sum _a|\varphi (a)-\varphi _B|\) and squeeze. If \(A\) is absorbing, the finite-time probabilities increase, so their limit is their supremum.
Let \(K\) be a kernel on configurations \(V\to \{ 0,1\} \) for which the all-one configuration \(\mathbf1\) is absorbing and the non-consensus probability tends to zero from \(s\). If \(K\varphi =\varphi \) and \(\varphi (\mathbf1)\ne \varphi (\mathbf0)\), the probability of fixation in \(\mathbf1\) from \(s\) is \((\varphi (s)-\varphi (\mathbf0))/(\varphi (\mathbf1)-\varphi (\mathbf0))\). For instance, a harmonic \(q^{k}\), with \(k\) the number of ones out of \(n\), gives \((1-q^k)/(1-q^n)\). Affine images \(u\varphi +v\) of harmonic observables are harmonic.
Apply the previous theorem with \(A=\{ \mathbf1\} \), \(B=\{ \mathbf0\} \); the event of lying in neither is non-consensus. Affine images are harmonic by linearity of expectation.
4 Rounds, concentration and phases
A deterministic update \(\mathrm{step}\colon S\times R\to S\) driven by a uniform round \(r\in R\) defines the kernel \(K(s)=\mathrm{law}(\mathrm{step}(s,r))\). Its \(T\)-step expectations are expectations over \(T\) i.i.d. uniform rounds.
Induction on \(T\), unfolding one round of \(\mathrm{expList}\).
For every functional \(F\) of \(T\) i.i.d. uniform rounds, \(\mathbb {E}F(r_T,\dots ,r_1)=\mathbb {E}F(r_1,\dots ,r_T)\). In particular the \(T\)-step expectations of a round-based process are also obtained by applying the rounds last to first.
Write both sides as uniform averages over \(\mathrm{Fin}\, T\to R\) and reindex by the involution \(i\mapsto T-1-i\).
Let \(X=\sum _{i{\lt}n}Y_i(\omega _i)\) with independent uniform coordinates. If each \(Y_i\) is \(\{ 0,1\} \)-valued, \(\Pr (X\ge \mathbb {E}X+\lambda )\le e^{-2\lambda ^2/n}\). If \(Y_i-\mathbb {E}Y_i\le b\) and \(\sum _i\mathrm{Var}\, Y_i\le \sigma ^2\), then \(\Pr (X\ge \mathbb {E}X+\lambda )\le \exp \bigl(-\lambda ^2/(2\sigma ^2(1+b\lambda /(3\sigma ^2)))\bigr)\).
Markov’s inequality applied to \(e^{tX}\), which factors over the coordinates. Hoeffding’s lemma bounds each Bernoulli factor; for Bernstein, \(e^y\le 1+y+y^2/(2(1-u/3))\) for \(y\le u{\lt}3\) bounds each factor, and \(t\) is chosen as \(\lambda /(\sigma ^2+b\lambda /3)\).
Let \(X=\sum _{i\in I}Y_i(x_i)\) under the independent product of distributions \(p_i\), where \(Y_i\) takes values in \([a_i,b_i]\). Then \(\Pr (X\ge \sum _i\mathbb {E}_{p_i}Y_i+\lambda )\le \exp \bigl(-2\lambda ^2/\sum _i(b_i-a_i)^2\bigr)\) for \(\lambda \ge 0\). The case of uniform \(p_i\) and \(\{ 0,1\} \)-valued \(Y_i\) is the Hoeffding bound of Theorem 23.
Transport the statement to the induced measure by Lemma 11. Each centred coordinate is sub-Gaussian with parameter \((b_i-a_i)^2/4\) by Mathlib’s Hoeffding lemma, and the coordinates are independent, so Mathlib’s Hoeffding inequality for sums of independent sub-Gaussian variables applies.
Let \(X=\sum _iX_i\) be a sum of independent \(\{ 0,1\} \)-valued trials with \(\Pr (X_i=1)=p_i\), and let \(\mu _L\le \mu =\sum _ip_i\le \mu _H\). For \(\delta {\gt}0\),
and for \(0{\lt}\delta {\lt}1\),
The trials are \(\{ 0,1\} \)-valued observables of the coordinates of an independent product of distributions, independent biased coins (counting the heads in any subset), or the coordinates of one uniform round (Mitzenmacher–Upfal, Probability and Computing, Theorems 4.4 and 4.5 with Exercise 4.7). For identical Bernoulli\((p)\) coins, conditioning on one coin gives \(\Pr (E)=p\, \Pr (E\mid \text{heads})+(1-p)\Pr (E\mid \text{tails})\), and the binomial tail \(T(m,k)=\Pr (\)
at least \(\)k\( heads among \)m\( coins\))\(\) satisfies \(T(m+1,k+1)=p\, T(m,k)+(1-p)\, T(m,k+1)\).
Markov’s inequality applied to \(e^{tX}\), which factors over the coordinates; each factor is \(1+p_i(e^t-1)\le e^{p_i(e^t-1)}\), so \(\mathbb {E}e^{tX}\le e^{\mu _H(e^t-1)}\) for \(t\ge 0\) and \(\mathbb {E}e^{tX}\le e^{\mu _L(e^t-1)}\) for \(t\le 0\). Take \(t=\log (1+\delta )\), respectively \(t=\log (1-\delta )\). The closed forms follow from \(\log (1+\delta )\ge 2\delta /(2+\delta )\) (the first term of the series of \(\log \frac{1+x}{1-x}\) at \(x=\delta /(2+\delta )\)) and \((1-\delta )\log (1-\delta )\ge -\delta +\delta ^2/2\). The conditioning formula sums over the value of the coin (independence of the coordinates), and the recursion of \(T\) is the case of the first coin.
Let \(X=\sum _{i{\lt}n}Y_i(\omega _i)\) with independent uniform \(\{ 0,1\} \)-valued coordinates and \(\mu =\mathbb {E}X\). Then \(\Pr (X\le \mathbb {E}X-\lambda )\le e^{-2\lambda ^2/n}\), and a \(\{ 0,1\} \) coordinate has variance at most its mean. For every real \(t\), \(\mathbb {E}e^{tX}\le \exp (\mu (e^t-1))\); hence \(\Pr (X\ge k)\le \exp (\mu (e^t-1)-tk)\) for \(t\ge 0\) and \(\Pr (X\le k)\le \exp (\mu (e^t-1)-tk)\) for \(t\le 0\). If \(\mathbb {E}X\le \mu \le k\) with \(\mu {\gt}0\), then \(\Pr (X\ge k)\le \exp (k-\mu -k\log (k/\mu ))\); if \(0{\lt}k\le \mu \le \mathbb {E}X\), then \(\Pr (X\le k)\le \exp (k-\mu -k\log (k/\mu ))\). Finally \(\Pr (X\le (1-\delta )\mathbb {E}X)\le \exp (-\delta ^2\mathbb {E}X/2)\) for \(0\le \delta {\lt}1\). Bernstein’s bound also holds for the lower tail \(\Pr (X\le \mathbb {E}X-\lambda )\) (when \(\mathbb {E}Y_i-Y_i\le b\)); for \(\{ 0,1\} \)-valued coordinates and \(\ell {\gt}0\), each of \(\Pr (X\ge \mu +\sqrt{3\ell (\mu +2\ell )})\) and \(\Pr (X\le \mu -\sqrt{3\ell (\mu +2\ell )})\) is at most \(e^{-\ell }\). For independent (not necessarily uniform) \(\{ 0,1\} \) trials with \(\mathbb {E}X\le (1-\varepsilon )c\), \(0\le \varepsilon {\lt}1\) and \(c\ge 0\), \(\Pr (X\ge k)\le \exp (c(\varepsilon -\varepsilon ^2/2)-\varepsilon k)\) for every \(k\).
The lower Hoeffding tail is the upper one for \(1-Y_i\). For the MGF bound, \(e^{tY}=1+(e^t-1)Y\) on \(\{ 0,1\} \) and \(1+y\le e^y\), factor by factor; Markov’s inequality applied to \(e^{tX}\) gives the tails, and \(t=\log (k/\mu )\) the closed forms (the exponent is monotone in \(\mu \) in the right direction). The last bound is the lower bound of Theorem 25 with \(\mu _L=\mathbb {E}X\) (trivial for \(\delta =0\)). The lower Bernstein tail is the upper one for \(-Y_i\); the \(\{ 0,1\} \) forms take \(b=1\), \(\sigma ^2=\mu +2\ell \) and \(\lambda =\sqrt{3\ell \sigma ^2}\). The last bound is Markov’s inequality on \(e^{\varepsilon X}\) with \((1-\varepsilon )e^{\varepsilon }\le 1-\varepsilon ^2/2\).
Let \(S=\sum _{i{\lt}n}f_i(\omega _i)\) with independent uniform coordinates, each \(f_i\) centered and bounded by \(1\) in absolute value, and \(\sigma ^2=\sum _i\mathbb {E}f_i^2\). Then \(\mathbb {E}S^2=\sigma ^2\) and \(\mathbb {E}S^4\le \sigma ^2+3\sigma ^4\). If \(\mathbb {E}X\ge 0\) and \(0\le \theta \le 1\), then \((1-\theta )^2(\mathbb {E}X)^2\le \mathbb {E}X^2\, \Pr (X{\gt}\theta \, \mathbb {E}X)\) (one-sided Paley–Zygmund). If \(\mathbb {E}Z^2=s{\gt}0\) and \(\mathbb {E}Z^4\le 4s^2\), then \(\Pr (s\le 4Z^2)\ge 9/64\) (two-sided Paley–Zygmund); hence \(\Pr (\sigma ^2\le 4S^2)\ge 9/64\) whenever \(\sigma ^2\ge 1\), in particular for centered \(\{ 0,1\} \)-valued coordinates, whose variance is \(p(1-p)\). For \(\{ 0,1\} \)-valued coordinates and every real \(t\), \(\mathbb {E}e^{tS}\le \exp (t\, \mathbb {E}S+nt^2/8)\). Finally, a sum \(X\) of pairwise uncorrelated \(\{ 0,1\} \)-valued variables with mean \(\mu \) has \(\mathbb {E}X^2\le \mu +\mu ^2\).
The moments by induction on \(n\), splitting off the first coordinate, which is independent of the others. For Paley–Zygmund, \(X\le \theta \, \mathbb {E}X+X\, 1_A\) with \(A=\{ X{\gt}\theta \, \mathbb {E}X\} \) pointwise, and Cauchy–Schwarz (Mathlib’s, through \(\operatorname {avg}=\mathbb {E}\)) gives \((\mathbb {E}[X 1_A])^2\le \mathbb {E}X^2\, \Pr (A)\); the two-sided form is the one-sided one for \(X=Z^2\) and \(\theta =1/4\). The exponential moment factors over the coordinates, and Hoeffding’s lemma bounds each factor. For the last bound, expand \(X^2\): the diagonal terms are \(\mathbb {E}X_i^2=\mathbb {E}X_i\) and the others \(\mathbb {E}X_i\, \mathbb {E}X_j\).
Probability is monotone in the event. An observable \(f\le 1\) with \(f(b){\lt}1\) at a point of positive weight has expectation \({\lt}1\). Markov’s inequality \(\Pr (X\ge c)\le \mathbb {E}X/c\) for \(X\ge 0\), \(c{\gt}0\); in particular \(\Pr (\sum _iY_i(\omega _i)\ge 1)\le \sum _i\mathbb {E}Y_i\) for nonnegative coordinates. One round of \(\mathrm{step}\) lands in an event with probability at least \(1-\mathbb {E}[\mathrm{bad}]\) when \(\mathrm{bad}\ge 0\) is at least \(1\) on every miss. If \(f\le Kf\), then \(n\mapsto K^nf(a)\) is nondecreasing; in particular the occupation probability of an absorbing event is nondecreasing in time. Finally \(e^{-2\log n}=1/n^2\) for \(n\ge 1\), \(e^{-3\log n}=1/n^3\) for \(n{\gt}0\), and \(\log n{\gt}0\) forces \(n\ge 1\).
Pointwise comparisons of indicators, integrated by monotonicity of the expectation; for the kernel statements, induction on time with \(K^{n+1}f=K^n(Kf)\).
For \(a,b\ge 0\): \(\lceil a\rceil +\lceil b\rceil \le \lceil c\rceil \) if \(a+b+2\le c\), and \(k\lceil a\rceil \le \lceil b\rceil \) if \(k(a+1)\le b\); \(\lceil ay\rceil \le \lceil by\rceil \) if \(0\le a\le b\). For \(w\ge 1\) and \(q{\gt}1\), \(w\le q^{\lceil \log w/\log q\rceil }\); growth by a factor \(q\) from \(\Delta {\gt}0\) passes \(N\ge \Delta \) within \(\log (N/\Delta )/\log q+2\) steps, and \(2^{2^T}\ge N\ge 2\) for some \(T\le 2\log \log N+3\). Moreover \(c^3\le x\) if \(3c\le \log x\); \((\log x)^3/6\le x\) and \((\log x)^4/24\le x\) if \(\log x\ge 0\); \(\varepsilon /2\le \log (1+\varepsilon )\) on \([0,1]\); and \(S/N^2\le C/N\) if \(S\le CN\), \(N{\gt}0\).
\(\lceil a\rceil {\lt}a+1\); \(w\le q^t\) iff \(\log w\le t\log q\); \(y^k/k!\le e^y\) at \(y=\log x\); and \(1-1/x\le \log x\).
Let \(A_1\supseteq \cdots \supseteq A_T\) be sets of states such that from \(A_i\) the chain stays in \(A_i\) with probability at least \(1-\varepsilon \) and, for \(i{\lt}T\), enters \(A_{i+1}\) with probability at least \(1-\nu \). From \(A_1\), after \(\ell T\) steps the chain is in \(A_T\) with probability at least \(1-T(\ell \varepsilon +\nu ^\ell )\).
Track the indicator of lying outside a set. In \(\ell \) steps the chain leaves \(A_i\) with probability at most \(\ell \varepsilon \), and misses \(A_{i+1}\) in all \(\ell \) steps with probability at most \(\nu ^\ell \). Sum over the \(T\) phases.
5 Drift and graph rounds
A family of kernels \((K_t)_{t\ge 0}\) moves the chain from time \(t\) to time \(t+1\) with \(K_t\); \(\mathrm{iterateSeq}(K,n,f)(a)\) is the expectation of \(f\) at time \(n\) from \(a\). A constant family gives the iterates of a single kernel.
Induction on \(n\).
Let \(\Psi \ge 0\), and for \(t{\lt}T\) let \(c_t\ge 0\), \(\mathbb {E}[\Psi (X_{t+1})\mid X_t=x]\le \Psi (x)-c_t/\Psi (x)\) when \(\Psi (x){\gt}0\), and \(\mathbb {E}[\Psi (X_{t+1})\mid X_t=x]=0\) when \(\Psi (x)=0\). If \(\sum _{t{\lt}T}c_t\ge 4\Psi (x_0)^2\), then \(\Pr _{x_0}(\Psi (X_T)=0)\ge 1/2\).
Let \(q=\Pr (\Psi (X_T){\gt}0)\); survival is nonincreasing, so it is at least \(q\) before \(T\). With \(\lambda =q/\Psi (x_0)\), the bound \(1/y\ge 2\lambda -\lambda ^2y\) linearizes the drift: \(\mathbb {E}\Psi (X_{t+1})\le (1+c_t\lambda ^2)\mathbb {E}\Psi (X_t) -2c_t\lambda \Pr (\Psi (X_t){\gt}0)\le \mathbb {E}\Psi (X_t)-c_t\lambda q\). (The paper uses Jensen’s inequality here; this is its optimal-\(\lambda \) form.) Summing, \(0{\lt}m q\le \mathbb {E}\Psi (X_T)\le \Psi (x_0)(1-4q^2)\) if \(q{\gt}0\), where \(m{\gt}0\) is the least positive value of \(\Psi \); hence \(q\le 1/2\).
Let \(\Psi \ge 0\) with every positive value at least \(\Psi _{\min }{\gt}0\), and \(\mathbb {E}[\Psi (X_{t+1})\mid X_t=x]\le (1-\delta _t)\Psi (x)\) for all \(x\) and \(t{\lt}T\). Then \(\Pr _{x_0}(\Psi (X_T){\gt}0)\le \prod _{t{\lt}T}(1-\delta _t)\, \Psi (x_0)/\Psi _{\min }\).
By induction \(\mathbb {E}\Psi (X_T)\le \prod _{t{\lt}T}(1-\delta _t)\Psi (x_0)\) (the factors are nonnegative unless \(\Psi \equiv 0\)); then Markov’s inequality \(\mathbf1_{\Psi {\gt}0}\le \Psi /\Psi _{\min }\).
In a round \(r\in \prod _vN(v)\) every vertex picks a neighbour. Under the uniform distribution the picks are independent and uniform: \(\mathbb {E}\prod _vf_v(r_v)=\prod _v\mathbb {E}_{u\in N(v)}f_v(u)\), and, without isolated vertices, \(\mathbb {E}g(r_v)=\mathbb {E}_{u\in N(v)}g(u)\). A uniform vertex \(v\) with a uniform round gives the sequential step “uniform vertex, uniform neighbour \(r_v\)”.
\(\sum _r\prod _vf_v(r_v)=\prod _v\sum _{u\in N(v)}f_v(u)\) and \(|\prod _vN(v)|=\prod _v\deg v\); the marginals take \(f_w=1\) for \(w\ne v\).
For a uniform dart \(d\) of \(G\), \(\mathbb {E}F(d_1,d_2)=\sum _v\sum _{u\in N(v)}F(v,u)/(2|E|)\); reversing \(d\) preserves the law, its underlying edge is a uniform edge, and its tail is \(v\) with probability \(\deg v/(2|E|)\).
Group the darts by tail (the darts with tail \(v\) are the neighbours of \(v\)) or by edge (each edge carries two darts).
A sum over the darts of \(G\) is the sum over the adjacent ordered pairs; along a walk from \(u\) to \(v\) the differences \(\psi (d_1)-\psi (d_2)\) telescope to \(\psi (u)-\psi (v)\); and over any set of distinct darts \(\sum _d(\psi (d_1)-\psi (d_2))^2\le \sum _{i\sim j}(\psi (i)-\psi (j))^2\).
Darts are the adjacent ordered pairs; induction on the walk; distinct darts are distinct ordered pairs and the summands are nonnegative.
The lazy version of a kernel \(K\) is \((I+K)/2\): it puts weight at least \(1/2\) on every self-loop, charges everything \(K\) charges, and has the same stationary distributions as \(K\). On a graph without isolated vertices the simple random walk \(D^{-1}A\) moves to a uniform neighbour, so its expectations are neighbour averages, and the lazy random walk is \((I+D^{-1}A)/2\).
On the complete graph the darts are the ordered pairs of distinct vertices, \(n(n-1)\) of them, and a sum over them is the sum over all ordered pairs minus the diagonal. A one-way protocol step on the dart \((u,v)\) updates the state of the responder \(v\) against the initiator \(u\).
A dart is an adjacent ordered pair; the complete graph has \(\binom n2\) edges, each carrying two darts.
6 Hitting times
This section formalizes Claim 2.9 of Doerr, Goldberg, Minder, Sauerwald and Scheideler, Stabilizing consensus with the power of two choices (SPAA 2011), as Theorem 41. Compared with the claim, the hypothesis \(c_4\log q\le q\) is added (the target is a possible value, which a non-asymptotic statement needs), and \(c_5\) also depends on \(c_1,c_2,c_3\) (details).
\(\mathrm{hitProb}(K,B,n)(a)=\Pr _a(\exists s\le n,\ X_s\in B)=\Pr _a(T_B\le n)\), the expectation over the first \(n\) transitions of the indicator that one of the states at the times \(0,\dots ,n\) lies in \(B\).
Let \(V\ge 0\) vanish on \(B\) and be at least \(V_{\min }{\gt}0\) off \(B\), with \(\mathbb {E}[V(X_{t+1})\mid X_t=x]\le \rho V(x)\) for \(x\notin B\). Then \(\Pr _a(T_B{\gt}t)\le \rho ^tV(a)/V_{\min }\).
In the chain stopped on entering \(B\), being outside \(B\) at time \(t\) is the event \(T_B{\gt}t\); apply Theorem 33 to the stopped chain with \(\delta =1-\rho \).
Let \(c_1{\gt}1\) and \(c_2,c_3,c_4,c_6{\gt}0\). There is \(c_5{\gt}0\) such that for every finite chain and observable \(X\in \{ 0,\dots ,q\} \) with \(c_4\log q\le q\): if from every state below the target \(\Pr [X_{t+1}\ge \min \{ c_1X_t,q\} ]\ge 1-e^{-c_2X_t}\), and \(\Pr [X_{t+1}\ge 1]\ge c_3\) when \(X_t=0\), then \(X\) reaches \(c_4\log q\) within \(c_5\log q+\log _{c_1}(c_4\log q)\) steps with probability at least \(1-q^{-c_6}\) (equivalently within \(C\log q\) steps).
The paper omits the proof. Let \(p=\min \{ c_3,1-e^{-c_2}\} \), \(\theta =1/p\) and \(\beta =c_2/2\). For a large threshold \(x_0\) take \(g(x)=1-\eta (\theta ^x-1)\) for \(x\le x_0\), with \(\eta \) chosen so that \(g(x_0)=1/2\), and \(g(x)=\tfrac 12e^{-\beta (x-x_0)}\) for \(x\ge x_0\); let \(V=g(X)\) below the target and \(V=0\) on it. Below \(x_0\) a step goes up by at least one with probability at least \(p\), and \(pg(x+1)+1-p\le \rho g(x)\) with \(\rho =1-(1-p)\eta /2\); above \(x_0\) growth by \(c_1\) fails with probability at most \(e^{-c_2x}\), and the expected potential is at most \(\tfrac 38e^{-\beta (x-x_0)}\le \rho g(x)\). Since \(V\le 1\) and \(V\ge \tfrac 12q^{-\beta c_4}\) below the target, Lemma 40 gives \(\Pr (T{\gt}t)\le 2\rho ^tq^{\beta c_4}\le q^{-c_6}\) for \(t\ge (1+\beta c_4+c_6)\log q/\log (1/\rho )\).
7 Relations between chains
The cross-field dictionary of Leanamics relates processes of different fields by a few kinds of relation. Four of them concern one step of two finite kernels and are defined here; the other kinds (the same continuous-time chain, a pathwise coupling, a large-population limit, the same deterministic recursion) are not.
Distributions with the same weights, or with the same expectations, are equal. The law \(pK^t\) at time \(t\) satisfies \(\mathbb {E}_{pK^t}[g]=\mathbb {E}_p[K^tg]\).
Take the indicator of a point as observable; induction on \(t\), exchanging two finite sums.
A kernel \(K\) on \(\alpha \) lumps to a kernel \(L\) on \(\beta \) along \(f:\alpha \to \beta \) if \(K(x)\circ f^{-1}=L(f(x))\) for every \(x\), equivalently \(\mathbb {E}_x[g(f(X_1))]=\mathbb {E}_{f(x)}[g(Y_1)]\) for every observable \(g\).
If \(K\) lumps to \(L\) along \(f\), then \((pK^t)\circ f^{-1}=(p\circ f^{-1})L^t\) for every initial law \(p\) and time \(t\), and the expectation of every functional of the trajectory \(f(X_0),\dots ,f(X_t)\) is that of \(Y_0,\dots ,Y_t\) from \(f(x)\). In particular the probabilities of events at time \(t\) and the hitting probabilities agree. Lumpings compose.
Induction on \(t\): one step of \(K\) seen through \(f\) is one step of \(L\).
The jump chain \(J\) of \(K\) is the step conditioned on moving: \(J(x,y)=K(x,y)/(1-K(x,x))\) for \(y\ne x\) and \(J(x,x)=0\), except that a state with \(K(x,x)=1\) stays absorbing. Two kernels have the same jump chain if their jump chains are equal.
\(Kg(x)=K(x,x)g(x)+(1-K(x,x))Jg(x)\), so \(g\) is harmonic at \(x\) for \(K\) iff it is for \(J\). If the rows of \(K\) and \(L\) are proportional off the diagonal with positive factors, they have the same jump chain; a lazy kernel \((I+K)/2\) has the jump chain of \(K\), and \(J\) is its own jump chain.
Off the diagonal the weights of \(K(x)\) add up to \(1-K(x,x)\); normalize.
If \(K\) and \(L\) have the same jump chain and \(A\) is absorbing for both, then \(\sup _t\Pr ^K_x(X_t\in A)=\sup _t\Pr ^L_x(Y_t\in A)\) for every \(x\).
The absorption probability \(h_K\) is the increasing limit of \(K^t1_A\), so \(Kh_K=h_K\) (a finite sum commutes with the limit); by the previous lemma \(Lh_K=h_K\). A nonnegative \(L\)-harmonic function that is at least \(1\) on \(A\) bounds \(L^t1_A\) for every \(t\), by induction; hence \(h_L\le h_K\), and symmetrically.
Kernels \(K\) on \(\alpha \) and \(L\) on \(\beta \) are dual with respect to \(H:\alpha \times \beta \to \mathbb R\) if \(\mathbb {E}_x[H(X_1,y)]=\mathbb {E}_y[H(x,Y_1)]\) for all \(x\) and \(y\).
If \(K\) and \(L\) are dual with respect to \(H\), then \(\mathbb {E}_x[H(X_t,y)]=\mathbb {E}_y[H(x,Y_t)]\) for every \(t\).
Induction on \(t\): condition on the first step of \(K\), apply the induction hypothesis, exchange the two finite expectations and apply the one-step duality inside.
The observables \(\varphi _i\) of \(K\) have mean-field map \(F\) if \(\mathbb {E}_x[\varphi (X_1)]=F(\varphi (x))\) for every \(x\). A lumping transfers a mean-field map, and with \(F\) the identity every \(\varphi _i\) keeps its expectation at all times.
The binomial law on \(\{ 0,\dots ,n\} \) has weights \(\binom nk p^k(1-p)^{n-k}\), those of Mathlib’s binomial distribution. The number of heads of independent Bernoulli(\(p\)) coins indexed by a set of size \(n\) has this law, so its mean is \(np\). The indicator of an event is a Bernoulli coin with the probability of the event, and an independent product transported coordinatewise is the product of the transported coordinates.
A configuration with \(k\) heads has weight \(p^k(1-p)^{n-k}\), and \(\binom nk\) configurations have \(k\) heads (they correspond to the subsets of size \(k\)); the total mass is \((p+1-p)^n\). The number of heads is the sum of the \(n\) indicators, each of mean \(p\).
The majority map is \(m(p)=3p^2-2p^3\). Conformist transmission (Boyd and Richerson, Eq. 7.1) is the recursion \(p'=p+Dp(1-p)(2p-1)\): a naive individual whose three models include \(j\) holders of a variant acquires it with probability \(0\), \(\frac13-\frac D3\), \(\frac23+\frac D3\), \(1\) for \(j=0,1,2,3\). Galam’s majority rule with groups of three is the recursion \(P'=P^3+3P^2(1-P)\).
\(m(p)\) is the probability that at least two of three independent coins of bias \(p\) show heads. The conformist table adopts the majority of the three models with probability \(D\) and otherwise copies one of them, drawn uniformly; if the three models are independent and each holds the variant with probability \(p\), the variant is acquired with probability \(p+Dp(1-p)(2p-1) =(1-D)p+Dm(p)\), which is \(p\) for \(D=0\) and \(m(p)\) for \(D=1\). Galam’s map is \(m\).
The number of holders among the three models has the law \(\mathrm{Bin}(3,p)\); expand the expectations of the table and of the majority indicator.