Modelling bacterial extinction

This week’s Riddler Classic poses a question about bacteria (paraphrased for brevity):

Each bacterium in a colony splits into two copies with probability \(p\) and dies with probability \((1-p)\). If the colony starts with one bacterium, what is the probability that the colony survives forever?

We can model the colony’s size as a Galton-Watson process. Let \(X_t\) be the colony’s size in generation \(t\in\{1,2,\ldots\}\) and let \(Y_{it}\) be the number of offspring generated by bacterium \(i\in\{1,2,\ldots,X_t\}\). The \(Y_{it}\) are independently and identically distributed, with $$\Pr(Y_{it}=y)=\begin{cases} p & \text{if}\ y=2 \\ 1-p & \text{if}\ y=0 \\ 0 & \text{otherwise} \end{cases}$$ for each \(i\) and \(t\). The colony’s size grows according to $$X_{t+1}=\sum_{i=1}^{X_t}Y_{it}$$ with \(X_1=1\). Our goal is to compute $$\lim_{t\to\infty}\Pr(X_t>0)=1-\lim_{t\to\infty}q_t,$$ where \(q_t\equiv\Pr(X_t=0)\) is the probability that the colony is extinct by generation \(t\).

We can compute \(q_t\) by conditioning on \(Y_{11}\), the number of offspring generated by the first bacterium. If \(Y_{11}=0\) then the colony is extinct from the second generation onwards. However, if \(Y_{11}=2\) then there are two sub-colonies in the second generation that must be extinct in \((t-1)\) generations if the whole colony is extinct by generation \(t\). These sub-colonies grow independently, so the probability that both are extinct in \((t-1)\) generations is \(q_{t-1}^2\). Thus, by the law of total probability, we have $$\begin{align} q_t &= \Pr(X_t=0\,\vert\,Y_{11}=0)\Pr(Y_{11}=0)+\Pr(X_t=0\,\vert\,Y_{11}=2)\Pr(Y_{11}=2) \\ &= 1\times(1-p)+q_{t-1}^2\times p \\ &= 1-p+pq_{t-1}^2 \end{align}$$ for \(t\ge2\). Defining \(q\equiv\lim_{t\to\infty}q_t\) and taking limits as \(t\to\infty\) gives¹ $$q=1-p+pq^2,$$ which has solutions $$\begin{align} \newcommand{\abs}[1]{\lvert#1\rvert} q &= \frac{1\pm\sqrt{1-4p(1-p)}}{2p} \\ &= \frac{1\pm\sqrt{(2p-1)^2}}{2p} \\ &= \frac{1\pm\abs{2p-1}}{2p}. \end{align}$$ The larger solution exceeds unity when \(p<0.5\), which we cannot have because \(q\) is a probability. Thus $$\lim_{t\to\infty}\Pr(X_t>0)=1-\frac{1-\abs{2p-1}}{2p}.$$ For example, if \(p=0.8\) then the colony survives forever with probability $$1-\frac{1-\abs{2\times0.8-1}}{2\times0.8}=0.75.$$ If \(p<0.5\) then extinction is guaranteed because each bacterium generates fewer than one offspring on average.