Toss 100 fair coins and take away the tails; toss the remaining coins and take away the tails. Continue until no coins remain. [duplicate]

100 participants have a fair coin each, on a given round, the not already discarded participants flip their coins, those who flip a tail are discarded from the game, the remaining ones continue to play until nobody is left (everyone has been discarded).

1. What would be the average number of trials (where each trial consists of a tossing and removing the tails) one would expect from doing this experiment?

2. Does conditional expectation work for something like this?

I know that each individual coin follows a Geometric distribution, but I am trying to figure out the sum of them to determine the average number of trials for a game like this.

My Logic/Thought Process: I started out trying to think of the probability that a particular coin makes it to round $r$ which is $\frac{1}{2^m}$. I then realized that each coin outcome can be modeled by a Geometric random variables with $p = 0.5$. I am just now unsure how to take the leap from this single case to a case with 100 coins. I presume it has to do with summing the geometric random variables, but I am not sure.

Solution 1:

This is essentially equivalent to computing the expected value of the maximum of $n=100$ iid geometric random variables, for $p=\frac12$

(BTW: The linked question includes the recursion given by @saulspatz's answer)

There is no closed form solution, but this approximation for large $n$ (with bounds) is given:

$$E_n \approx \frac{1}{2} + \frac{1}{\lambda} H_n$$

where $\lambda = - \log(1-p)=0.69314718\cdots$ and $H_n$ is the harmonic number.

For example, for $n=3$ this gives $E_3 \approx 3.14494$ , very near the exact $E_3=22/7=3.14285$

For $n=100$ this gives $E_{100} \approx 7.98380382$.

More in "Yet another application of a binomial recurrence order statistics", W. Szpankowski; V. Rego, Computing, 1990, 43, 4, 401-410.

Solution 2:

I doubt that there's a simple expression for the expectation. Let $E_n$ be the expected number of trials when $n$ coins remain, so that we are asked to compute $E_{100}$. We know that $E_0=0$ and that $E_1=2$. Now $$E_2=1+\frac14E_2+\frac12E_1+\frac14E_0$$ because we have to make one trial, and with probability $\frac14$ we throw two heads and still have two coins, with probability $\frac12$ we throw a head and a tail, and with probability $\frac14$, we throw two tails, and the experiment ends. This gives $E_2=\frac83$.

We can continue in this manner: $$E_3=1+\frac18E_3+\frac38E_2+\frac38E_1+\frac18E_0$$ which gives $E_3=\frac{22}7$ if I'm not mistaken.

One could easily write a computer program to work back to $E_{100}$, but it would be easier to proceed by simulation.

EDIT

I wrote the script I suggested. The exact value if a fraction whose numerator has $894$ decimal digits and whose denominator has $893$. The approximate value is $7.98380153515692$.

Solution 3:

Searching OEIS with @saulspatz first values, we can find that:

$$E_n = \frac{a(n)}{b(n)}$$

where $a(n)$ is OEIS A158466 and $b(n)$ is OEIS A158467. At OEIS A158466 you can find also the following formulas:

$$E_n = -\sum_{k=1}^n (-1)^k \frac{{n \choose k}}{1-\frac{1}{2^k}}$$

$$E_n = \sum_{k=1}^{\infty} k \left(\left(1-\frac{1}{2^k}\right)^n - \left(1-\frac{1}{2^{k-1}}\right)^n\right)$$

and thus (see here):

$$E_{100} \approx 7.983801535$$