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

Use the compartment counts $Z_n=(S_n,I_n,R_n)$ as the state of the SIRS Markov chain. Its state space is $\{(S,I,R)\in {\mathbb{Z}}_{\ge 0}^3:S+I+R=n\}$. The transition rates areEach susceptible has infection hazard $\lambda I/n$, so summing over the $S$ susceptibles gives the first rate. The memorylessness of the exponential distribution makes each of the $I$ current infectives have recovery hazard $\gamma$, irrespective of its infection time. Each removed individual has immunity-loss hazard $\nu$. These are all the possible off-diagonal transitions. The diagonal entry of the transition intensity matrix is minus their sum, and a transition with no eligible individual has rate zero. Thus the three total event rates are $\lambda SI/n$, $\gamma I$ and $\nu R$, and every event conserves population size.

Scale the SIRS Markov chain by population size: $U_n=Z_n/n=(s_n,i_n,r_n)$. Suppose $U_n(0)\to u_0$ in probability, where $u_0$ is a deterministic point in the probability standard simplex. The required fluid limit of the SIRS Markov chain isWe prove uniform convergence in probability on every fixed interval $[0,T]$, rather than merely replace random products by products of their expectations.

Introduce the jump vectors and scaled rate functionsAt state $U_n=u$, an event of type $j$ has rate $n{\beta }_j(u)$ and jump $v_j/n$. Let $N_1,N_2,N_3$ be independent unit-rate Poisson processes. The Poisson time-change representation of a Markov chain givesThis representation follows by giving each event type an independent exponential clock in its accumulated hazard. Conditional on the current state its firing rate is $n{\beta }_j$, hence it has exactly the transition rates from part (a). The finite state space and bounded rates rule out explosion. Values at the jump times do not affect the time integrals.

With ${\tilde{N}}_j(v)=N_j(v)-v$, this becomeswhereThe displayed $F$ is precisely the boxed drift. On the simplex, ${\beta }_j\le b_j$ with $b_1=\lambda$, $b_2=\gamma$, $b_3=\nu$. Thus every Poisson clock used before $T$ is at most $n{b}_{j}T$. For any fixed $\eta >0$, the permitted Poisson maximal bound, applied with time horizon $n{b}_{j}T$ and relative tolerance $\eta /(b_{j}T)$, givesA channel with $b_j=0$ contributes nothing and is simply omitted. Since $h(a)>0$ for $a>0$, these probabilities even decrease exponentially in $n$. Each $v_j$ has ${\ell }^1$ norm two. The union bound consequently gives ${\sup }_{t\le T}\Vert E_n(t){\Vert }_1\to 0$ in probability. Notice that the clock is random, but its deterministic upper bound makes the Poisson maximal estimate directly applicable.

The drift $F$ is Lipschitz on the simplex. Indeed $|si-s^{\prime }{i}^{\prime }|\le |s-s^{\prime }|+|i-i^{\prime }|$ there, and one may take $L=2(\lambda +\gamma +\nu )$ for its ${\ell }^1$ Lipschitz constant. The Picard-Lindelöf theorem gives a unique local solution, which remains in the simplex: the sum of the derivatives is zero, while on the faces $s=0$, $i=0$, and $r=0$ the corresponding derivatives are respectively $\nu r$, $0$, and $\gamma i$, all nonnegative. More explicitly, $i(t)=i(0)\exp ({\int }_0^t(\lambda s(a)-\gamma )da)$ is nonnegative, and the linear equations for $r$ and $s$ have nonnegative forcing terms; their integrating-factor formulas keep both nonnegative. Conservation then bounds every coordinate by one, so the local solution extends globally.

Subtract its integral equation from that of $U_n$. The Gronwall inequality yieldsThis proves the Poisson concentration proof of a density-dependent fluid limit for this model, including the initial-condition requirement and uniform finite-time approximation. In terms of population counts, the associated deterministic approximation is $\dot{S}=-\lambda SI/n+\nu R$, $\dot{I}=\lambda SI/n-\gamma I$, $\dot{R}=\gamma I-\nu R$. The limit concerns macroscopic initial proportions and fixed times; a single initial infective has limiting fraction zero, so early stochastic invasion on a growing time scale is not described by this finite-time limit alone.

