$n$ players toss a fair coin. The number of tosses with the result "heads" is recognized for each player.

The game stops if the numbers are pairwise different.

Let $X$ be the number of tosses for each player until the game is over.

  • What is $E(X)$ ?

Simulation gives the following table

      n               E(X)        Var(X)       number of games

      2                 2             6           100 000 000
      3                 5.22         38.277       100 000 000
      4                10.262       143.219       100 000 000
      5                17.568       407.487        10 000 000
      6                27.480       971.944        10 000 000
      7                40.338      2051.034         1 000 000
      8                56.529      3960.319         1 000 000
      9                76.313      7110.368         1 000 000
     10               100.355     12154.328         1 000 000
     11               128.885     19864.376           100 000
     12               162.443     31217.448           100 000
  • $\begingroup$ For $n=2$, the answer is $E(X)=2$ because the game stops as soon as the players produce a different result. But already for $n=3$, I have no idea how to calculate $E(X)$. $\endgroup$ – Peter May 18 '15 at 8:48
  • $\begingroup$ I'm not sure of something; With result $\{H,T\},\{H,T\},\{H,H\}$, the game ends? Or the numbers have to be pairwise different, for all pairs? $\endgroup$ – Masclins May 18 '15 at 9:48
  • $\begingroup$ As I mentioned, the numbers have to be pairwise different. So, the game would not stop in your example. $\endgroup$ – Peter May 18 '15 at 9:49

I know this is not what you're looking for, but I find this question surprisingly difficult and fascinating. So I'm replying with the hope that someone can take these further. The first thing I did was to run a simulation with a 1000 games for each number of coins from 2 to 20, just to get an estimate of what should we be looking for. The results are (rounded to 1 decimal digit): E(2)=2 E(3)=5.2 E(4)=10.3 E(5)=18 E(6)=26.5 E(7)=38.8 E(8)=54.6 E(9)=75.9 E(10)=94 E(11)=124.3 E(12)=161.2 E(13)=204.1 E(14)=261.2 E(15)=290.3 E(16)=356.7 E(17)=405.7 E(18)=483.9 E(19)=530.2 E(20)=634.4

While I cannot really trust the higher numbers (since E(n) is of the same order of magnitude of the number of games I ran), I do believe the trend is consistent, at the beginning I thought it looks like a 2nd degree polynomial in $N$, but there are too many deviations from this model.

The only other thing I managed to do is to calculate the probability of the game ending after the minimal number of steps (being equal to the number of coins, $N$) which is given by


  • $\begingroup$ 1) $1000$ games are not enough to have a satisfiable estimate. 2) I do not think that a polynomial of degree $2$ will be a good approximation 3) I would like to have exact values or at least values very close to the true ones. 4) The minimum length is $n-1$, if $n$ players participate. $\endgroup$ – Peter May 19 '15 at 11:45

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.