= Solution
Take the initial removed set to be empty, as required by the displayed equality in this <discrete SIR epidemic on a graph>. If initially removed individuals are allowed, add their indicators $Y_i(0)$ to the final-removal count; an isolated initially removed <vertex> already shows why this correction is necessary. Condition on a fixed initial infection vector.
Given the history through time $k$, the <union bound> over currently infected <neighbours> gives
$$
\mathbb E[X_i(k+1)\mid\mathcal F_k]
\leq\beta\sum_jA_{ij}X_j(k).
$$
Write $u(k)=\mathbb E X(k)$. Taking <expectations> and iterating this componentwise inequality for the nonnegative <adjacency matrix of a graph> gives $u(k)\leq(\beta A)^kX(0)$.
A <vertex> is infected at most once, and an infection lasts exactly one step before permanent removal. Hence $Y_i(\infty)=\sum_{k\geq0}X_i(k)$ under the stated initial convention. The <Tonelli theorem> now gives
$$
\boxed{\mathbb P(Y_i(\infty)=1)
=\mathbb P(i\text{ is ever infected})
\leq\sum_{k=0}^\infty\sum_j
\beta^k(A^k)_{ij}X_j(0)}.
$$
The <walk count from powers of an adjacency matrix> explains the terms: all possible transmission <walks> are counted, including <walks> that overcount because removal prevents reinfection. This is the <adjacency-matrix bound for a discrete SIR epidemic>.
Back to article page
