6
$\begingroup$

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.

enter image description here

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.

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 1, 2021 at 12:49
  • $\begingroup$ If you want a code snippet in python or R, please update your question. $\endgroup$ Mar 1, 2021 at 12:58
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Mar 1, 2021 at 15:07
  • $\begingroup$ For 7 to win, do you have to roll nine 7's or ten? $\endgroup$
    – John L
    Mar 1, 2021 at 18:17
  • 2
    $\begingroup$ 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. $\endgroup$
    – simonc8
    Mar 1, 2021 at 19:42

1 Answer 1

1
$\begingroup$

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
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – simonc8
    Mar 1, 2021 at 19:58
  • 1
    $\begingroup$ 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). $\endgroup$ Mar 2, 2021 at 6:15
  • $\begingroup$ 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}$. $\endgroup$
    – att
    Mar 18, 2021 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.