Count each unordered $k$-vertex set once. For each such set $A$, let $I_A$ be its clique indicator in the binomial random graph. All $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ required edges are independent, soThe Markov inequality, or first moment method, givesConsequentlyThis argument works even if $k=k(n)$ varies. The binomial coefficient shows that cliques are counted as vertex sets, not as their different ordered listings.

Expand $X^2={\sum }_{A,B}{I}_A{I}_B$, where the sum is over ordered pairs of $k$-sets. If $|A\cap B|=l$, the two cliques together require $2\left(\genfrac{}{}{0ex}{}{k}{2}\right)-\left(\genfrac{}{}{0ex}{}{l}{2}\right)$ different edges: precisely the edges within the overlap are counted twice. ThereforeThere are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ choices of $A$, then $\left(\genfrac{}{}{0ex}{}{k}{l}\right)$ ways to choose the overlap and $\left(\genfrac{}{}{0ex}{}{n-k}{k-l}\right)$ ways to choose the remaining vertices of $B$. It follows thatA binomial coefficient is zero when its lower argument is outside its possible range. The term $l=k$ includes $A=B$ and equals $\mathbb{E}X$, as it should.

Now take the usual fixed-$k$ interpretation of the appearance assertion. For $k=1$, $X=n$ deterministically. For fixed $k\ge 2$, the assumption ${\mu }_n\to \infty$ givessince ${\mu }_n\sim a_n^k/k!$. Eventually $p>0$. Subtracting ${\mu }_n^2$ in the second-moment formula, and using the identity that the overlap counts sum to the total number of ordered pairs, gives the overlap formula for the variance of a clique count:Overlaps of zero or one vertex have no shared edge and hence independent indicators, so their contributions vanish. For fixed $k$, the combinatorial coefficient in the $l$-th summand is $O_k(n^{-l})$. Moreover, because $p\le 1$ and $l\le k$,There are only finitely many terms. Thus $\mathrm{Var}X/{\mu }_n^2\to 0$. The Chebyshev inequality then givesproving the fixed-size clique appearance threshold:

The fixed-size condition cannot simply be dropped. For $k=n-1$ and $p=1-(\log n)/n^2$,However the complement graph has a binomial number $J$ of missing edges with mean asymptotic to $\frac{1}{2}\log n$ and variance at most that mean. By the Chebyshev inequality, $\mathbb{P}(J\ge 2)\to 1$. Conditional on $J\ge 2$, choose two distinct missing edges uniformly; their endpoints are disjoint except with probabilityThus with probability tending to one the complement has two disjoint edges. Deleting one vertex cannot remove both, so no $(n-1)$-clique exists. In this example $\mathbb{P}(X\ge 1)\to 0$, despite ${\mu }_n\to \infty$. This is growing clique size can invalidate a first-moment appearance criterion; the exact second-moment identity remains valid for growing $k$, but the stated conclusion needs the conventional fixed-$k$ quantifier.

Let $\mathcal{T}$ be the set of three-vertex subsets and let $I_A$ indicate that $A$ forms a triangle. ThenIn particular $p\sim (6\alpha {)}^{1/3}/n$. We will use the Stein-Chen method with edge-sharing dependency neighborhoods, rather than wrongly treating triangle indicators as mutually independent.

