[Math] What are the probabilities of a tie when rolling to see who goes first in a board games for various numbers of dice and various numbers of players

diceprobability

When playing many board games, the first step is to have everyone roll a die to see who goes first, with a roll off in the case of a tie. While doing that over the Christmas break, my husband suggested that we roll two dice instead of one, with the assertion that this would make ties less likely. My brother disagreed, claiming it wouldn't make any difference. I'm interested in investigating this question.

I've been able to calculate the probability of ties for the case of rolling one die for any number of players, and the case for rolling two dice with two players. However, I haven't actually found a general solution in either case (I mostly used a brute force approach in the one die case). Is anyone here aware of any sources that have investigated this issue?

(For the record, I'm pretty sure both my husband and brother have forgotten the conversation, so you don't need to worry about hurting anyone's feelings. 🙂 )

Best Answer

We look only at the simplest case, where there is a single die. But to make things more interesting, let the die be $d$-sided, with equal probabilities for the numbers $1,2,\dots,d$. Suppose there are $m$ players. We find the probability that a tie doesn't occur.

Assume that "highest number goes first." So there is no tie if for some $k\ge 2$, one players rolls a $k$ and all other players roll numbers $\le k-1$.

Let the number of players be $m$. First we find the probability that Alicia rolls a $k$ and everybody else rolls a number $\le k-1$.

The probability Alicia rolls a $k$ is $\frac{1}{d}$. The probability everyone else rolls a number $\le k-1$ is $\left(\frac{k-1}{d}\right)^{m-1}$. So the probability of no tie, with Alicia winning, is $$\sum_{k=2}^d \frac{1}{d} \left(\frac{k-1}{d}\right)^{m-1}.$$ Sum over all players. The probability of no tie is $$\frac{m}{d^m}\sum_{k=2}^d (k-1)^{m-1}.$$ The remaining sum is a well-known one, with a long history. There are simple formulas for it in the cases $m-1=1,2,3$. For the general case, please see Faulhaber's Formula.

Remark: We can, with some pain, compute the probability of no tie with $3$ players and $2$ dice. We compute the probability that there is no tie and Alicia is the winner, and multiply by $3$.

Alicia can be the clean winner in any one of $10$ ways. She can throw a $3$ and be the clear winner, or throw a $4$ and be the clear winner, or throw a $5$ and be the clear winner, and so on up to throwing a $12$ and being the clear winner. We start computing these various probabilities.

The probability Alicia throws a $3$ is $\frac{2}{36}$. The probability the other two both throw something $\le 1$ is $\left(\frac{1}{36}\right)^2$. Multiply.

The probability Alicia throws a $4$ is $\frac{3}{36}$. The probability the other two both throw something $\le 3$ is $\left(\frac{3}{36}\right)^2$. Multiply.

The probability Alicia throws a $5$ is $\frac{4}{36}$. The probability the other two both throw something $\le 4$ is $\left(\frac{6}{36}\right)^2$. Multiply.

And so on. Add up the $10$ terms we get. One could even extend to $d$-sided dice and $3$ players, and get a closed form formula.

Related Solutions

Probability – Average of Rolling Two Dice and Taking the Higher Value

For $k=1,\dots,6$ there are $k^2$ ways to get two numbers less than or equal to $k$. To get two numbers whose maximum is $k$ I must get two numbers that are less than or equal to $k$, but not two numbers that are less than or equal to $k-1$, so there are $k^2-(k-1)^2=k^2-(k^2-2k+1)=2k-1$ ways to get two numbers whose maximum is $k$. Thus, the probability of getting a maximum of $k$ is

$$\frac{2k-1}{36}\;,$$

and the expected value of the maximum is

$$\begin{align*} \sum_{k=1}^6k\cdot\frac{2k-1}{36}&=\frac1{36}\sum_{k=1}^6\left(2k^2-k\right)\\ &=\frac1{18}\sum_{k=1}^6k^2-\frac1{36}\sum_{k=1}^6k\\ &=\frac{6\cdot7\cdot13}{18\cdot6}-\frac{6\cdot7}{36\cdot2}\\ &=\frac{91}{18}-\frac{21}{36}\\ &=\frac{161}{36}\\ &=4.47\overline{2}\;. \end{align*}$$

Of course this is larger than the expected value of $\frac72=3.5$ for a single roll of a die: picking the maximum of the two numbers can be expected to bias the result upwards.

Probability – Most Unfair Set of Three Nontransitive Dice

It turns out that you can do very slightly better than the dice in your example. The probability has to be a multiple of $1/36$, your example has $20/36$, and the best possible value is $21/36=7/12$.

From my answer to the question that anon linked to, we know that the probability of one $6$-sided die beating another while having a lower median can be at most $3/4-1/12=2/3=24/36$. Wikipedia gives an example of a cycle of four dice in which each die beats the next one with this probability.

You're looking for a cycle of three dice in which each die beats the next one with the same probability. Without loss of generality we can assume that the dice carry $18$ different numbers. Then there are $18!/6!^3=17153136$ different sets of dice, so it's well within the reach of our electronic friends to try them all out. Here's code that does that (rather inefficiently). The result is that the maximal probability for such a cycle is $21/36=7/12$ and there are eight different sets of dice that attain that probability. Here they are, with consecutive stretches of numbers collapsed into one as in your example:

0 3 3 3 6 6
2 2 2 5 5 5
1 4 4 4 4 4

0 0 3 3 3 6
2 2 2 2 2 5
1 1 1 4 4 4

0 3 5 5 5 5
2 4 4 4 4 7
1 1 1 6 6 6

0 3 5 7 7 7
2 2 4 4 6 9
1 1 1 8 8 8

0 3 3 5 5 5
2 2 2 4 4 7
1 1 1 6 6 6

0 3 5 5 7 7
2 2 2 4 6 9
1 1 1 8 8 8

0 3 3 3 3 5
2 2 2 2 4 7
1 1 1 6 6 6

0 0 3 6 6 6
2 2 2 5 5 5
1 1 1 4 7 7

There are two sets with $7$ different numbers, four sets with $8$ and two with $10$, and your near-optimal example has $9$, whereas the mean number of different numbers after collapsing, averaged over all sets with $18$ different numbers, is $18-17\cdot(5/17)=13$, so consecutive stretches of numbers and thus high collapsibility are a striking feature of these sets.

P.S.: I just realized that there's a symmetry in that you can invert the orders of both the dice and the numbers and get another set with the same probability. The first two sets are related by this symmetry, as are the third and seventh, the fourth and sixth and the fifth and eighth. Thus there are only four really different sets of dice, with $7$, $8$, $10$ and $8$ different numbers, respectively.

Best Answer

Related Solutions

Probability – Average of Rolling Two Dice and Taking the Higher Value

Probability – Most Unfair Set of Three Nontransitive Dice

Related Question