Adjacency-matrix bound for a discrete SIR epidemic ($\mathrm{Pr}(i\text{ ever infected})\le {\sum }_{k\ge 0}[(\beta A{)}^{k}X(0){]}_i$)

The conditional union bound gives $\mathbb{E}{X}_i(k+1)\le \beta {\sum }_j{A}_{ij}\mathbb{E}{X}_j(k)$ in a discrete SIR epidemic on a graph. Iteration bounds the infection vector at step $k$ by $(\beta A{)}^{k}X(0)$. Each vertex is infected at most once, so summing the probabilities in time gives the displayed bound. Powers of the adjacency matrix of a graph count walks, which can overcount impossible reinfections without invalidating the upper bound. Initially removed individuals must be counted separately when bounding all eventual removals.