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$$ gives1 $$q=1-p+pq^2,$$ which has solutions \begin{align} \newcommand{\abs}{\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.

1. The function $$x\mapsto x^2$$ is continuous and so preserves limits. ↩︎