# Each member of a population dies with probability $\frac12$ each day, what is the probability that there will be exactly $1$ person alive?

Suppose that there are $n$ people alive in a population. Due to a deadly disease, each person dies with probability $\frac12$ each day (and there are no births). What is the probability that there will be exactly one person alive at some time?

Thoughts:

Let $p_k$ be the probability that the population reaches exactly $1$ person given that there are currently $k$ people alive. Then $p_0 = 0$ and $p_1 = 1$.

The probability of going from $k$ people alive to $k - j$ being alive (where $0 \leq j \leq k$) is the probability that $j$ die: $$\binom{k}{j} \left(\frac{1}{2}\right)^j \left(\frac{1}{2}\right)^{k - j} = \binom{k}{j} \left(\frac{1}{2}\right)^k$$ And using conditional probability we have the recursion: $$p_k = \frac{1}{2^k} \binom{k}{0} p_k + \frac{1}{2^k} \binom{k}{1} p_{k - 1} + \cdots + \frac{1}{2^k} \binom{k}{k - 1} p_1 + \frac{1}{2^k} \binom{k}{k} p_0,$$ or $$(2^k - 1)p_k = \binom{k}{1} p_{k - 1} + \cdots + \binom{k}{k - 1} p_1.$$ Is it possible to solve a recursion like this? Is there a better way to solve the puzzle?

• Where did you encounter this problem? – Brian Tung Aug 1 '18 at 19:53
• I find it converges to something like $0.7213$ – Ross Millikan Aug 1 '18 at 20:53
• @RossMillikan: This is $\frac1{2\log2}$, and we can get this by approximating Brian's sum by an integral. – joriki Aug 1 '18 at 21:02
• @KeithBackman: That is a valid representation of the question, if I understand you correctly, but $n$ is not then a red herring. The result is $2/3$ when $n = 2$, and $5/7$ when $n = 3$, for example. As joriki pointed out, there is a simple limiting value, but it is approached—it is not a constant for all $n$. – Brian Tung Aug 1 '18 at 21:15
• @BrianTung I imagine he watched Avengers: Infinity War and wondered what would happen if that was a daily occurrence. – mbomb007 Aug 1 '18 at 21:20

Partial solution. First find the probability that one specific person is the unique last survivor, then multiply by $n$.

Omegaman is the last to die on the $k+1$st day with probability

$$p_k = \frac{1}{2^{k+1}} \left(1-\frac{1}{2^k}\right)^{n-1}$$

so then the desired probability is

\begin{align} q & = n\sum_{k=1}^\infty p_k \\ & = n\sum_{k=1}^\infty \frac{1}{2^{k+1}} \left(1-\frac{1}{2^k}\right)^{n-1} \\ & = \frac{n}{2} \sum_{k=1}^\infty \frac{1}{2^k} \left(1-\frac{1}{2^k}\right)^{n-1} % & = \frac{n}{2} % \sum_{k=1}^\infty \frac{1}{2^k} % \sum_{j=0}^{n-1} \binom{n-1}{j}\left(-\frac{1}{2^k}\right)^j \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j % \sum_{k=1}^\infty \left(\frac{1}{2^k}\right)^{j+1} \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j % \sum_{k=1}^\infty \left(\frac{1}{2^{j+1}}\right)^k \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j % \frac{\frac{1}{2^{j+1}}}{1-\frac{1}{2^{j+1}}} \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j \frac{1}{2^{j+1}-1} \end{align}

Still working out if there's a closed-form expression for this. I will point out that we can obtain

$$q = \frac{n}{2} \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j \frac{1}{2^{j+1}-1}$$

if that counts as closed.

• Discouragingly, the sequence $1, 2, 15, 228, 7065, \ldots$, which describes the numerators for the probabilities for increasing $n$ when the denominators are $1, 3, 21, 315, 9765, \ldots$—the former series is not in OEIS, while the latter is. – Brian Tung Aug 1 '18 at 21:13
• The final formula for $q$ is obtained by applying the binomial theorem to the formula above it I assume. To answer your earlier question, I encountered this problem when a colleague said they had attended a quiz and a prize was assigned to a random player by everyone standing up and tossing a coin until they got a head, and the last player left standing was the winner. Since no winner is guaranteed, he was interested to know the chance of a winner existing. – Alex Aug 1 '18 at 22:47

I believe Brian has solved the problem as far as it can be solved for finite $n$. But my skepticism about finding a closed form for the limit for $n\to\infty$ was unwarranted. Approximating Brian's sum by an integral for large $n$, we find

\begin{eqnarray*} q &=& \frac n2\sum_{k=1}^\infty\frac1{2^k}\left(1-\frac1{2^k}\right)^{n-1} \\ &\approx& \frac n2\int_0^\infty2^{-x}\left(1-2^{-x}\right)^{n-1}\mathrm dx \\ &=& \frac n2\int_0^1u(1-u)^{n-1}\frac{\mathrm du}{u\ln2} \\ &=& \frac n{2\ln2}\int_0^1(1-u)^{n-1}\mathrm du \\ &=& \frac1{2\ln2} \\ &\approx& 0.7213\;, \end{eqnarray*}

in agreement with Ross's numerical results.

We can also ask how this limit depends on the survival probability $r$, which is $r=\frac12$ in the question. For $r=0$ we have $q=0$, and for $r\to1$ we should have $q\to1$. In general, for large $n$,

\begin{eqnarray*} q &=& n(1-r)\sum_{k=1}^\infty r^k\left(1-r^k\right)^{n-1} \\ &\approx& n(1-r)\int_0^\infty r^x\left(1-r ^x\right)^{n-1}\mathrm dx \\ &=& n(1-r)\int_0^1u(1-u)^{n-1}\frac{\mathrm du}{-u\ln r} \\ &=& \frac{r-1}{\ln r}\;. \end{eqnarray*}

