Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 36 (Spread of Epidemics and Rumours)

In the SI model, one infection reduces the susceptible count by one, and the total event rate is $\lambda X(t)Y(t)/n=nb(X_n(t))$, where $b(u)=\lambda u(1-u)$. The Poisson time-change representation of a Markov chain therefore giveswhere $N_n$ is a unit-rate Poisson process. Subtracting its clock from its count givesThus $X_n(t)=a-{\int }_0^{t}b(X_n(s))ds-{\epsilon }_n(t)$. The clock stops when the susceptible count reaches zero, so the representation also includes the absorbing state.

Fix $T>0$ and put $K=\lambda T/4$. Since $0\le X_n\le 1$, the clock in part (a) is at most $nK$ on $[0,T]$. The Poisson maximal concentration bound gives, for every $\delta >0$,Here $h(u)>0$ for $u>0$, so the probabilities are summable in $n$. The Borel-Cantelli lemma, first for positive rational $\delta$ and then for all $\delta$, yields ${\sup }_{t\le T}|{\epsilon }_n(t)|\to 0$ almost surely. No independence between the processes for different population sizes is required.

The deterministic SI model solves the logistic equation $x^{\prime }=-\lambda x(1-x)$ with $x(0)=a$, givingOn $[0,1]$, $b$ is Lipschitz continuous with constant $\lambda$. Subtracting the two integral equations givesThe Gronwall inequality impliesThis is the uniform almost-sure fluid limit of the SI model. One can take the intersection of the probability-one events for integer $T$ to obtain the conclusion on every finite interval. Use population sizes with $an$ integral; if the initial susceptible count is rounded, the extra initial error is at most $1/n$ and the same Gronwall inequality proof applies.

Write $q=1-p$. A disconnected graph has a connected component of a graph of size $1\le s\le \lfloor n/2\rfloor$. For a fixed $s$-element vertex set $S$, all $s(n-s)$ edges between $S$ and its complement must be absent. Their independent absence has probability $q^{s(n-s)}$. The union bound givesSet $r_n=n{q}^{n/2}$. Since $p$ is fixed in $(0,1)$, $r_n\to 0$. For large $n$, the final sum is at most the geometric series $r_n/(1-r_n)$, which tends to zero. Hence the binomial random graph is connected with probability tending to one, as in connectivity of a fixed-density binomial random graph.

For a nonnegative integer-valued random variable, $1_{\{X>0\}}\le X$ pointwise. Taking expectations givesThis is the indicator form of the Markov inequality.

Let $I_{ij}$ be the indicator random variable that the unordered vertex pair $\{i,j\}$ has no common neighbour. For each of the other $n-2$ vertices, the two required edges are both present with probability $p^2$. The edge pairs for different candidate neighbours are disjoint sets of independent random choices. Thus $\mathbb{E}{I}_{ij}=(1-p^2{)}^{n-2}$. Linearity of expectation yieldsthe missing common-neighbour count in a binomial random graph.

If $X=0$, every pair of vertices has a common neighbour, so every pair has graph distance at most two. In particular the graph is connected and its graph diameter is at most two. By the Markov inequality and part (ii),We include disconnected graphs among those with diameter greater than two. Thereforeby diameter bound for a fixed-density binomial random graph.

Each unordered triple of vertices is a triangle in a graph with probability $p^3$. Consequently the triangle count in a binomial random graph satisfies $\mathbb{E}X=\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3\le (np{)}^3/6$. If $np\to 0$, the Markov inequality gives $\mathbb{P}(X>0)\le \mathbb{E}X\to 0$. Hencethe sparse direction of the triangle-existence threshold in a binomial random graph.

Count each unordered triple once. For a three-element vertex set $S$, let $I_S$ indicate that its three edges are present. Then $X={\sum }_{|S|=3}{I}_S$ andIf $|S\cap T|=\ell$, their edge sets have $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ edges in common, so their union contains $6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ distinct edges. Independence gives $\mathbb{E}[I_S{I}_T]=p^{6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)\left(\genfrac{}{}{0ex}{}{3}{\ell }\right)\left(\genfrac{}{}{0ex}{}{n-3}{3-\ell }\right)$ such ordered pairs: choose $S$, its shared vertices, and the remaining vertices of $T$. ThusThis overlap count is the basis of triangle variance in a binomial random graph.

When $\mu =\mathbb{E}X>0$, the event $X=0$ implies $|X-\mu |\ge \mu$. The Chebyshev inequality therefore givesThis is the second moment method for proving that a nonnegative count is positive.

Two distinct triangles in a graph with at most one common vertex use disjoint edges, so their indicator random variables are independent and have zero covariance. A pair sharing an edge has covariance $p^5-p^6$. The count from part (i) givesWith $\mu =\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3$, the triangle variance in a binomial random graph therefore satisfiesBoth terms tend to zero when $np\to \infty$, because $n^{2}p=n(np)\to \infty$. Applying part (ii) provescompleting the triangle-existence threshold in a binomial random graph.

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 givesWrite $u(k)=\mathbb{E}X(k)$. Taking expectations and iterating this componentwise inequality for the nonnegative adjacency matrix of a graph gives $u(k)\le (\beta A{)}^{k}X(0)$.

A vertex is infected at most once, and an infection lasts exactly one step before permanent removal. Hence $Y_i(\infty )={\sum }_{k\ge 0}{X}_i(k)$ under the stated initial convention. The Tonelli theorem now givesThe 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.

Put $Z={\sum }_i{Y}_i(\infty )$ and $1=(1,\dots ,1{)}^T$. Sum the bounds in part (a) over the vertices, using linearity of expectation and the Tonelli theorem for the nonnegative series:The bound remains valid if the series diverges, although it then gives no finite estimate. When the spectral radius of $\beta A$ is less than one, the series is a Neumann series, giving the resolvent bound for a discrete SIR epidemic.

Because $A$ is a real symmetric matrix, the spectral theorem gives $\Vert A{\Vert }_2=\rho (A)$. For $\beta \rho <1$, the Neumann series satisfiesLet $m={\sum }_i{X}_i(0)$ be the initial infected count. Since its entries are indicator random variables, $\Vert X(0){\Vert }_2=\sqrt{m}$, while $\Vert 1{\Vert }_2=\sqrt{n}$. The Cauchy-Schwarz inequality and the operator norm bound yieldThus a sufficient asymptotic condition for a small outbreak isFor example, it holds when $m=o(n)$ and $\beta \rho \le 1-\eta$ for a fixed $\eta >0$. For any fixed $\delta >0$, the Markov inequality then givesThis is the spectral condition for a small discrete SIR outbreak. A uniform gap and few initial infections are needed for this conclusion; the finite-population condition $\beta \rho <1$ alone does not control an asymptotically vanishing gap or an initially macroscopic infected set.