Reed–Frost Epidemics and Bond Percolation
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 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 is false as stated; 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.
1 The model
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\).
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 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.
7 The Kermack–McKendrick SIR model
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\).
8 Kurtz’s law of large numbers for SIR, in discrete time
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 24 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 25 bounds the complement by \(6e^{-c\varepsilon ^2N}\). Small \(N\) and \(\varepsilon \ge 2\) are absorbed in \(C\).
9 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.
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 29) bounds the probability of missing a target, and a phase potential on the iterated kernel replaces the paper’s domination by geometric variables. Lemma 30 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 29 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 is false: 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. See FORMALIZATION_DIFFERENCES.md.
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\).
10 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).
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\} \).
11 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.