Here's a plot.

The probability increases very rapidly around $r=0$; for $r=0.01$ we already have $q\approx0.215$.

• Could you please round out your answer so it doesn't rely on another person's answer? It'd be nice if I didn't have to view two partial answers to see a "complete" answer. – mbomb007 Aug 1 '18 at 21:23
• @mbomb007: No, I don't want to copy his answer -- I added a link to it. – joriki Aug 1 '18 at 21:35
• So it turns out that this problem has been addressed in some published papers and it turns out that it doesn't converge as $n \rightarrow \infty$. It oscillates around a constant but never converges. The quote in the comment below is from "The Asymptotics of Group Russian Roulette" by Van de Brug, Kager and Meester arxiv.org/abs/1507.03805 – Alex Aug 6 '18 at 20:10
• "A number of papers [2–4, 6, 8–11] study the following related problem and generalizations thereof. Suppose we have $n$ coins, each of which lands heads up with probability $p$. Flip all the coins independently and throw out the coins that show heads. Repeat the procedure with the remaining coins until 0 or 1 coins are left. The probability of ending with 0 coins does not converge as $n \rightarrow \infty$ and becomes asymptotically periodic and continuous on the $\log n$ scale [6, 11]." – Alex Aug 6 '18 at 20:10

Here's a look at the problem using a generating function. As you point out, we have for $k > 1$: $$p_k = \frac{1}{2^k}\sum_{j=0}^k \binom{k}{j} p_j$$ Note that this is off by $\frac12$ when $k=1$. We define $f(z)$ to be the exponential generating function for $p_k$: $$f(z) = \sum_{k=0}^\infty \frac{p_k}{k!} z^k$$ Then we observe: $$f(\frac z2)e^{\frac z2} + \frac{z}{2} = \sum_{k=0}^\infty \left(\sum_{j=0}^k \frac{p_j}{j!(k-j)!}\right)\left(\frac{z}{2}\right)^k + \frac{z}{2} = f(z)$$ This gives us a recursion formula for $f(z)$. Inductively, we can see $$f(z) = \frac{z}{2} + f(\frac z2)e^{\frac z2} = \frac{z}{2} + \frac{z}{4}e^{\frac{z}{2}} + f(\frac z4)e^{\frac {3z}4} = ... = \sum_{n=0}^{N-1} \frac{z}{2^{n+1}} e^{\frac{2^n - 1}{2^n} z} + f(\frac{z}{2^N}) e^{\frac{2^N - 1}{2^N} z}$$ Taking the limit as $N$ goes to infinity and recalling that $f(0) = p_0 = 0$, we determine: $$f(z) = \sum_{n=0}^{\infty} \frac{z}{2^{n+1}} e^{\frac{2^n - 1}{2^n} z} =\frac{z e^z}2 \sum_{n=0}^\infty \frac{e^{-2^{-n} z}}{2^n}$$ Thus we have $p_n = f^{(n)} (0)$ which works out to agree with the other answers: $$p_n = f^{(n)}(0) = \frac{n}{2}\sum_{k=1}^\infty 2^{-k}\left(1 - 2^{-k}\right)^{n-1}$$ Note that this is increasing in $n$, and bounded above by $1$, hence it converges.

Now we show that $\lim p_k = \frac1{2\log 2}$. Notice that the sum $\sum_{n=0}^\infty \frac{e^{-2^{-n} z}}{2^n}$ is a left Riemann sum with interval divisions of length $1$ of the integral $\int_0^\infty 2^{-x} e^{-2^{-x} z} dx$, which evaluates to $\frac{1 - e^{-z}}{z\log 2}$. Call the integrand $g(x)$. Notice that $g(x)$ is increasing for $x < \log_2{z}$ and decreasing for $x > \log_2{z}$. Thus, for the smaller $x$, the integral underestimates the sum, and for the larger $x$, it overestimates. Changing to a right Riemann sum switches the over/underestimation but since all terms in the series go to $0$ exponentially as $z$ goes to infinity this doesn't change the asymptotics of the overall sum in $z$. Hence the sum and the integral are asymptotically equivalent. We therefore can conclude $$f(z) \sim \frac{e^z}{2\log 2}$$ which implies that if $p_n$ converges to a limit, it must converge to $\frac1{2\log 2}$. Since we have already established that $p_n$ is convergent, this shows that indeed $\lim\limits_{n\rightarrow\infty} p_n = \frac1{2\log2}$.

This is as far as I can get ...

Another possible approach would be to reason that after $k$ days, the probability of any particular person being alive is $2^{-k}$ and the probability of being dead is $(1-2^{-k})$ so the probability that exactly one person is alive after $k$ days is given by ... $$P_k =n( 1-2^{-k})^{n-1}2^{-k} \\= n(2^k -1)^{n-1}2^{-nk}$$

your final probability will be $$P=\sum_{k=0}^\infty P_k$$ $$P= n\sum_{k=0}^\infty \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j 2^{(j-n)k } \\ = n\sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j \sum_{k=0}^\infty 2^{(j-n)k } \\ =n \sum_{j=0}^{n-1}\dfrac{ (-1)^j \binom{n-1}{j} }{ 1-2^{j-n} }$$

• I think you're counting each day that someone is alive on their own as a separate contribution, whereas only the first day should count? For instance, for $n=1$, you get $P=2$. – joriki Aug 1 '18 at 20:47
• I think @joriki is right. I haven't checked it properly but intuitively you just need to multiply your result by $1/2$ so that $P_k$ is the probability that only one person is alive at time $k$ and none is alive at time $k+1$. – Luca Citi Aug 1 '18 at 22:49