# How many tosses are necessary that $n$ players produce pairwise different numbers of tosses with the result “heads”?

$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

• 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)$. – Peter May 18 '15 at 8:48
• 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? – Masclins May 18 '15 at 9:48
• As I mentioned, the numbers have to be pairwise different. So, the game would not stop in your example. – Peter May 18 '15 at 9:49

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
$P_N(n=N)=N!\prod_{j=0}^N{\binom{N}{j}}\frac{1}{2^N}$.
• 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. – Peter May 19 '15 at 11:45