- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
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 \).
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\).
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.
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.
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 \).
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.
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\} \).
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 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.
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.
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.
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.
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\).
\(\lambda =\max (\lambda _2,|\lambda _n|)\) for the sorted eigenvalues of \(P\) (\(0\) if \(n{\lt}2\)).
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\).
\(\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\} \).
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 \).
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.
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\).
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 }\).
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.
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.
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.)
\(\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\).
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).
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\).
\(\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.
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)}\).
For \(0 \le x \le 1\) and \(m \in \mathbb {N}\):
and consequently \(mx/2 \le 1-(1-x)^m\) whenever \(mx \le 1\).
At least \(t\) successes among \(t(d-1)+1\) independent Bernoulli\((p)\) trials occur with probability at most \(\exp (\varepsilon - \varepsilon ^2 t/2)\).
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.
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.
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\).
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)\).
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.
- Epidemics.DFS.State.Inv
- Epidemics.DFS.State.move_settle
- Epidemics.DFS.fresh_nextQuery
- Epidemics.DFS.card_queried_ofAnswers
- Epidemics.DFS.mem_found_iff_of_queryAnswers
- Epidemics.DFS.queried_of_mem_done_of_mem_unvisited
- Epidemics.DFS.stack_chain_ofAnswers
- Epidemics.DFS.length_stack_le
- Epidemics.DFS.count_true_le_card
- Epidemics.DFS.card_union_append_le
- Epidemics.DFS.reachable_of_mem_comp
- Epidemics.DFS.count_drop_le_card_comp
- Epidemics.DFS.exists_of_epochs_lt
\(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|\).
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\)).
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.
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.
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.
\(\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\).
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]\).
\(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 \).
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\).)
With the same calls, the PUSH–PULL informed set contains the PUSH and the PULL informed sets after every number of rounds.
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 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}\).
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)]\).
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.)
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\).
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)\).
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\).
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).
- Epidemics.Revisited.push_expect_card_le
- Epidemics.Revisited.push_expect_uninformed
- Epidemics.Revisited.push_growth_lower
- Epidemics.Revisited.pull_expect_card_le
- Epidemics.Revisited.pull_expect_uninformed
- Epidemics.Revisited.pull_growth_lower
- Epidemics.Revisited.pushPull_expect_card_le
- Epidemics.Revisited.pushPull_expect_uninformed
- Epidemics.Revisited.pushPull_growth_lower
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\).
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\)).
- Epidemics.Revisited.push_informProb
- Epidemics.Revisited.pull_informProb
- Epidemics.Revisited.pushPull_informProb
- Epidemics.Revisited.push_homogeneous
- Epidemics.Revisited.pull_homogeneous
- Epidemics.Revisited.pushPull_homogeneous
- Epidemics.Revisited.push_cov_nonpos
- Epidemics.Revisited.pull_cov_eq_zero
- Epidemics.Revisited.pushPull_cov_nonpos
- Epidemics.Revisited.push_upperGrowth
- Epidemics.Revisited.push_upperShrinking
- Epidemics.Revisited.pull_upperGrowth
- Epidemics.Revisited.pull_upperDoubleShrinking
- Epidemics.Revisited.pull_fastFinishing
- Epidemics.Revisited.pushPull_upperGrowth
- Epidemics.Revisited.pushPull_upperDoubleShrinking
- Epidemics.Revisited.pushPull_fastFinishing
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.
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\).
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\).
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\).
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.
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 \).
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 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.
- Epidemics.bipsSourceStep
- Epidemics.cobraStopStep
- Epidemics.cobraStopped
- Epidemics.bipsKernel
- Epidemics.cobraStopStep_inter_eq_empty_iff
- Epidemics.cobraStopped_eq_ofStep
- Epidemics.cobra_bips_dual
- Epidemics.cobra_bips_duality_hitProb
- Epidemics.not_mem_foldl_cobraStopStep
- Epidemics.foldl_bipsSourceStep
- Epidemics.cobra_bips_duality_of_dual
\(\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.
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\).
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)}\).
- Epidemics.KermackMcKendrick.IsSolution.sum_eq_one
- Epidemics.KermackMcKendrick.IsSolution.s_pos
- Epidemics.KermackMcKendrick.IsSolution.i_pos
- Epidemics.KermackMcKendrick.IsSolution.r_nonneg
- Epidemics.KermackMcKendrick.IsSolution.strictAntiOn_s
- Epidemics.KermackMcKendrick.IsSolution.strictMonoOn_r
- Epidemics.KermackMcKendrick.IsSolution.s_eq_mul_exp
\(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]\).
- Epidemics.KermackMcKendrick.IsSolution.tendsto_i
- Epidemics.KermackMcKendrick.IsSolution.exists_tendsto_s
- Epidemics.KermackMcKendrick.IsSolution.tendsto_r
- Epidemics.KermackMcKendrick.IsSolution.final_size
- Epidemics.KermackMcKendrick.IsSolution.limit_pos
- Epidemics.KermackMcKendrick.IsSolution.R₀_mul_limit_lt_one
- Epidemics.KermackMcKendrick.IsSolution.final_size_unique
- Epidemics.KermackMcKendrick.IsSolution.final_size_unique_of_le_one
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\).
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]\).
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\).
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.
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\).
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.
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\).
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\).
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.
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).
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\).
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).
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\).
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\).
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.
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 }))\).
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.