4
$\begingroup$

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.

EDIT: with @SteveKass's suggestion, I realize that we can model this game as a Markov process, with $n+1$ states. Each state represents the number of players who have 'won' - so state $S_0$ means no players have won, and state $S_i$ means exactly i players have won. Thus state $S_n$ means the game is done, which is an absorbing state.

So the state transition probabilities for 4 players with 4 dice from state zero can be computed:

P(no progress) = P(all the same number) + P(even number of collisions)

So these rolls have the form 1111, or 2222, or 1122, or 3434. So there are 10 combinations of collision rolls: 4 where all numbers match, and 36 where two numbers appear an even number of times. So the state transition matrix probability for S(0,0) (meaning we are at the beginning of the game, but stay in state zero because the rolls don't advance the game), is $\frac{40}{256}$ (there are ${4 \choose 1}$ ways to roll all the same number, and ${4 \choose 2}$ ways to select two numbers, and ${4 \choose 2}$ ways to distribute those numbers into rolls, hence $4+36=40$ over $4^4$ total possible rolls).

However I see no generalized way of counting the number of collision possibilities. For 4 players, it is only AAAA, AABB, or ABAB. For 5 players, it is AABBB, or AAAAA, AAABB, or ABBAAA, etc. For 10 players, it is any even partitioning of the rolls that results in an even number of conflicts, like AABBBBBBBB, AAAABBBBBB, AAAAAABBBB, AAAAAAAABB, AABBAAAAAA, and AAAABBAAAA, etc. I don't know of any equation that will tell me the number of possible collision possibilities as $n$ becomes large.

$\endgroup$
3
  • $\begingroup$ Is the PDF you mentioned A Collection of Dice Games by Matthew M. Conroy? I am interested in dice games, if not, could you please share it with me? Thanks a lot! $\endgroup$
    – simplzh
    Aug 30 '19 at 13:58
  • $\begingroup$ Why do you say the number of states is not fixed? Can’t we define the states as $W_s$ for each subset $s$ of the players, where the state $W_s$ means the players who have won at least once comprise the set $s$? The initial state is $W_\emptyset$, and the final absorbing state is $W_{\{1,\dots,n\}}$. There are $2^n$ states, and I'm not suggesting it's easy to model in general, but unless I’ve misunderstood the question, there seem to be well-defined states and computable transition probabilities. $\endgroup$
    – Steve Kass
    Aug 30 '19 at 20:47
  • 1
    $\begingroup$ @SteveKass, I think you are correct. Thinking about a slightly simpler problem, I realized that if I don't care about the order of players, just about how many rounds are expected, then it indeed can be modeled as a Markov chain. If there are n nodes, then the chain has n+1 states, where state 0 means no players have advanced (aka. the beginning of the game), and the nth state means that n players have won. Since no player can 'unwin', then the transition probabilities can clearly define all possible transitions between any two states. $\endgroup$ Dec 12 '19 at 2:21
1
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ Can you explain your recursive formulas (just one of them, even)? For starters, it seems like the expected length of the $4$-player $4$-sided dice game $E$ should be $p_4+$something, since the game can end after one roll with probability $p_4$. It also seems like more information is needed than just the number of players winning a round, since on the first roll just player $1$ could win, and then on the second roll, just player $1$ could win again or just player $2$ could win, which two events (within the probability $p_1$ make different progress towards completion. $\endgroup$
    – Steve Kass
    Aug 30 '19 at 20:43
  • $\begingroup$ recursive formulas 1: $$𝐸(4)=𝑝_0∗(1+𝐸(4))+𝑝_1∗(1+𝐸(3))+𝑝_2∗(1+𝐸(2))+p_4*1 $$Yes, all we care about is win at least once, so that's why some recursive formulas have some fractions before $p_i$. $\endgroup$
    – simplzh
    Aug 30 '19 at 21:08
  • $\begingroup$ Ok, two more questions. First, should you have the word not in the definition of $E(n)$? It seems like you are computing $E(4)$ as the expected number of games required for $4$ players to have won, not to not have won. Second, in the formula you explained, I get the $p_4\times1$ term, but if after the first roll $2$ players win, then why is the expected number of successive games remaining $E(2)$? It seems like it should be more complicated. It seems like the expected number is the number of games where a particular two players (and possibly others) finally win. $\endgroup$
    – Steve Kass
    Aug 30 '19 at 21:19
  • $\begingroup$ First, before the game starts, we have $4$ players have not won at least once, at the end, we have $0$ player have not won at least once; Second, that's what I meant just now. Suppose 2 players A, B have won at least once. In this round, we have 2 players won. Then we need to consider three situations 1. A, B both won; 2. A or B won; 3. neither of A, B won. So there is some fractions in last 3 recursion formula. $\endgroup$
    – simplzh
    Aug 30 '19 at 21:27
  • $\begingroup$ Thanks! I get it now: Instead of “$E(n)$ means $n$ players have not won at least once.” you mean “$E(n)$ is the expected number of rolls to finish a game where $n$ players have not yet won at least once.” Your probabilities and recursion look good to me now, but I didn't solve them or simulate the game to see why they don't match the OP'S simulation. $\endgroup$
    – Steve Kass
    Aug 30 '19 at 22:13
1
$\begingroup$

I'm one step closer to an answer...

The first part is recognizing that for the expected number of rounds, the ordering of the players does not matter. In other words, the ordering players 1,2,3,4, is just as likely as 4,3,2,1, no matter how many sides the dice have.

As a result, we can model the game with a Markov Chain with $n$ states, labeled $S_0$ through $S_n$, where the i-th state indicates that i players have been established. We can also establish that the probability of being in state $i$ and progressing to state $j$ is denoted $p_{ij}$.

Specifically for 4 players rolling 4-sided dice: I used a program to enumerate every dice roll, and calculate the probabilities of each state. We construct the state transition Matrix in canonical form (also noting a factor $4^4$ is divided from each matrix entry) we have:

$P = \begin{bmatrix} 40 & 48 & 144 & 0 & 24\\ 0 & 52 & 108 & 72 & 24\\ 0 & 0 & 88 & 120 & 48\\ 0 & 0 & 0 & 148 & 108\\ 0 & 0 & 0 & 0 & 256\\ \end{bmatrix} = \begin{bmatrix} \frac{5}{32} & \frac{3}{16} & \frac{9}{16} & 0 & \frac{3}{32}\\ 0 & \frac{13}{64} & \frac{27}{64} & \frac{9}{32} & \frac{3}{32}\\ 0 & 0 & \frac{11}{32} & \frac{15}{32} & \frac{3}{16}\\ 0 & 0 & 0 & \frac{37}{64} & \frac{27}{64}\\ 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}$

Extracting transitional matrix $Q$, and using the equation $N = (I-Q)^{-1}$ yields:

$ N*\begin{bmatrix}1\\1\\1\\1\end{bmatrix} = \begin{bmatrix}\frac{32}{27}&\frac{128}{459}&\frac{1280}{1071}&\frac{4864}{3213}\\ 0&\frac{64}{51}&\frac{96}{119}&\frac{1856}{1071}\\ 0&0&\frac{32}{21}&\frac{320}{189}\\ 0&0&0&\frac{64}{27}\end{bmatrix} * \begin{bmatrix}1\\1\\1\\1\end{bmatrix} = \begin{pmatrix}\frac{13408}{3213}\\ \frac{4064}{1071}\\ \frac{608}{189}\\ \frac{64}{27}\end{pmatrix}$

So the first row in the vector should be the expected number of states to transitions between $S_0$ and $S_4$, which comes out to 4.173, which matches my original simulation exactly.

The first row matches @simplzh coefficients, however I cannot figure out how to calculate the other rows. For example, row 1,1, the probability of being in state 1 and staying in state 1, is 52/256. This should be the sum of all rolls of the form AAAA and AABB (4+36), plus all rolls of the form AAAB, with one player being added in (the one who has already won). Because if that player wins again, the game doesn't progress.

I still can't seem to find a compact representation of this probability for a general $n$ and $k$ however.

$\endgroup$

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.