Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / B / 6

Explore the individuals one at a time, maintaining the number of discovered but unprocessed individuals. It starts at $S_0=1$. Processing one individual removes it and adds its offspring, soThe offspring choices make these increments independent. Exploration stops when the queue first becomes empty; every processed individual has then been counted exactly once. Hencewith $K=\infty$ if the walk never hits zero. The increment sequence can be extended independently beyond the stopping time for probability estimates.

The event $K=k$ implies $S_k=0$. If $B_k$ counts the positive increments, then $B_k\sim \mathrm{Bin}(k,p)$ and $S_k=1+2B_k-k$. Let $\delta =|p-1/2|>0$.

For $p>1/2$, $S_k=0$ forces $B_k=(k-1)/2\le k/2$, so the lower-tail Hoeffding form of the Chernoff bound givesFor $p<1/2$ and $k\ge 1/\delta$, the required value is at least $kp+\delta k/2$. The upper-tail bound gives $\mathbb{P}(K=k)\le e^{-{\delta }^{2}k/2}$.

To include all smaller positive integers, note that each finite-time atom has probability strictly less than one: at $k=1$ its probability is $1-p<1$, while for $k>1$ immediate extinction already has positive probability and excludes $K=k$. Over the finitely many small $k$ with nonzero atom, take the minimum of $-k^{-1}\log \mathbb{P}(K=k)$ and the applicable tail constant. This minimum is positive, and zero atoms impose no restriction. Thus for both cases there is $c>0$ such thatIn the supercritical case this bounds the finite atoms, not the positive probability of $K=\infty$.

Let $Z_r$ be the size of generation $r$, with $Z_0=1$. Its offspring mean is $2p$, so conditioning on the previous generation gives $\mathbb{E}{Z}_r=(2p{)}^r$. At $p=1/2$,The interchange uses Tonelli's theorem for nonnegative variables. Critical extinction is nevertheless almost sure: its probability is the smallest root in $[0,1]$ of $s=(1+s^2)/2$, whose only root is one. Hence $K$ is finite almost surely. If all its finite atoms had the exponential bound, then $\mathbb{E}K\le {\sum }_{k\ge 1}k{e}^{-ck}<\infty$, a contradiction.

For $p>1/2$ the extinction probability is $(1-p)/p<1$. There is positive mass at $K=\infty$, so the mean is infinite even if every finite atom decays exponentially. This is precisely why the critical contradiction does not extend to the supercritical case.