Here is the needed Poisson approximation with dependency neighborhoods, together with its proof. For indicators $I_A$ with means $p_A$, let $B_A$ contain $A$ and suppose $I_A$ is independent of the entire family of indicators outside $B_A$. With $\mu ={\sum }_A{p}_A$ and $W={\sum }_A{I}_A$, defineThe total variation distance convention is $d_{TV}(P,Q)={\sup }_E|P(E)-Q(E)|$. We claimFor an indicator test function $g$ on the nonnegative integers, solve the Poisson Stein equationwith $\Vert \Delta f{\Vert }_{\infty }\le 1$. This elementary Stein factor can be proved as follows. Take the immigration--death process with immigration rate $\mu$ and per-particle death rate one. Starting at $k$, its time-$t$ distribution iswith independent summands. Its stationary law is that of $Z$. Coupling the initial particles with a stationary Poisson initial population makes the centered expectations decay at least as a constant times $(k+\mu )e^{-t}$, sois finite. Its generator equation is $\mu (u(k+1)-u(k))+k(u(k-1)-u(k))=g(k)-\mathbb{E}g(Z)$, obtained by integrating the semigroup derivative. Set $f(k)=u(k)-u(k-1)$ for $k\ge 1$; choose $f(0)=f(1)$, which does not affect the equation. To bound $\Delta f(k)$, couple the processes starting at $k-1,k,k+1$ by adding two independent initial particles. Both survive to time $t$ with probability $e^{-2t}$, and otherwise their second difference cancels in expectation. Since $|g(j+2)-2g(j+1)+g(j)|\le 2$,This proves the Stein factor for $k\ge 1$, and the chosen $f(0)$ handles $k=0$.

Put $W_A=W-{\sum }_{C\in B_A}{I}_C$. Independence gives $\mathbb{E}[I_{A}f(W_A+1)]=p_A\mathbb{E}f(W_A+1)$. Inserting this identity into the Stein equation yieldsThe first sum in absolute value is at most $b_1$, since the two arguments differ by ${\sum }_{C\in B_A}{I}_C$. In the second sum, on $I_A=1$ the arguments differ by ${\sum }_{C\in B_A\setminus \{A\}}{I}_C$, giving bound $b_2$. Taking the supremum over event indicators $g$ proves the claimed total variation distance bound.

For triangle $A$, choose $B_A$ to consist of $A$ itself and all triangles sharing an edge with $A$. There are exactly $1+3(n-3)$ such triangles. Every outside triangle uses none of the three edges of $A$, even if it shares one vertex, so $I_A$ is independent of their entire indicator family. For distinct neighboring triangles, their union has five edges and $\mathbb{E}(I_A{I}_C)=p^5$. ThereforeThe Stein-Chen method gives $d_{TV}(\mathcal{L}(X),\mathrm{Poisson}({\mu }_n))\to 0$. Coupling Poisson distributions of two means by adding an independent Poisson variable givesThis proves the Poisson limit for triangles in a binomial random graph:Applying the same bound to the event $\{1,2,\dots \}$ givesFor finite $n$ this is an approximation, not an exact formula: the error from $1-e^{-{\mu }_n}$ is at most $b_1+b_2$, and the error from $1-e^{-\alpha }$ is at most $b_1+b_2+|{\mu }_n-\alpha |$.

The exponent printed in the original PDF is too strong under the stated increment bound. Take $M_0=0$, let $M_1$ equal $1$ or $-1$ with equal probabilities, and set $M_k=M_1$ for $k\ge 1$. This is a martingale with $c_1=1$ and $c_k=0$ for $k>1$. For $n=1$ and $x=1$,Thus the printed inequality is false. The intended two-sided Azuma-Hoeffding inequality isHere the $c_k$ are deterministic increment bounds. We prove this corrected assertion from conditional exponential moments.

Let $D_k=M_k-M_{k-1}$. The martingale property gives $\mathbb{E}[D_k\mid {\mathcal{F}}_{k-1}]=0$. For $c_k>0$, convexity of the exponential function gives the secant bound on $[-c_k,c_k]$,Taking conditional expectation removes the terms containing $D_k$, soThe last inequality follows term by term from $(2j)!\ge 2^{j}j!$ in the power series for $\cosh z$ and $e^{z^2/2}$. If $c_k=0$ the increment is zero and the same bound holds directly. This is the bounded-increment case of the Hoeffding lemma.

Repeated conditioning, without any independence assumption, now givesWrite $C={\sum }_{k=1}^n{c}_k^2$. If $C>0$, the Markov inequality gives for $\theta >0$,Minimizing at $\theta =x/C$ gives $e^{-x^2/(2C)}$. Apply the same argument to the martingale $-M$ for the lower tail, and use the union bound to obtain the boxed result. If $C=0$, all increments vanish almost surely, so the deviation probability is zero for every $x>0$. This handles the degenerate case without dividing by zero and proves the correct bound in full.