$n$ players play a game where they flip a fair coin simultaneously. If a player has a different result than the others, that player is out, and then the remaining $n - 1$ players continue until there are two players left and they are the winners. For example, for $n=3$, a result $(H,T,T) $ makes the first player lose and the other two to win, and $(H,H,H)$ will make them toss again.

I'll define the variable: $$Y =\text{number of rounds until there are two players left out of } n$$

I'm looking for $E(Y), VAR(Y)$. What I did was:

Define a random variable $$X_i = \text{number of rounds until one player out of } i \text{ is out}$$

so is follows that: $X_i \sim{\mathrm{Geo}(2\cdot\frac{i}{2^{i}} = \frac{i}{2^{i-1}})}$ , since we have to choose a player and a value for the coin $$Y =\sum_{i=3}^{n}X_i$$ $$E(Y) = E(\sum_{i=3}^{n}X_i)=\sum_{i=3}^{n}E(X_i)=\sum_{i=3}^{n}\frac{2^{i}}{i}$$ $$VAR(Y) = \sum_{i=3}^{n}VAR(X_i) = \sum_{i=3}^{n} \dfrac{\dfrac{2^{i-1}-i}{2^{i-1}}}{\dfrac{i^2}{2^{2(i-1)}}} = \sum_{i=3}^{n} \dfrac{2^{i-1}(2^{i-1}-i)}{i^2}$$

Is there a closed form solution to this problem?

  • $\begingroup$ @joriki huh, right. Thanks! $\endgroup$ – Theoretical Economist May 20 '20 at 10:11
  • 1
    $\begingroup$ The approach seems valid. Are you hoping to simplify the summation into a closed form? I am not sure that's possible (and but would be happy to be proved wrong). BTW you can add the variances too since the $X_i$'s are independent. $\endgroup$ – antkam May 20 '20 at 18:53
  • $\begingroup$ "If a player has a different result than the others": What does this mean? On the first round, if half of the players flip heads and the other half flip tails, are they all out? $\endgroup$ – Michael May 21 '20 at 2:32
  • $\begingroup$ I have updated the question $\endgroup$ – CodeHoarder May 21 '20 at 6:03

Your Answer

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

Browse other questions tagged or ask your own question.