# Probability of winning

This is a game to teach children about probability - for each roll of the dice the counter corresponding to the total moves forward one space. Obviously 7 is the most likely to move followed by 6/8, 5/9 etc. so the race is unfair although the dice are fair.

This made me want to calculate the probability of any given counter winning, and I got into a complete tangle doing this. In essence: if you have $$n$$ outcomes with probabilities $$p_1, p_2 ...p_n$$ such that $$p_1 + ...+ p_n=1$$ what is the probability that a given outcome will occur $$m$$ times before any other outcome occurs $$m$$ times?

Grateful for guidance.

• The dice rolls follow a multinomial distribution, so you can in principle evaluate a large sum over the PMF. I would not expect there to be a closed form solution. Mar 1, 2021 at 12:49
• If you want a code snippet in python or R, please update your question. Mar 1, 2021 at 12:58
• A related question was asked (but not answered) at stats.stackexchange.com/questions/487162. The present question admits brute-force answers as well as some good approximations, especially when all the $p_i$ are relatively small or $m$ is large.
– whuber
Mar 1, 2021 at 15:07
• For 7 to win, do you have to roll nine 7's or ten? Mar 1, 2021 at 18:17
• John L - it's 9. All the counters start in the bottom row. And poor old counter 1 has very little chance of going anywhere, but that's something for the children to work out. Mar 1, 2021 at 19:42

## 1 Answer

Even the case where there are only two horses is hard to calculate.
Suppose the first horse advances with probability $$p$$ and the second horse advances with probability $$1-p$$. The probability the first horse advances $$k$$ spaces before the second horse advances $$k$$ spaces is:
$$\sum_{n=k-1}^{2(k-1)}P[\text{first horse advances }k-1\text{ spaces up until turn }n\text{ and advances on turn }n+1]$$
$$=\sum_{n=k-1}^{2(k-1)}p {n\choose{k-1}}p^{k-1}(1-p)^{n-k+1}$$ which cannot be simplified using elementary functions.

For the case given, the chances each horse (1-12) advances $$k=9$$ spaces first are approximately: 0, 0.000019, 0.001846, 0.018712, 0.078557, 0.201543, 0.399709, 0.200976, 0.077823, 0.018976, 0.001823, 0.000016

For $$k=10$$, the probabilities change slightly:
0, 0.000009, 0.001248, 0.016030, 0.073834, 0.201509, 0.414829, 0.201925, 0.073274, 0.016057, 0.001279, 0.000006

As $$k$$ gets larger, the probability increases in the middle so that when $$k=1000$$, for example, the probability horse 7 wins is 99.99%. I found these approximate values using simulation in R:

k=10
ps=c(1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1)/36
set.seed(123)
nsim=1000000
winner=rep(0, nsim)
for (i in 1:nsim) {
x=sample(c(1:11), 11*(k-1)+1, replace=TRUE, prob=ps)
winner[i]=1
indx=which(x==1)[k]
if (is.na(indx)) indxw=11*(k-1) + 1 else indxw=indx
for (j in 2:11) {
indx=which(x==j)[k]
if (!is.na(indx)) if (indx<indxw) {
winner[i]=j
indxw=indx
}
}
}
tabulate(winner)/nsim

• Many thanks for this. I can see from your formula that it could get impossibly complicated as soon as you add more horses. I had tried a much smaller simulation of 1000 games using Python, but R is obviously much better suited to this type of thing. Mar 1, 2021 at 19:58
• In the general case of $k$ horses making $m$ steps, the brute force approach would evaluate the multinomial PMF for (say) $x_1=m$ and $x_2, \dots, x_k\in\{0, \dots, m-1\}$, so you need to sum $(k-1)^m$ probabilities, each one very small. Quite apart from the combinatorial explosion, the numerics of very small numbers may start to matter. A dynamic programming approach seems to also lead to evaluating all $(k-1)^m$ probabilities. It looks like this is a good example to teach kids about simulation in Python (or R). Mar 2, 2021 at 6:15
• Might be worth noting the summation formula generalizes into $d$ dimensions: the probability the $n$th horse wins is $\sum_{\substack{0 \le x_1,...,x_d < k\\x_n=k-1}}{\sum_i x_i\choose x_1,...,x_d}p_n\prod_{i} p_i^{x_i}$.
– att
Mar 18, 2021 at 2:04