14
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Where did you encounter this problem? $\endgroup$ – Brian Tung Aug 1 '18 at 19:53
  • 2
    $\begingroup$ I find it converges to something like $0.7213$ $\endgroup$ – Ross Millikan Aug 1 '18 at 20:53
  • 1
    $\begingroup$ @RossMillikan: This is $\frac1{2\log2}$, and we can get this by approximating Brian's sum by an integral. $\endgroup$ – joriki Aug 1 '18 at 21:02
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian Tung Aug 1 '18 at 21:15
  • 1
    $\begingroup$ @BrianTung I imagine he watched Avengers: Infinity War and wondered what would happen if that was a daily occurrence. $\endgroup$ – mbomb007 Aug 1 '18 at 21:20
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brian Tung Aug 1 '18 at 21:13
  • $\begingroup$ 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. $\endgroup$ – Alex Aug 1 '18 at 22:47
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mbomb007 Aug 1 '18 at 21:23
  • $\begingroup$ @mbomb007: No, I don't want to copy his answer -- I added a link to it. $\endgroup$ – joriki Aug 1 '18 at 21:35
  • $\begingroup$ 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 $\endgroup$ – Alex Aug 6 '18 at 20:10
  • $\begingroup$ "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]." $\endgroup$ – Alex Aug 6 '18 at 20:10
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – joriki Aug 1 '18 at 20:47
  • $\begingroup$ 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$. $\endgroup$ – Luca Citi Aug 1 '18 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.