Dice game - how do find the expected number of rounds?

Question

I've been struggling trying to find an analytical solution to this problem.

Let's say we have a dice game, played with n players rolling n, k sided dice, with k >= n. The dice determine the order of winning players: each player is assigned a number, from 1 to n, and all roll their k-sided dice simultaneously. Winners are selected each round if the number they roll is unique amongst the n players. If a players roll is matched by another player, then both must continue to the next round, and there can be more than one winner each round, or zero winners. All players roll their dice even if they have already won. All players keep rolling until all have won at least once. The problem is to find the average and expected number of rounds each games last as a function of n and k.

For example, if we had a game of 4 players, each rolling 4-sided dice, a potential game might proceed like this:

Roll 1 - (1,1,3,3) : no winning players, since no player rolled a unique number

Roll 2 - (1,2,2,3) : player 1 and player 4 win, since each rolled a unique number

Roll 3 - (1,1,3,4) : player 3 and player 4 win

Roll 4 - (1,3,3,4) : player 1 and 4 win

Roll 5 - (2,3,2,2) : player 2 wins

Each player has won at least once, so this game ends in 5 rounds.

It would make sense that as k becomes >> n, then the expected number of rounds would converge at 1 (since the probability of there being any matching number for a large sided dice tends towards zero for a large number of sides).

This is a simple problem to simulate, and running each game 1 million times shows the following result:

4 players, rolling 4-sided dice -> average number of rounds = 4.17346

4 players, rolling 10-sided dice -> average number of rounds = 1.806924

6 players, rolling 6-sided dice -> average number of rounds = 5.225997

6 players, rolling 10-sided dice -> average number of rounds = 3.043941

6 players, rolling 100-sided dice -> average number of rounds = 1.15475

This does not seem to be model-able with a Markov Chain, since the number of states is not fixed from game to game with a given n and k.

NOTE: this is not homework, but I came across this game in a PDF full of dice games and haven't been able to find or work-out a solution.

Answer 1

I think there is not a general solution. Here is my solution on 4 players, rolling 4-sided dice case. Calculation is pretty complicated. I don't know if there is any better method.

First of all, we need to figure out results of each round of rolling. 4 players roll 4 dice, then we can get:

• 0 winner: $p_0=\frac{10}{64}$
  • AAAA: $p_01=4*\frac{1}{4^4}=\frac{1}{64}$
  • AABB: $p_02={4\choose2}\frac{\frac{4*3}{2}}{4^4}=\frac{9}{64}$
• 1 winner: $p_1=\frac{12}{64}$
  • AAAB: $p={4\choose1}\frac{4*3}{4^4}=\frac{12}{64}$
• 2 winners: $p_2=\frac{36}{64}$
  • AABC: $p={4\choose2}\frac{4*3*2}{4^4}=\frac{36}{64}$
• 3 winners: $p_3=0$
  • not possible
• 4 winners: $p_4=\frac{6}{64}$
  • ABCD: $p=\frac{4*3*2*1}{4^4}=\frac{6}{64}$

$E(n)$ is the expected number of rolls to finish a game where $n$ players have not yet won at least once. So we want to know $E(4)$.

$$E(4)=1+p_0*E(4)+p_1*E(3)+p_2*E(2)$$ $$E(3)=1+p_0*E(3)+\frac{1}{4}p_1*E(3)+\frac{3}{4}p_1*E(2)+\frac{1}{2}p_2*E(2)+\frac{1}{2}p_2*E(1)$$ $$E(2)=1+p_0*E(2)+\frac{2}{4}p_1*E(2)+\frac{2}{4}p_1*E(1)+\frac{1}{6}p_2*E(2)+\frac{4}{6}p_2*E(1)$$ $$E(1)=1+p_0*E(1)+\frac{3}{4}p_1*E(1)+\frac{3}{6}p_2*E(1)$$

And I got $E(4)=6.401612$ which is not close to the simulation result. If you find out what's wrong with it please comment. Thanks a lot!