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

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$.