6
$\begingroup$

Suppose we have a coin flipping game involving $n$ players. In each round everyone still playing flips a fair coin, and the players whose coin comes up tails are eliminated. The game continues until at most one player is still alive, and they are declared the winner.

Now, it is possible that the game does not end with a winner (e.g. if $n=2$ and both players get tails on their first flip). Let $f(n)$ denote the probability that a game with $n$ players has a winner. We have $f(0)=0$ and $f(1)=1$. For $n>1$ it follows from considering the binomial distribution that $$f(n) = \sum_{k=0}^{n}\frac{\binom{n}{k}}{2^{n}} f(k) $$ (Here $\binom{n}{k}/(2^n)$ represents the probability $k$ players survive the current round), which can be rearranged as $$f(n) = \sum_{k=0}^{n-1} \frac{\binom{n}{k}}{2^n-1} f(k)$$ Using this formula we can compute $f(n)$ recursively.
$$\begin{array}{cc} n & f(n) \\ 0 & 0 \\ 1 & 1 \\ 2 & 2/3 \\ 3 & 5/7 \\ 4 & 76/105 \\ 5 & 157/217 \\ \vdots & \vdots \\ 20 & 0.7213 \end{array}$$ The sequence of numerators doesn't seem to be in OEIS, nor does the sequence $a_n=f(n)(2^n-1)(2^{n-1}-1)\dots(3)(1)$ from clearing all the denominators in the recursion.

Is there a way of analytically determine the limit (if it exists) of $f(n)$ as $n$ goes to infinity? It seems from calculation to be about $0.7213$, though I'm not confident in digits beyond that due to error propagation as the recursion continues.

$\endgroup$
4
  • $\begingroup$ It may be $\frac{1}{2\ln(2)}$. This is the only reasonable number in the OEIS that agrees with the first four digits of $0.7213$. $\endgroup$ – Varun Vejalla Aug 9 '19 at 0:05
  • 2
    $\begingroup$ A closed form expression for $\ f(n)\ $ for $\ n\ge 2 $ is $$ f(n)= n2^{-n} + \frac{n}{2}\sum_\limits{k=1}^{n-1}{n-1\choose k}\frac{\left(-1\right)^{k-1}\left(2^k-1\right)}{2^k\left(2^{k+1}-1\right)}\ .$$ $\endgroup$ – lonza leggiera Aug 9 '19 at 6:50
  • $\begingroup$ Could you elaborate on how you obtained the recurrence relation $f(n) = \sum_{k=0}^{n-1} \frac{\binom{n}{k}}{2^n-1} f(k)$? From your description ...represents the probability 𝑘 players survive the current round... it seems that you confused the round of flipping with the "round" of recurrence regarding a change in the remaining number of players. $\endgroup$ – Lee David Chung Lin Aug 15 '19 at 4:13
  • $\begingroup$ Let $A_k$ be the event that exactly $k$ out of the $n$ players get heads. Then we have $$P(\textrm{win}) = \sum_{k=0}^n P(A_k) P (\textrm{win } | A_k).$$ The probability of $A_k$ is $\frac{\binom{n}{k}}{2^n}$, and the probability of winning given $A_k$ is $f(k)$. $\endgroup$ – Kevin P. Costello Aug 15 '19 at 7:11
1
$\begingroup$

The limit of $f(n)$ as $n$ goes to infinity does not exist.

Suppose that $n$ is large. Then we can choose an integer $k$ such that $n = 2^k x$ with $1 \leq x < 2$. What is the probability of winning starting at $n$?

Let us say that we win at step $k+m$ if at step $k+m$ there is only one player, but their next coin flip is tails. That is half the probability that at step $k+m$ there is only one player left. But if $k$ is large, the odds of there being one player left is approximated by the Poisson Distribution with $\lambda = 2^m x$. Therefore the probability of winning is approximately $\sum_{m = -\infty}^{\infty} 0.5 * (2^m x) * e^{- 2^m x}$.

It isn't too hard to see that this sum converges, and it is easy to calculate it with a short program. If we calculate this for $x = 1.0$ we get $0.721352103337$. For $x = 1.5$ we get $0.721346354574$. The difference is around $0.00000574876$ and is far larger than calculation error. And therefore the probability keeps bouncing around in a range that includes these values and so can't converge.

$\endgroup$
11
  • $\begingroup$ Although the values do bounce around a bit, I am 99% certain that $f(n)$ does converge. I checked up to $n = 300$ and found a certain pattern. $f(n)$ increases for a bit, then decreases for a bit. Each time, the interval length gets lowered a bit. For example, $f(8) \approx 0.72092$ is a local min. From there, it increases until $f(13) \approx 0.72147$. From there, it decreases until $f(19) \approx 0.72129$, which is greater than $f(8)$. $\endgroup$ – Varun Vejalla Aug 9 '19 at 2:09
  • $\begingroup$ In short, the lower bound increases and the upper bound decreases. $\endgroup$ – Varun Vejalla Aug 9 '19 at 2:10
  • $\begingroup$ @automaticallyGenerated The pattern that I pointed out is a bouncing around between $2^k$ to $1.5 * 2^k$ and back again for $2^{k+1}$. The estimate that it is based on gets more accurate the larger $k$ is. Along the sequence $n = 2^k$ you converge to one limit, and the sequence $n = 3 * 2^k$ converges to a different one that is about $0.00000574876$ smaller. $\endgroup$ – btilly Aug 9 '19 at 3:44
  • $\begingroup$ In short, I've described the asymptotic behavior. You're guessing based on numerical experiments with small $n$. $\endgroup$ – btilly Aug 9 '19 at 3:46
  • $\begingroup$ I think I see my problem. I assumed that the lower bound and upper bound converge to the same number, when in fact the lower bound converges to $L$ and the upper bound converges to $U$, $L<U$. $\endgroup$ – Varun Vejalla Aug 9 '19 at 4:46

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.