Epidemics and Rumor Spreading
We formalize the pathwise correspondence between the Reed–Frost (Independent Cascade) epidemic and bond percolation, after Kempe, Kleinberg and Tardos: with one coin per edge, the nodes infected in round \(t\) are exactly those at distance \(t\) from the initial set in the graph of open edges. Consequently the final outbreak is the set of nodes connected to the initial set by open edges, and with i.i.d. Bernoulli\((p)\) coins the probability of eventual infection is a bond-percolation connection probability. Below the threshold, on graphs of maximum degree \(d\) with \(p(d-1)\le 1-\varepsilon \), every cluster has at most \((10/\varepsilon ^2)\log n\) vertices with probability at least \(1-1/n\) (Becchetti et al.), so a subcritical Reed–Frost epidemic stays small and dies out within \(O(\log n)\) rounds. We then formalize the supercritical phase of the Erdős–Rényi random graph \(G(n,(1+\varepsilon )/n)\) (bond percolation on \(K_n\)) by the depth-first-search argument of Krivelevich and Sudakov: with probability at least \(1-C/n\) there is a path of length \(\varepsilon ^2 n/5\) and a component of \(\varepsilon n/2\) vertices; read through the coupling, a Reed–Frost epidemic on \(K_n\) with \(R_0=pn{\gt}1\) infects \(\Omega (n)\) nodes with probability \(\Omega (1)\). The development is in the finite layer of the shared dynamics package.
We also formalize the deterministic Kermack–McKendrick SIR model: for every solution of \(s'=-\beta si\), \(i'=\beta si-\gamma i\), \(r'=\gamma i\) on \([0,\infty )\) with \(r(0)=0\), the threshold theorem (\(i\) initially increases iff \(R_0s(0){\gt}1\), with \(R_0=\beta /\gamma \)), the epidemic peak, and the final-size equation \(s_\infty =s(0)e^{-R_0(1-s_\infty )}\), following Hethcote (SIAM Review 2000, Theorem 2.1). This part uses Mathlib’s real analysis.
We also formalize an elementary proof that push, pull and push–pull on \(K_n\), with every node calling a uniformly random node among the other \(n-1\) and from one informed node, inform all nodes within \(O(\log n)\) rounds with probability at least \(1-2/n\) (library RumorSpread, Sections 10 to 19); the only concentration tool is an exponential-moment induction for adaptive Bernoulli trials.
We also formalize the upper bounds of Doerr and Kostrygin’s analysis of general rumor-spreading processes (Randomized rumor spreading revisited, ICALP 2017): the exponential growth and shrinking regimes and the total spreading time \(\log _{1+\gamma }n+\frac1\rho \ln n+O(1)\), with exponential tails. Lemma 20 of that paper needs a major correction; we prove corrected versions.
We also formalize the duality between the coalescing-branching random walk (COBRA) and the BIPS epidemic of Cooper, Radzik and Rivera (Theorem 4), pathwise and by time reversal of i.i.d. rounds, and their bounds on the COBRA cover time on regular expanders: \(O(\log n/(1-\lambda )^3)\) when \(1-\lambda \ge C_0\sqrt{\log n/n}\) (Theorems 1 and 2), and \(O(\log n)\) with branching factor \(1+\rho \) for constant \(\lambda {\lt}1\) and \(\rho {\gt}0\) (Theorem 3), with high probability and in expectation.
1 The model
This section and the three following ones (distances, pathwise layers, random coins) formalize the live-edge coupling of Kempe, Kleinberg and Tardos (KDD 2003) for the Independent Cascade model, also Theorem A.3 of Becchetti, Clementi, Denni, Pasquale, Trevisan and Ziccardi (arXiv:2103.16398).
Every edge \(e\) of a finite graph \(G\) carries a coin \(\omega (e)\in \{ \mathrm{true},\mathrm{false}\} \); the percolated graph \(G_\omega \) keeps the edges whose coin is true. In one round, a susceptible node becomes infected if it has an infected neighbour across an open edge, and every infected node recovers. Initially the set \(I_0\) is infected and nobody is recovered. We write \(d(v)\in \mathbb N\cup \{ \infty \} \) for the distance from \(I_0\) to \(v\) in \(G_\omega \).
2 Distances from a set
\(d(v)=0\) iff \(v\in I_0\); if \(u\) and \(v\) are adjacent in \(G_\omega \) then \(d(v)\le d(u)+1\); if \(d(v)=t+1\) then \(v\) has a neighbour \(u\) in \(G_\omega \) with \(d(u)=t\); \(d(v){\lt}\infty \) iff \(v\) is connected to \(I_0\) in \(G_\omega \), and then \(d(v){\lt}|V|\).
The infimum over \(I_0\) is attained; take the second-to-last vertex of a shortest walk; a shortest walk is a path.
3 Pathwise layers
For every coin assignment and every \(t\), the nodes infected in round \(t\) are those with \(d(v)=t\), and the nodes recovered by round \(t\) are those with \(d(v){\lt}t\).
Both statements together, by induction on \(t\), using Lemma 2.
Nobody is infected in round \(t\) as soon as every finite \(d(v)\) is \({\lt}t\), in particular for \(t\ge |V|\); the nodes recovered after \(|V|\) rounds are those connected to \(I_0\) in \(G_\omega \).
Immediate from Theorem 3 and \(d(v){\lt}|V|\) when finite.
4 Random coins
With independent Bernoulli\((p)\) coins, each edge is open with probability \(p\), and the probability that \(v\) is eventually infected equals the probability that \(v\) is connected to \(I_0\) by open edges.
The two events coincide for every coin assignment (Corollary 4).
The coupling is pathwise because every edge is used at most once: once its coin has been seen from an infected endpoint, that endpoint is recovered for good. This is why a single coin per edge gives the same process, in distribution, as fresh coins in every round (that distributional statement is not formalized here).
5 Subcritical percolation and small outbreaks (EPI-2)
After Becchetti, Clementi, Denni, Pasquale, Trevisan, Ziccardi (arXiv:2103.16398), Theorem 2.3 and its proof, Theorem E.1. Throughout, the degrees of \(G\) are at most \(d\), \(n = |V|\), and \(p(d-1) \le 1 - \varepsilon \) with \(0 {\lt} \varepsilon {\lt} 1\). The small-world part of the paper is formalized in the next section (EPI-6).
A few points of the paper need a minor correction, and the corrected versions are what is formalized: the Chernoff step in the proof of Theorem E.1, which does not account for the extra trial at the source (the formal bound is \(e^{\varepsilon }\exp (-\varepsilon ^2 t/2)\), still of the form \(\exp (-\Omega (\varepsilon ^2 t))\) that the theorem states), and a typo in its union bound (details), and, in the small-world part, the hypothesis of claim 2 of Theorem 2.5 and the starting set of the exploration in Algorithm 3 (details).
At least \(t\) successes among \(t(d-1)+1\) independent Bernoulli\((p)\) trials occur with probability at most \(\exp (\varepsilon - \varepsilon ^2 t/2)\).
Markov’s inequality on \(e^{\varepsilon X}\) and the bound \(\mathbb E[e^{\varepsilon X}] \le \exp (\mu (e^{\varepsilon }-1))\) for a sum of independent trials with mean \(\mu \le (1-\varepsilon )(t+1)\) (the Chernoff layer of the shared dynamics package, before optimizing the tilt: Distribution.prob_ge_le_exp), then \((1-\varepsilon )e^{\varepsilon } \le 1 - \varepsilon ^2/2\).
The component of \(s\) in \(G_p\) has more than \(t\) vertices with probability at most that of at least \(t\) successes in \(t(d-1)+1\) independent Bernoulli\((p)\) trials.
For an exploration state (discovered set \(D\), examined pairs \(X\), forced closed), induction on a budget \(m \ge \mathrm{frontier}(D, X) + (k-1)(d-1)\): conditioning on the coin of one frontier edge, a closed coin removes that edge from the frontier, and an open one adds a vertex and at most \(d-1\) new frontier edges at it while removing the examined one. This is the recursion of the binomial tail. The initial frontier of \(\{ s\} \) has at most \(d\) edges.
The component of any vertex has more than \(t\) vertices with probability at most \(\exp (\varepsilon - \varepsilon ^2 t/2)\), and with probability at least \(1 - 1/n\) every component of \(G_p\) has at most \((10/\varepsilon ^2)\log n\) vertices.
With probability at least \(1 - 1/n\), the Reed–Frost epidemic with \(R_0 = p(d-1) \le 1 - \varepsilon \) infects at most \(|I_0| (10/\varepsilon ^2)\log n\) nodes and nobody is infected in round \(\lfloor (10/\varepsilon ^2)\log n \rfloor \); and every component of \(G(n, c/n)\) with \(c \le 1 - \varepsilon \) has at most \((10/\varepsilon ^2)\log n\) vertices.
The final outbreak is the union of the components of \(I_0\), and distances inside a component are smaller than its size (Corollary 4). \(G(n, c/n)\) is bond percolation on \(K_n\), with \(d = n - 1\) and \(p(d-1) \le c\).
6 Small-world networks below the threshold (EPI-6)
This section continues Section 5. After Becchetti, Clementi, Denni, Pasquale, Trevisan, Ziccardi (arXiv:2103.16398), Definitions 1.1 and 1.2, claim 2 of Theorems 2.1, 2.2, 2.4, 2.5, and Lemma C.1. \(\mathrm{SWG}(n, q)\) is the cycle \(C_n\) together with the edges of \(G(n, q)\); \(3\text{-}\mathrm{SWG}(n)\) is the cycle together with a uniformly random perfect matching. Probabilities are over the graph and the percolation.
\(\mathrm{SWG}(n, q)\) is \(C_n \cup \mathrm{perc}(K_n, b)\) with \(b\) i.i.d. Bernoulli\((q)\), and \(3\text{-}\mathrm{SWG}(n)\) is \(C_n \cup M\) with \(M\) uniform among the perfect matchings of \(K_n\) (\(n\) even). The critical value \(p^* = (\sqrt{c^2+6c+1} - c - 1)/(2c)\) is the root of \(c p (1 + p) = 1 - p\), so that \(p {\lt} p^*\) if and only if \(c p(1+p) {\lt} 1-p\); for \(c = 1\), \(p^* = \sqrt2 - 1\). The graph \(3\text{-}\mathrm{SWG}(n)\) has maximum degree \(3\).
The percolation graph of \(\mathrm{SWG}(n, q)\) with parameter \(p\) has the law of the percolation of \(K_n\) with independent coins, of probability \(p\) on the cycle edges and \(pq\) on the other pairs.
A pair is an open edge if and only if its percolation coin is open and it is a cycle edge or an open bridge; these combined coins are independent across pairs, with the stated probabilities.
If an adaptive process reads, at each step, coordinates of an independent family not read before, and every factor \(f_h \ge 0\) satisfies \(\mathbb E[f_h(\mathrm{obs}_h)] \le 1\) for every history \(h\), then the product of the factors along the process has expectation at most \(1\).
Condition on the history: the event that the history is \(h\) depends only on the coordinates read along \(h\), which are independent of the fresh ones (principle of deferred decisions); induction on the number of steps.
Explore the cluster of \(s\) one node at a time, with independent Bernoulli\((r_e)\) coins, giving each discovered node the weight \(h_e \in [w_{\min }, w_{\max }]\) of the pair through which it was discovered. If the expected weight discovered from every node of weight \(w\) is at most \(\lambda w\), then for \(\theta \ge 0\) and \(\kappa \le 2\) with \(\theta w_{\max } \le \kappa - 1\) and \(\kappa \lambda \le 1\), the cluster of \(s\) has more than \(t\) nodes with probability at most \(\exp (-\theta ((1-\kappa \lambda ) t w_{\min } - w_{\max }))\).
The exponential of \(\theta \) times (discovered weight \(-\ \kappa \lambda \, \cdot \) processed weight) is a supermartingale, by \(1 - r + r e^x \le e^{\kappa r x}\) for \(0 \le x \le \kappa - 1 \le 1\) and Lemma 12. A cluster with more than \(t\) nodes leaves \(t\) processed and \(t + 1\) discovered nodes after \(t\) steps; Markov’s inequality concludes.
Let \(c {\gt} 0\), \(p_0 = p^* - \varepsilon {\gt} 0\) and \(\delta = 1 - p_0 - c p_0 (1 + p_0)\). For \(n \ge 2\), \(q = c/n\) and \(p \le p_0\), with probability at least \(1 - 2/n\) every component of the percolated \(\mathrm{SWG}(n, q)\) has at most \((64/\delta ^2) \log n\) nodes.
Weights \(1\) (discovered through a cycle edge: at most one undiscovered cycle neighbour) and \(1 + p_0\) (otherwise: at most two), and at most \(n\) further pairs each open with probability \(pc/n\): the expected discovered weight is at most \((1 - \delta /2)\) times the weight. Apply Theorem 13 with \(\theta = \delta /8\), \(\kappa = 1 + \delta /4\) and a union bound over the nodes.
For \(p {\lt} 1/2 - \varepsilon \), with probability at least \(1 - 1/n\) every component of the percolated \(3\text{-}\mathrm{SWG}(n)\) has at most \((10/(2\varepsilon )^2) \log n\) nodes.
Theorem 8 with \(d = 3\) and \(2\varepsilon \) in place of \(\varepsilon \).
Below the threshold (\(p {\lt} p^* - \varepsilon \) on \(\mathrm{SWG}(n, c/n)\), \(p {\lt} 1/2 - \varepsilon \) on \(3\text{-}\mathrm{SWG}(n)\)), with probability at least \(1 - C/n\) the Reed–Frost epidemic from \(I_0\) is over within \(\beta \log n\) rounds and at most \(\beta |I_0| \log n\) nodes are recovered at the end.
Deterministic consequences of the component bounds (Corollary 9).
7 The supercritical giant component
Source: M. Krivelevich and B. Sudakov, The phase transition in random graphs: a simple proof, Random Structures & Algorithms 43 (2013), arXiv:1201.6529. Throughout, \(G(n,p)\) is the percolated complete graph \((K_V)_\omega \) with i.i.d. Bernoulli\((p)\) coins, \(n=|V|\), and \(p=(1+\varepsilon )/n\) is written \(pn=1+\varepsilon \).
If an adaptive strategy queries the coins one at a time, the next coordinate being a function of the answers so far, and never queries a coordinate twice among its first \(m\) queries, then its first \(m\) answers are i.i.d. Bernoulli\((p)\).
The answers equal a list \(L\) iff the coordinates queried along \(L\), which are determined by \(L\) and distinct, take the values of \(L\): a cylinder event of probability \(\prod _k w(L_k)\).
The search of Krivelevich–Sudakov (Section 2) with the sets \(S\) (done), \(U\) (stack) and \(T\) (unvisited), stopped before each query; after \(U=T=\emptyset \) the remaining pairs are queried.
Every pair is queried at most once; all pairs between \(S\) and \(T\) have been queried negatively; \(U\) spans a path; \(|U|\le 1+\sum X_i\) and, while \(T\ne \emptyset \), \(|S\cup U|\ge \sum X_i\); the vertices of one epoch are connected; when an epoch starts, the explored set \(D\) has all its pairs with \(V\setminus D\) queried.
An invariant preserved by every move and answer; moves without query terminate because \(2|S|+|U|\le 2n\) increases.
The deterministic steps of the proofs of Theorems 1 and 2 of the paper: \(|S\cup U|{\lt}n/3\) at time \(N_0\), \(|U|\ge \ell n+1\), and the current epoch started before \(t_1\).
In each case \(|S||T|\) (or \(|D|(n-|D|)\)) would exceed the number of queries.
Among \(N_0\) i.i.d. Bernoulli\((p)\) trials, the number of successes deviates from \(N_0p\) by \(\delta N_0p\) with probability at most \(2e^{-\delta ^2N_0p/3}\) (Chernoff bounds of FND-3 instead of Chebyshev, as in the paper’s Discussion, item 1); the same holds at every time of a window.
Chernoff bounds and the union bound.
For every small enough \(\varepsilon {\gt}0\) there is \(C\) such that \(G(n,(1+\varepsilon )/n)\) contains a path with at least \(\varepsilon ^2n/5\) edges with probability at least \(1-C/n\).
Run the search for \(N_0=\lfloor \varepsilon n^2/2\rfloor \) queries; on the typical event the stack is a path of the required length.
For every small enough \(\varepsilon {\gt}0\) there is \(C\) such that \(G(n,(1+\varepsilon )/n)\) has a component with at least \(\varepsilon n/2\) vertices with probability at least \(1-C/n\); for every \(\varepsilon {\gt}0\) there are \(c{\gt}0\) and \(C\) such that it has a component with at least \(cn\) vertices with probability at least \(1-C/n\).
No epoch starts between the times \(t_1=\lfloor \eta n^2\rfloor \) and \(N_0=\lfloor \theta n^2\rfloor \), so the positive answers in between lie in one component; \(\theta =\varepsilon /2\) for the first statement, \(\theta \) small in terms of \(\varepsilon \) for the second.
On \(K_n\) with \(pn=R_0{\gt}1\), the Reed–Frost epidemic started from any single node infects at least \(cn\) nodes with probability at least \(q{\gt}0\) for \(n\ge n_0\); for \(R_0=1+\varepsilon \) with \(\varepsilon \) small, at least \(\varepsilon n/2\) nodes with probability at least \(\varepsilon /2-C/n\).
The final outbreak is the component of the initial node (Corollary 4); by symmetry of \(K_n\) this node lies in a component of size \(\ge k\) with probability at least \(k/n\) times the probability that such a component exists.
8 The Kermack–McKendrick SIR model
The SIR model of Kermack and McKendrick (1927), following Hethcote, The mathematics of infectious diseases (SIAM Review 2000), system (2.2) and Theorem 2.1.
Let \(\beta ,\gamma {\gt}0\) and \(R_0=\beta /\gamma \). A solution is a triple \((s,i,r)\) of real functions such that \(t\mapsto (s,i,r)(t)\) is an integral curve on \([0,\infty )\) (one-sided derivative at \(0\)) of the field \((s,i,r)\mapsto (-\beta si,\ \beta si-\gamma i,\ \gamma i)\), with \(s(0),i(0){\gt}0\), \(r(0)=0\) and \(s(0)+i(0)+r(0)=1\). Solutions are assumed, not constructed.
On \([0,\infty )\): \(s+i+r=1\); \(s,i{\gt}0\) and \(r\ge 0\); \(s\) is strictly decreasing and \(r\) strictly increasing; and \(s(t)=s(0)e^{-R_0r(t)}\).
The derivatives of \(s+i+r\) and of \(se^{R_0r}\) vanish (\(R_0\gamma =\beta \)), and a function with zero right derivative is constant. For \(i{\gt}0\), compare \(i\) with the barrier \(b(t)=\tfrac {i(0)}2e^{-\gamma t}\): where they touch, \(b'=-\gamma i{\lt}\beta si-\gamma i=i'\) since \(s{\gt}0\), so \(i\ge b\). Monotonicity follows from the signs of \(s'=-\beta si\) and \(r'=\gamma i\).
If \(R_0s(0)\le 1\), then \(i\) is strictly decreasing on \([0,\infty )\). The function \(i\) is strictly increasing on some \([0,\varepsilon ]\), \(\varepsilon {\gt}0\), iff \(R_0s(0){\gt}1\).
\(i'=i(\beta s-\gamma )\) and \(s(t){\lt}s(0)\) for \(t{\gt}0\). If \(R_0s(0){\gt}1\), then \(\beta s-\gamma {\gt}0\) near \(0\) by continuity.
\(i(t)\to 0\), \(s(t)\to s_\infty \) and \(r(t)\to 1-s_\infty \); moreover \(s_\infty =s(0)e^{-R_0(1-s_\infty )}\), \(0{\lt}s_\infty {\lt}1/R_0\), and \(s_\infty \) is the unique root of this equation in \((0,1/R_0]\) and in \((0,1]\).
\(s\) and \(r\) are monotone and bounded, so \(i=1-s-r\) converges; if \(i\to L{\gt}0\), the mean value theorem makes \(r\) grow by more than \(1\). Pass to the limit in \(s=s(0)e^{-R_0r}\). If \(R_0s_\infty \ge 1\) then \(i'{\gt}0\) forever, contradicting \(i\to 0\). Uniqueness: \(\log x-R_0x\) is strictly increasing on \((0,1/R_0]\) and strictly decreasing on \([1/R_0,\infty )\), and at \(x=1\) it exceeds its value \(\log s(0)-R_0\) at the roots because \(s(0){\lt}1\).
If \(R_0s(0){\gt}1\), there is \(t_{\max }{\gt}0\) with \(s(t_{\max })=1/R_0\) such that \(i\) is strictly increasing on \([0,t_{\max }]\) and strictly decreasing on \([t_{\max },\infty )\), and \(i(t_{\max })=i(0)+s(0)-1/R_0-\log (R_0s(0))/R_0\).
Intermediate value theorem between \(s(0){\gt}1/R_0\) and \(s_\infty {\lt}1/R_0\); the sign of \(\beta s-\gamma \) changes at \(t_{\max }\). The value follows from \(\log s=\log s(0)-R_0r\) and \(r=1-s-i\).
9 Kurtz’s law of large numbers for SIR, in discrete time
After Kurtz (J. Appl. Probab. 7, 1970) and Wormald (1999, Theorem 5.1), for the SIR model of Section 8.
Let \(\beta ,\gamma \in \mathbb N\). A configuration assigns to each of \(N\) agents a compartment \(S\), \(I\) or \(R\); \(X=(S,I,R)/N\) are the scaled counts. One step draws \((u,v)\) uniformly in \([N]^2\) and one of \(\beta +\gamma \) equally likely clocks: on one of the \(\beta \) infection clocks an infected \(u\) infects a susceptible \(v\), on one of the \(\gamma \) recovery clocks an infected \(u\) recovers. This is the continuous-time chain (\(S+I\to 2I\) at rate \(\beta SI/N\), \(I\to R\) at rate \(\gamma I\)) uniformized at rate \((\beta +\gamma )N\). The deviation probability is the probability that \(\| X_k-x(k/((\beta +\gamma )N))\| _\infty {\gt}\theta \) for some \(k\le n\).
\(\mathbb E[X_{k+1}-X_k\mid X_k=x]=F(x)/((\beta +\gamma )N)\) with \(F\) the Kermack–McKendrick field, and \(\| X_{k+1}-X_k\| _\infty \le 1/N\).
Among the \(N^2(\beta +\gamma )\) rounds, \(\beta IS\) move an agent from \(S\) to \(I\) and \(\gamma NI\) move one from \(I\) to \(R\); a round changes the compartment of at most one agent.
If increments \(D(X_j,\rho _j)\) along i.i.d. uniform rounds have zero conditional mean and \(|D|\le c\), their partial sums \(M_k\) satisfy \(\mathbb P(\exists k\le n,\ M_k\ge \lambda )\le e^{-\lambda ^2/(2nc^2)}\).
Hoeffding’s lemma (\(\mathbb E e^{\theta D}\le \cosh (\theta c)\le e^{\theta ^2c^2/2}\) by convexity) makes \(e^{\theta M_k-k\theta ^2c^2/2}\) a nonnegative supermartingale; Ville’s maximal inequality, proved by induction on \(n\) peeling off the first round, bounds the probability that it reaches \(\mu \) by \(1/\mu \); take \(\theta =\lambda /(nc^2)\).
Let \(\beta ,\gamma ,T{\gt}0\). There are \(C,c{\gt}0\) and \(L\) such that for every \(N\), every initial configuration, every solution \(x\) of the Kermack–McKendrick system started in the simplex and every \(\varepsilon {\gt}0\), with probability at least \(1-Ce^{-c\varepsilon ^2N}\), \(\| X_k-x(k/((\beta +\gamma )N))\| _\infty \le L\| X_0-x(0)\| _\infty +\varepsilon \) for all \(k\le T(\beta +\gamma )N\). Hence, if \(X_0\to x(0)\), the scaled chain converges to \(x\) in probability, uniformly on \([0,T]\).
The simplex is invariant under the ODE (first integral for \(s\), integrating factor for \(i\)); there \(F\) is \((2\beta +\gamma )\)-Lipschitz and bounded by \(\beta +\gamma \), so one Euler step errs by \(O(h^2)\), \(h=1/((\beta +\gamma )N)\). By Lemma 31 each coordinate of \(X_k-X_0-h\sum _{j{\lt}k}F(X_j)\) is a martingale with increments at most \(2/N\); on the event where the six one-sided maximal deviations stay below \(\delta =\varepsilon /(2L)\), the discrete Grönwall inequality gives the bound with \(L=e^{(2\beta +\gamma )T}\), once \(\varepsilon N\ge 2LT(2\beta +\gamma )\); Lemma 32 bounds the complement by \(6e^{-c\varepsilon ^2N}\). Small \(N\) and \(\varepsilon \ge 2\) are absorbed in \(C\).
10 Rumor spreading without self-calls: the model
This section and the next ones, up to Section 19, give a complete and elementary proof that the uniform push protocol on the complete graph \(K_n\), started from a single informed node, informs all \(n\) nodes within \(O(\log n)\) rounds with high probability (library RumorSpread, namespace RumorPush). Here every node calls a uniformly random node among the other \(n-1\), whereas the protocols of Sections 21 and 22 allow calls to oneself. The probability space is finite and uniform throughout; the only analytic ingredients are Bernoulli’s inequality and Markov’s inequality, and the only concentration tool is a one-line exponential-moment induction for adaptive Bernoulli trials. No measure theory, no PMF/ENNReal, no Chernoff bounds, and no martingales are used. This argument has been fully formalized (no sorry) in Lean 4 + Mathlib; the main theorem is RumorPush.push_informs_all_whp. With the same random calls, the pull and push–pull protocols of Karp, Schindelhauer, Shenker and Vöcking also inform all nodes within \(O(\log n)\) rounds with high probability (Section 19); for pull, a second-moment bound replaces the reverse Markov inequality.
Fix \(n \ge 2\) and let \(V = \{ 0,1,\dots ,n-1\} \) be the vertex set of the complete graph \(K_n\).
A round configuration is a function \(\omega \colon V \to V\) with \(\omega (v) \ne v\) for all \(v\). Let \(R_n\) denote the (finite) set of round configurations; it carries the uniform probability measure, i.e. every node picks a uniformly random target among the other \(n-1\) nodes, independently of all other nodes.
For an informed set \(I \subseteq V\) and a round configuration \(\omega \in R_n\), the next informed set is
(Only informed nodes actually transmit; letting all nodes draw a target and ignoring the choices of uninformed nodes is an equivalent and formalization-friendlier convention.)
Fix a horizon \(T \in \mathbb {N}\) and a start vertex \(v_0 \in V\). The sample space is \(\Omega = R_n^{\, T}\) (uniform measure, i.e. i.i.d. uniform rounds). For \(\omega = (\omega _0,\dots ,\omega _{T-1}) \in \Omega \) define \(I_0(\omega ) = \{ v_0\} \) and \(I_{t+1}(\omega ) = \mathrm{step}(I_t(\omega ), \omega _t)\) for \(0 \le t {\lt} T\). We write \(m_t = |I_t|\) and \(U_t = n - m_t\) for the numbers of informed and uninformed nodes. Since \(\Omega \) is finite, all probabilities are finite ratios and all expectations are finite sums; “conditioning on \(I_t\)” means partitioning \(\Omega \) according to the first \(t\) coordinates. In the formalization, a trajectory is simply a List of round configurations and \(\mathrm{run}\ I\ l\) folds step over the list \(l\).
Two trivial but load-bearing facts, both immediate from Definition 35:
\(I_t(\omega ) \subseteq I_{t+1}(\omega )\) for all \(t\) and all \(\omega \); hence \(m_t\) is non-decreasing and \(U_t\) is non-increasing in \(t\), pointwise on \(\Omega \).
\(|I_{t+1}(\omega ) \smallsetminus I_t(\omega )| \le |I_t(\omega )|\); equivalently \((\mathrm{step}(I,\omega )).\mathrm{card} \le 2\, I.\mathrm{card}\).
11 Push without self-calls: the main theorem
Throughout, \(\log \) denotes the natural logarithm.
Let \(n \ge 2\), let \(v_0 \in V\), and set
Then \(\Pr \bigl[\, I_T = V \, \bigr] \; \ge \; 1 - \frac{2}{n}\). In particular all nodes are informed after \(O(\log n)\) rounds with high probability.
The constants are deliberately crude: the proof is organized to minimize the analytic toolkit, not the round count. The sharp answer is \(\log _2 n + \log n + o(\log n)\) (Frieze–Grimmett [ 1 ] , Pittel [ 2 ] ). Replacing \(2/n\) by \(n^{-\alpha }\) for any fixed \(\alpha \ge 1\) only changes the constants in \(T_1, T_2\).
The proof has two phases, glued by Lemma 37:
Growth phase (Section 16): while \(m_t \le n/2\), each round multiplies \(m_t\) by \(\ge 9/8\) with probability \(\ge 1/8\); an exponential-moment bound for adaptive trials shows that after \(T_1\) rounds, \(m_{T_1} {\gt} n/2\) except with probability \(\le 1/n\).
Saturation phase (Section 17): once \(m_t \ge n/2\), the expected number of uninformed nodes contracts by a factor \(2/3\) per round; after \(T_2\) further rounds Markov’s inequality gives \(U_T = 0\) except with probability \(\le 1/n\).
12 Finite uniform probability
All randomness in this development is uniform over finite types, so instead of measure theory or PMF we work with plain finite sums. The definitions and their basic laws are those of the shared dynamics library (Dynamics.Uniform), which also identifies them with Mathlib’s finite expectation Finset.expect and with the independent product of uniform distributions (Dynamics.Bridge).
For a finite type \(\alpha \) and \(f \colon \alpha \to \mathbb {R}\), \(\mathrm{avg}(f) := \bigl(\sum _{a} f(a)\bigr) / |\alpha |\) is the expectation of \(f\) under the uniform distribution on \(\alpha \).
For a finite type \(\alpha \), \(\mathrm{expList}\ \alpha \ T\ F\) is the expectation of a functional \(F\) of a trajectory of \(T\) i.i.d. uniform draws from \(\alpha \), defined by recursion on \(T\): the head draw is averaged out first, i.e. \(\mathrm{expList}\ \alpha \ 0\ F = F(\, []\, )\) and \(\mathrm{expList}\ \alpha \ (T{+}1)\ F = \mathrm{avg}\bigl(a \mapsto \mathrm{expList}\ \alpha \ T\ (l \mapsto F(a :: l))\bigr)\). This makes “conditioning on the first round” a definitional unfolding rather than a measure-theoretic construction.
\(\mathrm{avg}\) and \(\mathrm{expList}\) are monotone, additive, and homogeneous, and constants pass through unchanged. These pointwise inequalities pushed through \(\mathrm{avg\_ le\_ avg}\) / \(\mathrm{expList\_ le\_ expList}\) are the only form in which Markov’s inequality and union bounds are used below (Lemmas 49 and 50); they are not separately formalized lemmas.
\(\mathrm{expList}\ \alpha \ T\ F\) equals the uniform average of \(F\) over all length-\(T\) sequences of draws, i.e. over the product probability space \(\mathrm{Fin}\ T \to \alpha \) of \(T\) i.i.d. uniform rounds. This confirms that the recursive definition of Definition 42 is the textbook object.
13 Elementary inequalities
We write \(x := \tfrac {1}{n-1}\), so \(0 {\lt} x \le 1\) for \(n \ge 2\).
For all real \(y \ge -1\) (we only use \(y\in [-1,1]\)) and \(m \in \mathbb {N}\): \((1+y)^m \ge 1 + my\). Equivalently, with \(y = -x\): \(1 - mx \le (1-x)^m\).
For \(0 \le x \le 1\) and \(m \in \mathbb {N}\):
and consequently \(mx/2 \le 1-(1-x)^m\) whenever \(mx \le 1\).
For \(0 \le x \le 1\) and \(m \in \mathbb {N}\): \((1-x)^m \le \dfrac {1}{1+mx}\).
For \(x {\gt} 0\): \(1 - \tfrac 1x \le \log x\). (The formalization only needs this left inequality, applied at \(x = 9/8,\ 16/15,\ 3/2\), together with Mathlib’s numeric bound \(\log 2 {\lt} 0.6931471808\).)
Let \(\Omega \) be a finite nonempty set with the uniform measure, \(f \colon \Omega \to \mathbb {R}\) with \(f \ge 0\), and \(a {\gt} 0\). Then \(\Pr [f \ge a] \le \mathbb {E}[f]/a\). In particular, if \(f\) takes values in \(\mathbb {N}\), then \(\Pr [f \ne 0] \le \mathbb {E}[f]\).
Let \(f \colon \Omega \to \mathbb {R}\) with \(0 \le f \le b\) pointwise, \(b {\gt} 0\), and let \(0 {\lt} a {\lt} b\). Then \(\Pr [f \ge a] \ge \dfrac {\mathbb {E}[f] - a}{b}\). (As with Lemma 49, the formalization does not isolate this as a named lemma: each use site supplies its own pointwise bound and pushes it through \(\mathrm{avg\_ le\_ avg}\), e.g. in the proof of Lemma 53.)
14 One-round estimates
Fix an informed set \(I\) with \(|I| = m \ge 1\) and let \(\omega \in R_n\) be a uniform round configuration. All statements in this section concern this single round; by independence of the rounds they apply verbatim to the conditional law of round \(t\) given \(I_t = I\).
For any fixed \(u \notin I\),
The Lean proof is the only place where a probability is computed rather than estimated: it counts round configurations avoiding \(u\) on \(I\) via an explicit equivalence to a product of subtypes and Fintype.card_pi.
Let \(N(\omega ) = |\mathrm{step}(I,\omega )| - m\) be the number of newly informed nodes. The formalization gives the exact formula
from which, if \(1 \le m \le n/2\): \(\mathbb {E}_\omega [N] \ge m/4\) (using Lemma 46 and \(n - m \ge n/2\), \(mx \le 1\)).
If \(1 \le m \le n/2\), then \(\Pr _\omega \bigl[\, |\mathrm{step}(I,\omega )| \ge \tfrac {9}{8}\, m\, \bigr] \ge \tfrac 18\).
If \(m \ge n/2\), then for every fixed \(u \notin I\), \(\Pr _\omega [u \notin \mathrm{step}(I,\omega )] = (1-x)^m \le \tfrac 23\), and consequently, with \(U' := n - |\mathrm{step}(I,\omega )|\), \(\mathbb {E}_\omega [U'] \le \tfrac 23(n-m)\).
15 Adaptive Bernoulli trials
A round is good if it multiplies the informed set by \(\ge 9/8\), or if the informed set already exceeds \(n/2\):
\(\mathrm{goodCount}\) counts the good rounds along a trajectory. By Lemma 53 (applied when \(m_t \le n/2\); trivial otherwise), \(\Pr [X_t = 1 \mid \omega _0,\dots ,\omega _{t-1}] \ge \tfrac 18\) for every prefix, since \(\omega _t\) is independent of the prefix and \(\mathrm{expList}\) conditions on it definitionally.
For every \(T\) and every nonempty \(I\),
over \(T\) rounds started at \(I\). (This specializes the textbook “\(\mathbb {E}[s^G] \le (1-p(1-s))^T\) for adaptive \(\{ 0,1\} \)-trials with per-step success probability \(\ge p\)” at \(p = 1/8\), \(s = 1/2\); the formalization proves the specialized statement directly by induction on \(T\) rather than the general one, since only this instance is needed. The ensuing tail bound \(\Pr [G {\lt} L] \le 2^{L}(15/16)^{T}\) (via \(s^{L}\Pr [G{\lt}L] \le \mathbb {E}[s^G]\)) is likewise not isolated as a separate lemma; it is proved inline inside Lemma 58 (phase1).
16 Push: the growth phase
Let \(L \in \mathbb {N}\) satisfy \((9/8)^L {\gt} n/2\). If the informed set never exceeds \(n/2\) up to time \(T_1\), then along that trajectory \(m_{T_1} \ge (9/8)^{\mathrm{goodCount}} \cdot m_0\): every good round multiplies \(m_t\) by \(\ge 9/8\) and every round is non-decreasing (Lemma 37), so \(\mathrm{goodCount} \ge L\) would force \(m_{T_1} {\gt} n/2\), a contradiction; hence \(\mathrm{goodCount} {\lt} L \Rightarrow m_{T_1} \le n/2\) is impossible to rule out only via the deterministic growth bound stated here.
If \((9/8)^L \ge n\), then after \(T_1\) rounds the informed set is still \(\le n/2\) with probability at most \(2^{L}\, (15/16)^{T_1}\).
With \(L = \left\lceil 9 \log n \right\rceil + 1\) we have \((9/8)^L \ge n\) (numeric_A), and with \(T_1 = \left\lceil 117 \log n \right\rceil + 23\) we have \(2^{L}(15/16)^{T_1} \le 1/n\) (numeric_B), using \(\log \tfrac 98 \ge \tfrac 19\), \(\log \tfrac {16}{15} \ge \tfrac 1{16}\) and \(\log 2 {\lt} 0.6932\). Combined with Lemma 58: \(\Pr [m_{T_1} \le n/2] \le 1/n\). The clean statement to formalize is that any \(L, T_1\) satisfying these two numeric inequalities work; the values above merely exhibit admissible ones.
17 Push: the saturation phase
Let \(A = \{ m_{T_1} {\gt} n/2\} \) (an event determined by the first \(T_1\) coordinates). Then for every \(s \ge 0\), \(\mathbb {E}\bigl[\, U_{T_1 + s}\, \mathbf{1}_A \, \bigr] \le (2/3)^{s}\, n\), by induction on \(s\) using Lemma 54 at each step (monotonicity keeps \(m_{T_1+s} {\gt} n/2\) on \(A\)).
With \(T_2 = \left\lceil 6 \log n \right\rceil \): \(\Pr [\, U_T \ge 1 \text{ and } A \, ] \le n\, (2/3)^{T_2} \le 1/n\). (\(U_T\) is \(\mathbb {N}\)-valued, so Markov applied to \(U_T \mathbf{1}_A\) and Lemma 60 give the first inequality; \((2/3)^{T_2} n \le 1/n\) (numeric_C) follows from \(\log \tfrac 32 \ge \tfrac 13\) and \(T_2 \ge 6\log n\).)
18 Proof of the push theorem
Let \(\mathrm{prNotAllInformed}(n,v_0,T)\) be the probability that some node is still uninformed after \(T\) rounds started at \(v_0\). For all \(L, T_1, T_2\) with \((9/8)^L \le n\):
Failure requires either phase 1 to fail (informed set still \(\le n/2\) after \(T_1\) rounds, Lemma 58) or phase 2 to leave an uninformed node on the complementary event, controlled by Lemma 60 via Markov.
With \(T_1 = \left\lceil 117\log n \right\rceil + 23\), \(T_2 = \left\lceil 6\log n \right\rceil \), \(T = T_1+T_2\), Theorem 39 follows from Lemma 62, Lemma 59 and Corollary 61:
19 PULL and PUSH–PULL without self-calls
We now treat the two other protocols of Karp, Schindelhauer, Shenker and Vöcking [ 3 ] , driven by the same random calls: in a round configuration \(\omega \in R_n\) every node \(v\) calls \(\omega (v)\). In PULL the caller learns the rumor from its callee; in PUSH–PULL the rumor travels in both directions along every call. As for PUSH, partners are chosen among the other \(n-1\) nodes (KSSV allow self-calls; only constants change), and the round count is a crude \(O(\log n)\) instead of the sharp \(\log _3 n + O(\log \log n)\) of [ 3 , Thm. 2.1 ] .
\(\mathrm{pullStep}(I,\omega ) = I \cup \{ v : \omega (v) \in I\} \) and \(\mathrm{pushPullStep}(I,\omega ) = \mathrm{step}(I,\omega ) \cup \mathrm{pullStep}(I,\omega )\); trajectories fold these steps over a list of i.i.d. uniform rounds, and the failure probabilities are the probabilities that some node is still uninformed after \(T\) rounds started from \(\{ v_0\} \).
With the same calls, the PUSH–PULL informed set contains the PUSH and the PULL informed sets after every number of rounds.
The calls \(\omega (v)\), \(v \in V\), of a uniform round are independent, each uniform among the other \(n-1\) nodes; in particular a caller \(v \notin I\) calls into \(I\) with probability \(|I|/(n-1)\).
Let \(m = |I|\) and \(u = n - m\). From a single informed node a PULL round informs nobody with probability \((1 - \frac1{n-1})^{n-1}\). After one PULL round, \(\mathbb {E}|I'| = m + u\, \frac{m}{n-1}\) and \(\mathbb {E}[n - |I'|] = \frac{u(u-1)}{n-1} \le \frac{u^2}{n}\) (quadratic shrinking). After one PUSH–PULL round, \(\mathbb {E}[n - |I'|] = \frac{u(u-1)}{n-1}\bigl(1 - \frac1{n-1}\bigr)^{m}\).
Let \(f(I,a) \supseteq I\) be a spreading step driven by i.i.d. uniform rounds \(a\). Suppose that from every nonempty \(I\) a round is good (\(|f(I,a)| \ge \frac98 |I|\), or \(|I| {\gt} n/2\)) with probability at least \(1/8\), and that for \(|I| \ge n/2\) the expected number of uninformed nodes contracts by \(2/3\). Then after \(\left\lceil 160 \log n \right\rceil \) rounds from \(\{ v_0\} \), some node is uninformed with probability at most \(2/n\). The proof is the PUSH proof of Sections 15–18, which uses no other property of \(\mathrm{step}\).
A PULL round is good with probability at least \(1/8\), and for \(|I| \ge n/2\) it contracts the expected uninformed count by \(2/3\).
The contraction follows from \(\frac{u(u-1)}{n-1} \le \frac23 u\) for \(u \le n/2\). For good rounds, let \(X\) be the number of uninformed callers that call into \(I\), so \(|I'| = |I| + X\). By Lemma 65, \(\mu = \mathbb {E}X = \frac{(n-m)m}{n-1} \ge \max (m/2, 1/2)\) for \(m \le n/2\) and, the calls being pairwise independent, \(\mathbb {E}X^2 \le \mu + \mu ^2\). A round with \(X {\gt} \mu /4 \ge m/8\) is good, and the one-sided Paley–Zygmund inequality gives \(\Pr [X {\gt} \mu /4] \ge \frac{(3/4)^2\mu ^2}{\mathbb {E}X^2} \ge \frac{9\mu }{16(1+\mu )} \ge 3/16\). Unlike PUSH, the reverse Markov argument of Lemma 53 does not apply, since a PULL round can inform many more than \(|I|\) new nodes.
Let \(n \ge 2\) and \(v_0 \in V\). After \(\left\lceil 160 \log n \right\rceil \) rounds of PULL, or of PUSH–PULL, started from \(\{ v_0\} \), all nodes are informed with probability at least \(1 - 2/n\).
20 The Lean library RumorSpread
Sections 10 to 19 are fully formalized in the library RumorSpread of this package (namespace RumorPush); the build contains no sorry and the main theorem depends only on the three standard axioms (propext, Classical.choice, Quot.sound). File structure (dependency order): Bounds.lean (Section 13), Dynamics.Uniform of the shared dynamics library (Section 12), Model.lean (Section 10), OneRound.lean (Section 14), Growth.lean (Sections 15–16), Saturation.lean (Section 17), Main.lean (main theorem and numeric lemmas), Dynamics.Equivalence of the shared dynamics library (Theorem 44). PULL and PUSH–PULL (Section 19): PullFoldl.lean and PullModel.lean (Definition 63, Lemma 64), PullIndep.lean (Lemma 65), PullOneRound.lean (Lemma 66), PullPhases.lean (Lemma 67), PullGood.lean (Lemma 68), PullMain.lean and PullPushPull.lean (Theorem 69).
21 Randomized rumor spreading revisited
We follow Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version arXiv:2303.11150), with the numbering of the long version.
Lemma 20 of the paper needs a major correction; corrected versions are formalized (Lemma 75, details). The proof of Theorem 43 and the parameters of the push, pull and push–pull instances need a minor correction, and the corrected versions are formalized (details).
A rumor-spreading process on \(n\) nodes is a Markov kernel on the set \(S\) of informed nodes under which informed nodes stay informed. For a round started from \(S\), \(\mathrm{informProb}(S,x)\) is the probability that \(x\) is informed after the round and \(\mathrm{cov}(S,x,y)\) the covariance of the events that \(x\) and \(y\) are. The tail of the spreading time is \(\mathrm{notYet}(m,t,S)=\Pr [\text{fewer than }m\text{ nodes informed after }t\text{ rounds from }S]=\Pr [T(|S|,m){\gt}t]\); expected times are bounded through all partial sums of \(\sum _t\Pr [T{\gt}t]\). Homogeneity (Definition 6) is defined but not assumed.
Upper exponential growth (Definition 9): for \(1\le |S|=k{\lt}fn\), every uninformed node is informed with probability at least \(\gamma \frac kn(1-a\frac kn-\frac b{\ln n})\) and covariances are at most \(ck/n^2\). Upper exponential shrinking (Definition 11): when \(u=n-|S|\le gn\), every uninformed node stays uninformed with probability at most \(e^{-\rho }+au/n\) and covariances are at most \(c/u\).
If distinct uninformed nodes have covariance at most \(c\), the number of informed nodes after one round has variance at most its expected increase plus \(c(n-|S|)^2\).
Expand the variance of a sum of indicators.
If every uninformed node is informed with probability at least \(p\) in every round started with \(\ell \le |S|{\lt}m\) informed nodes, then \(\Pr [T(\ell ,m){\gt}r]\le \frac{n-\ell }{n-m}(1-p)^r\) and \(E[T(\ell ,m)]\le \frac{n-\ell }{n-m}\cdot \frac1p\).
The potential \(n-|S|\) (set to \(0\) once \(|S|\ge m\)) contracts by \(1-p\) in expectation.
Under the upper exponential growth conditions, with \(\gamma \) between two positive constants and \(af{\lt}1\), from any nonempty \(S\): \(\Pr [T(|S|,fn){\gt}\lceil \log _{1+\gamma }n\rceil +r]\le Ae^{-\alpha r}\) and \(E[T(|S|,fn)]\le \log _{1+\gamma }n+B\), with constants depending only on the parameters.
Phases \(k_{j+1}=k_j+E_0(k_j)\) with a round target \(E_0(k)=E(k)-Ak^{3/4}\); Cantelli’s inequality (Lemma 72) bounds the probability of missing a target, and a phase potential on the iterated kernel replaces the paper’s domination by geometric variables. Lemma 73 crosses the last stretch up to \(fn\).
If every round started with \(1\le |S|{\lt}fn\) has \(p_k\le p\) and covariances at most \(c/n\), then (one round) for every \(f'\in \, ]f+p(1-f),1[\), a round from \(|S|{\lt}fn\) ends with at least \(f'n\) informed nodes with probability at most \(C/n\); and (path form) there is \(f'\in \, ]f,1[\) such that the probability of jumping over \([fn,f'n[\) within \(t\) rounds is at most \(\frac Cn\) times the expected number of these rounds started below \(fn\), i.e. \(O(E[T(|S|,fn)]/n)\).
Chebyshev’s inequality with Lemma 72 for one round, then a union bound over the rounds along the trajectory.
The paper’s Lemma 20 claims probability \(1-O(1/n)\) of landing in \([fn,f'n]\); this needs a major correction, as the process that from every \(|S|{\lt}fn\) informs all nodes with probability \(c/n\) (and otherwise none) satisfies the hypotheses and jumps from \(1\) to \(n\) with probability one (details).
Under the upper exponential shrinking conditions, with \(\rho \) between two positive constants and \(e^{-\rho _{lo}}+ag{\lt}1\), from any \(S\) with \(n-|S|\le gn\): \(\Pr [T(|S|,n){\gt}\lceil \ln n/\rho \rceil +r]\le Ae^{-\alpha r}\) and \(E[T(|S|,n)]\le \ln n/\rho +B\).
Under the growth conditions on \([1,fn[\), the shrinking conditions below \(gn\) uninformed nodes and a probability at least \(p{\gt}0\) of being informed in between, from any nonempty \(S\): \(\Pr [T{\gt}\lceil \log _{1+\gamma }n\rceil +\lceil \ln n/\rho \rceil +r]\le Ae^{-\alpha r}\) and \(E[T]\le \log _{1+\gamma }n+\ln n/\rho +B\).
Definition 13: when \(n^{1-\alpha }\le u=n-|S|\le gn\), every uninformed node stays uninformed with probability at most \(a(u/n)^{\ell -1}\) and covariances are at most \(cn/u^2\). Fast finishing (the second hypothesis of Theorem 43): when \(u\le n^{1-\alpha }\), every uninformed node stays uninformed with probability at most \(n^{-\tau }\).
Let \(\ell {\gt}1\), \(a,c\ge 0\), \(g,\alpha \in [0,1]\), \(ag^{\ell -1}{\lt}1\) and \(\tau {\gt}0\). Under the upper double exponential shrinking conditions and fast finishing, from any \(S\) with \(n-|S|\le gn\): \(\Pr [T(|S|,n){\gt}\lceil \log _\ell \ln n\rceil +r]\le Cn^{A'-\alpha 'r}\) and \(E[T(|S|,n)]\le \log _\ell \ln n+B\).
Three stages. Geometric targets \(g\mu ^jn\), \(\mu =(1+ag^{\ell -1})/2\), bring \(u\) below \(g_0n\) in a constant number of phases; double exponential targets \(\varepsilon _{j+1}=2a_1\varepsilon _j^\ell \), i.e. \(\varepsilon _j=e^{-(\kappa +\ell ^jD_0)}\), bring it below \(\varepsilon _Jn\le n^{1-\beta /(2\ell )}\) in \(J\le \log _\ell \ln n\) phases; below that, every uninformed node stays uninformed with probability at most \(n^{-\tau _3}\) and Markov’s inequality finishes. A phase fails with probability at most \(n^{-2\delta }\) (Chebyshev with Lemma 72 above \(n^{1-\alpha }\) uninformed nodes, Markov with fast finishing below), and the phase potential \(\lambda ^{J-j}\), \(\lambda =n^\delta \), contracts by \(n^{-2\delta }+n^{-\delta }\) per round. The paper’s first stage uses Lemma 19, whose tail rate does not depend on \(n\); the per-round Chebyshev bound gives the polynomial tail.
Under the growth conditions on \([1,fn[\), the double exponential shrinking conditions and fast finishing below \(gn\) uninformed nodes (\(g{\gt}0\)), and a probability at least \(p{\gt}0\) of being informed in between, from any nonempty \(S\): \(\Pr [T{\gt}\lceil \log _{1+\gamma }n\rceil +\lceil \log _\ell \ln n\rceil +r]\le Ae^{-\kappa r}\) and \(E[T]\le \log _{1+\gamma }n+\log _\ell \ln n+B\).
In a round every node calls a uniformly random node (itself included), independently. Push: informed nodes inform the nodes they call. Pull: uninformed nodes calling an informed node become informed. Push–pull: both.
These protocols allow calls to oneself, as in the paper. Sections 10 to 19 treat the same three protocols with calls among the other \(n-1\) nodes only: there the bounds are \(O(\log n)\) with explicit constants, for every \(n\ge 2\), while here they are sharp, with constants and a threshold on \(n\) that are only shown to exist. The two models are different processes, and neither development uses the other.
With \(k=|S|\) informed nodes, an uninformed node is informed with probability \(1-(1-\frac1n)^k\) (push), \(\frac kn\) (pull), \(1-(1-\frac1n)^k(1-\frac kn)\) (push–pull); distinct uninformed nodes are nonpositively correlated (independent for pull). Hence push satisfies the upper growth conditions with \(\gamma =1\), \(a=\frac12\) and the upper shrinking conditions with \(\rho =1\), \(a=\frac2e\), \(g=\frac12\); pull and push–pull satisfy the growth conditions with \(\gamma =1\), \(a=0\) and \(\gamma =2\), \(a=\frac34\), and the double exponential shrinking conditions with \(\ell =2\), \(a=1\), \(g=\alpha =\frac12\) and fast finishing with \(\tau =\frac12\) (all with \(b=c=0\), \(f=\frac12\)).
The calls are independent uniform coordinates, so the events “\(x\) stays uninformed” and “\(x\) and \(y\) stay uninformed” have product probabilities. The bounds use \((1-x)^k\le 1-kx+(kx)^2/2\) and \(e^t\le 1+2t\) on \([0,1]\).
From any nonempty set of informed nodes on \(K_n\), all nodes are informed within \(\lceil \log _2n\rceil +\lceil \ln n\rceil +r\) (push), \(\lceil \log _2n\rceil +\lceil \log _2\ln n\rceil +r\) (pull) and \(\lceil \log _3n\rceil +\lceil \log _2\ln n\rceil +r\) (push–pull) rounds, except with probability at most \(Ae^{-\kappa r}\); the expected times are at most \(\log _2n+\ln n+B\), \(\log _2n+\log _2\ln n+B\) and \(\log _3n+\log _2\ln n+B\).
22 Rumor spreading revisited: lower bounds for push, pull and push–pull
The lower halves of Theorems 51 to 53 of Doerr and Kostrygin (same paper and numbering as Section 21): started from one informed node, push, pull and push–pull need \(\log _2n+\ln n\), \(\log _2n+\log _2\ln n\) and \(\log _3n+\log _2\ln n\) rounds minus \(O(1)\), in expectation and with exponential tails. With Theorem 83 this determines the spreading times up to additive constants. The general lower bounds (Theorems 27, 38 and 48) are not formalized: the paper joins them through Lemma 20, which needs a major correction, and the formal proofs take a direct route for the instances. The growth phase is bounded by the first moment, the final phase by a round-by-round lower envelope, and the two are joined at a fixed time.
The paper’s joining of the phases also needs a minor correction (Theorems 38 and 48 start from an exact number of uninformed nodes, which the process started from one node need not visit), and so do Corollary 17 (not for \(u=0\)), the statement of Lemma 42 (\(q(u_{j+1})\) for \(q(u_j)\)), some typos in Lemmas 39 and 40, and a constant in the proof of Theorem 27; none affects the statements (details).
Let \(V\) be an observable of a Markov kernel and \((g_i)\), \((\delta _i)\) sequences with \(\delta _i\ge 0\). If from every state with \(V\ge g_i\) the observable falls below \(g_{i+1}\) in one round with probability at most \(\delta _i\), then from a state with \(V\ge g_0\) it is below \(g_t\) after \(t\) rounds with probability at most \(\sum _{i{\lt}t}\delta _i\) (the round-by-round form of Lemmas 42 and 50). For a rumor-spreading process: if one round multiplies the expected number of informed nodes by at most \(\mu \), then \(\Pr [T(|S|,m)\le t]\le \mu ^t|S|/m\); and if every state with fewer than \(m'\) informed nodes reaches \(m\) within \(t\) rounds with probability at most \(B\), then \(\Pr [T(|S|,m)\le s+t]\le \Pr [T(|S|,m')\le s]+B\).
Induction on \(t\) for the envelope; Markov’s inequality on \(E|S_t|\le \mu ^t|S|\); the Markov property at time \(s\).
After one round from \(S\), \(E|S'|\le 2|S|\) (push, pull) and \(E|S'|\le 3|S|\) (push–pull), and \(E[n-|S'|]=(n-|S|)(1-\frac1n)^{|S|}\), \((n-|S|)(1-\frac{|S|}n)\) and \((n-|S|)(1-\frac1n)^{|S|}(1-\frac{|S|}n)\). Hence \(\Pr [T(|S|,m)\le t]\le 2^t|S|/m\) (push, pull) and \(3^t|S|/m\) (push–pull).
Let \(u=n-|S|\) and \(u'\) the number of uninformed nodes after one round. Push, at any level \(4\le v\le u\): \(\Pr [u'{\lt}v/e-v^{3/4}]\le v^{-1/2}\). Pull: \(\Pr [u'{\lt}u^2/(2n)]\le 4n^2/u^3\). Push–pull: \(\Pr [u'{\lt}u^2/(2en)]\le 4e^2n^2/u^3\).
Chebyshev’s inequality on the lower tail of \(u'\), with \(\mathrm{Var}[u']\le u\) (Lemma 72 with nonpositive covariances) and \(E[u']\ge u/e\) (push, from \((1-\frac1n)^k\ge e^{-1}\) for \(k{\lt}n\)), \(E[u']=u^2/n\) (pull), \(E[u']\ge u^2/(en)\) (push–pull).
For every \(n\), every \(S\) with \(u=n-|S|\) uninformed nodes and every \(t\): \(\Pr [T(|S|,n)\le t]\le 1600\, e^{(t-\ln u)/2}\).
Lower envelope (Lemma 84) along the explicit targets \(g_i=q_i^3(q_i-20)\), \(q_i=(ue^{-i})^{1/4}\), which replace the paper’s recursive \(u_{j+1}=E_0(u_j)\) (Lemma 40). The step \(g(qe^{-1/4})\le g(q)/e-g(q)^{3/4}\) reduces to \(c^4-20c+20\le 0\) for \(c=e^{1/4}\); while \(q_i\ge 40\), round \(i\) fails with probability at most \(2/q_i^2\) (Lemma 86) and these failure probabilities sum to at most \(4e^{(t-\ln u)/2}\); when \(q_t{\lt}40\) the bound exceeds \(1\).
For \(n\ge 3\), every \(S\) with \(2|S|\le n\) and every \(t\le \log _2\ln n-5\): \(\Pr [T(|S|,n)\le t]\le 128\, n^{-1/2}\) (pull) and \(128e^2n^{-1/2}\) (push–pull).
Lower envelope along the double exponential targets \(g_i=2n(1/4)^{2^i}\) (pull) and \(2en(1/(4e))^{2^i}\) (push–pull), the paper’s \(\varepsilon _{j+1}=E(\varepsilon _j)/2\), with Lemma 86. The paper’s exponent \(-1+2\alpha \ell \) is replaced by the weaker \(-1/2\), which comes from the cruder variance bound and suffices below.
There are \(A\), \(B\), \(\kappa {\gt}0\) and \(N\) such that, for \(n\ge N\) and one informed node on \(K_n\), all nodes are informed within \(\lfloor \log _2n\rfloor +\lfloor \ln n\rfloor -r\) (push), \(\lfloor \log _2n\rfloor +\lfloor \log _2\ln n\rfloor -r\) (pull) and \(\lfloor \log _3n\rfloor +\lfloor \log _2\ln n\rfloor -r\) (push–pull) rounds with probability at most \(Ae^{-\kappa r}\); the expected times are at least \(\log _2n+\ln n-B\), \(\log _2n+\log _2\ln n-B\) and \(\log _3n+\log _2\ln n-B\) (stated for every partial sum \(\sum _{t{\lt}R}\Pr [T{\gt}t]\) with \(R\) at least the bound).
Join the two phases at a fixed time (Lemma 84) with \(m'=n/2\). Push: after \(\lfloor \log _2n\rfloor -\lceil r/2\rceil \) rounds at most \(n/2\) nodes are informed except with probability \(O(2^{-r/2})\) (Lemma 85), and from there Theorem 87 bounds the rest. Pull and push–pull: the same with \(\lfloor \log _2\ln n\rfloor -5\) rounds for the final phase (Theorem 88), whose \(n^{-1/2}\) becomes \(e^{-(\ln 2/4)r}\) since a nontrivial time forces \(r\le 2\log _2n\). The tails have rate \(\kappa =\ln 2/4\); the expectations follow by summing the tail series.
23 COBRA and BIPS: the model
We follow Cooper, Radzik and Rivera, The coalescing-branching random walk on expanders and the dual epidemic process, PODC 2016 (arXiv:1602.05768). The duality itself (their Theorem 4) is in the next section.
In a round \(r\), every vertex \(x\) of a finite graph \(G\) samples \(k\) neighbours \(r(x,0),\dots ,r(x,k-1)\). A uniform round is exactly the paper’s sampling: \(k\) uniform neighbours with replacement, independently for every vertex; \(t\) i.i.d. uniform rounds are averaged with Dynamics.expList. If \(G\) is connected and has at least two vertices, rounds exist.
Every vertex of a connected graph with at least two vertices has a neighbour.
COBRA from \(C_0=C\): \(C_{s+1}=\{ r_{s+1}(x,i) : x\in C_s,\ i{\lt}k\} \). BIPS with persistent source \(v\) from \(A_0\): \(A_{s+1}=\{ v\} \cup \{ u : \exists i,\ r_{s+1}(u,i)\in A_s\} \).
24 COBRA–BIPS duality
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)]\).
The uniform average over \(\mathrm{Fin}\, T\to \alpha \) is invariant under \(\omega \mapsto \omega \circ \mathrm{rev}\) (the time-reversal lemma of the shared dynamics package).
For all rounds \(r_1,\dots ,r_t\): COBRA from \(C\) along \(r_1,\dots ,r_t\) visits \(v\) at some time \(s\le t\) (time \(0\) included) iff BIPS from \(\{ v\} \) along \(r_t,\dots ,r_1\) infects a vertex of \(C\).
Induction on \(t\), generalizing \(C\). Both sides say that a chain \(x_0\in C\), \(x_j=r_j(x_{j-1},i_j)\), reaches \(v\) within \(t\) steps: COBRA unfolds the first round, BIPS the last round of the reversed sequence.
For every finite graph, every \(k\), every vertex \(v\), set \(C\) and time \(t\): \(\hat{\mathbb P}(\mathrm{Hit}_C(v){\gt}t\mid C_0=C)=\mathbb P(C\cap A_t=\emptyset \mid A_0=\{ v\} )\). In particular (equation (2)), \(\hat{\mathbb P}(\mathrm{Hit}_u(v){\gt}t)=\mathbb P(u\notin A_t\mid A_0=\{ v\} )\). The paper assumes \(G\) connected and regular and \(k\ge 1\); none of this is needed.
Assume that rounds exist. COBRA stopped when it visits \(v\) and BIPS with source \(v\), on the sets that contain \(v\), are dual with respect to \(H(C,A)=1\{ C\cap A=\emptyset \} \): \(\mathbb {E}_C[H(C_1,A)]=\mathbb {E}_A[H(C,A_1)]\) (Dynamics.Kernel.Dual). Hence for every \(t\) the probability that the COBRA kernel from \(C\) has not visited \(v\) by time \(t\) is \(\Pr (C\cap A_t=\emptyset \mid A_0=\{ v\} )\), which is Theorem 94 again.
For every round and every \(A\ni v\), the stopped COBRA step from \(C\) avoids \(A\) iff \(C\) avoids the BIPS step from \(A\): if \(v\in C\) both sides fail, and otherwise both say that no vertex of \(C\) samples a vertex of \(A\). Duality at every time follows from the one-step duality by the Markov property (the shared lemma on duality), as in the paper’s proof by one-step conditioning.
25 COBRA cover time on expanders
Here \(G\) is \(r\)-regular with \(r{\gt}0\) on \(n\) vertices, \(P=A(G)/r\), \(\lambda =\max (\lambda _2,|\lambda _n|)\), \(k\ge 2\), and \(d_A(x)=|N(x)\cap A|\). Expectations of unbounded times \(\tau \) are written as tail sums: every partial sum \(\sum _{s{\lt}H}\Pr (\tau {\gt}s)\) is bounded uniformly in \(H\).
\(\lambda =\max (\lambda _2,|\lambda _n|)\) for the sorted eigenvalues of \(P\) (\(0\) if \(n{\lt}2\)).
For every set \(A\): \(\sum _x (d_A(x)/r)^2\le \lambda ^2|A|+(1-\lambda ^2)|A|^2/n\).
\(\sum _x(d_A(x)/r)^2=\| P1_A\| ^2\); expand \(1_A\) in an orthonormal eigenbasis of \(P\): the top eigenvector is constant with coefficient \(|A|/\sqrt n\), and every other eigenvalue has square at most \(\lambda ^2\). If \(\lambda \ge 1\), use \(d_A(x)\le r\) and \(\sum _x d_A(x)=r|A|\).
One BIPS round from \(A\) gives \(\mathbb {E}|A'|\ge |A|(1+(1-\lambda ^2)(1-|A|/n))\), \(\mathbb {E}e^{-\varphi |A'|}\le \exp (-(1-e^{-\varphi })\mathbb {E}|A'|)\) for every real \(\varphi \), and \(\Pr (|A'|\le (1-\delta )\mu )\le e^{-\delta ^2\mu /2}\) for \(\mu \le \mathbb {E}|A'|\), \(0{\lt}\delta {\lt}1\).
Vertices are infected independently; \(u\ne v\) with probability \(1-(1-d_A(u)/r)^k\ge 2d_A(u)/r-(d_A(u)/r)^2\). Sum and apply Lemma 97. The MGF factors over the vertices and \(1-x\le e^{-x}\); the Chernoff bound is Markov’s inequality with \(\varphi =-\log (1-\delta )\).
Let a round-driven set process have a persistent source, the MGF bound of Lemma 98, growth \(\mathbb {E}|A'|\ge |A|(1+c(1-|A|/n))\) with \(0{\lt}c\le 1\), be monotone, and have \(V\) absorbing. From \(\{ v\} \) the size exceeds \(m\le n/2\) within \(13m/c+24C\log n/c^2\) rounds except with probability \(n^{-C}\); from \(|A_0|\ge 4000\log n/c^2\) it reaches \(9n/10\) within \(T\ge 24\log n/c\) rounds except with probability \(T n^{-5}\); from \(|A_0|\ge 9n/10\) (if \(4000\log n/c^2\le 9n/10\)) it covers \(V\) after \(T\ge 8\log n/c\) rounds except with probability \(n^{-5}\). BIPS satisfies the hypotheses with \(c=1-\lambda \).
Lemma 2: the exponential supermartingale \(e^{-\varphi |A_t|}\) on the event of staying small, \(\varphi =\log (1+c/2)\). Lemma 3: a round with \(|A'|{\lt}|A|(1+c/23)\) has probability \(\le n^{-5}\); union bound over rounds with moving targets. Lemma 4: staying above \(9n/10\) and the recursion \(\mathbb {E}B_{t+1}\le \theta \mathbb {E}B_t+tn^{-7}\) for the number \(B_t\) of healthy vertices. The paper’s Lemmas 3 and 4 need minor corrections (\(\log _2\) versus \(\ln \) doublings; a missing factor \(B_0\)).
If \(1-\lambda \ge 128\sqrt{\log n/n}\), BIPS from \(\{ v\} \) has \(A_T\ne V\) with probability at most \(3/n^3\) for \(T\ge 60000\log n/(1-\lambda )^3\), and \(\sum _{s{\lt}H}\Pr (A_s\ne V)\le 130000\log n/(1-\lambda )^3\).
Chain the three phases at their first hitting times with \(m=\left\lceil 4000\log n/(1-\lambda )^2 \right\rceil \) and \(C=3\). (The paper’s proof takes \(m=4000\log n/(1-\lambda ^2)\), which needs a minor correction: Lemma 3 needs \(|A|\ge 4000\log n/(1-\lambda )^2\).) For the expectation, restart from the current set: monotonicity and the persistent source give \(\Pr (A_{s+T_0}\ne V)\le \Pr (A_s\ne V)/2\).
If \(1-\lambda \ge 128\sqrt{\log n/n}\), COBRA from \(\{ u\} \) has \(\bigcup _{t=1}^T C_t\ne V\) with probability at most \(3/n^2\) for \(T\ge 60002\log n/(1-\lambda )^3\), and every partial tail sum of the cover time is at most \(130000\log n/(1-\lambda )^3\).
Union bound over the missed vertex \(w\). Splitting off the first round, missing \(w\) at the times \(1,\dots ,T\) is not hitting \(w\) within \(T-1\) rounds from \(C_1\ne \emptyset \), which by Theorem 94 has probability \(\Pr (C_1\cap A_{T-1}=\emptyset )\le \Pr (A_{T-1}\ne V)\). For the expectation, restart COBRA from the nonempty set \(C_s\) (equation (1)).
A round gives every vertex two neighbour samples and a uniform coin in \(\{ 0,\dots ,q-1\} \); a vertex uses its second sample iff its coin is \({\lt}p\). COBRA pushes to the used samples, BIPS contacts them.
The duality holds for the coin processes; with \(\rho =p/q\), \(\mathbb {E}|A'|\ge |A|(1+\rho (1-\lambda ^2)(1-|A|/n))\); and for constants \(\lambda _0{\lt}1\), \(\rho _0{\gt}0\) there are \(C,N\) such that for \(n\ge N\), \(\lambda \le \lambda _0\) and \(\rho \in [\rho _0,1]\) the COBRA cover time with branching factor \(1+\rho \) is at most \(C\log n\) with probability \(1-C/n^2\) and in expectation.
Both coin processes are target-set processes, whose duality is proved as Theorem 4. A vertex \(u\ne v\) is infected with probability \((1+\rho )P_u-\rho P_u^2\), \(P_u=d_A(u)/r\); sum and apply Lemma 97. Then Theorems 99 to 101 apply with \(c=\min (1,\rho _0(1-\max (\lambda _0,0)))\), and \(128\sqrt{\log n/n}\le c\) for \(n\) large.