Horse race puzzle

Introduction

This post is part pedagogical rant, part discussion of a beautiful technique in combinatorics, both motivated by a recent exchange with a high school student, about an interesting dice game that seems to be a common introductory exercise in probability:

There are 12 horses, numbered 1 through 12, each initially at position 0 on a track. Play consists of a series of turns: on each turn, the teacher rolls two 6-sided dice, where the sum of the dice indicates which horse to advance one position along the track. The first horse to reach position $n=5$ wins the race.

At first glance, this seems like a nice exercise. Students quickly realize, for example, that horse #1 is a definite loser– the sum of two dice will never equal 1– and that horse #7 is the best bet to win the race, with the largest probability (1/6) of advancing on any given turn.

But what if a student asks, as this particular student did, “Okay, I can see how to calculate the distribution of probabilities of each horse advancing in a single turn, but what about the probabilities of each horse winning the race, as a function of the race length $n$ ?” This makes me question whether this is indeed such a great exercise, at least as part of an introduction to probability. What started as a fun game and engaging discussion has very naturally led to a significantly more challenging problem, whose solution is arguably beyond most students– and possibly many teachers as well– at the high school level.

I like this game anyway, and I imagine that I would likely use it if I were in a similar position. Although the methods involved in an exact solution might be inappropriate at this level, the game still lends itself nicely to investigation via Monte Carlo simulation, especially for students with a programming bent.

Poissonization

There is an exact solution, however, via several different approaches. This problem is essentially a variant of the coupon collector’s problem in disguise: if each box of cereal contains one of 12 different types of coupons, then if I buy boxes of cereal until I have $n=5$ of one type of coupon, what is the probability of stopping with each type of coupon? Here the horses are the coupon types, and the dice rolls are the boxes of cereal.

As in the coupon collector’s problem, it is helpful to modify the model of the horse race in a way that, at first glance, seems like unnecessary additional complexity: suppose that the dice rolls occur at times distributed according to a Poisson process with rate 1. Then the advances of each individual horse (that is, the subsets of dice rolls with each corresponding total) are also Poisson processes, each with rate equal to the probability $p_i$ of the corresponding dice roll.

Most importantly, these individual processes are independent, meaning that we can easily compute the probability of desired states of the horses’ positions on the track at a particular time, as the product of the individual probabilities for each horse. Integrating over all time yields the desired probability that horse $j$ wins the race:

$P(j) = \displaystyle\int_{0}^{\infty} p_j \frac{e^{-p_j t}(p_j t)^{n-1}}{(n-1)!} \prod\limits_{i \neq j} \sum\limits_{k=0}^{n-1} \frac{e^{-p_i t}(p_i t)^k}{k!} dt$

Intuitively, horse $j$ advances on the final dice roll, after exactly $n-1$ previous advances, while each of the other horses has advanced at most $n-1$ times.

Generating functions

This “Poissonization” trick is not the only way to solve the problem, and in fact may be less suitable for implementation without a sufficiently powerful computer algebra system. Generating functions may also be used to “encode” the possible outcomes of dice rolls leading to victory for a particular horse, as follows:

$G_j(x) = p_j \frac{(p_j x)^{n-1}}{(n-1)!} \prod\limits_{i \neq j} \sum\limits_{k=0}^{n-1} \frac{(p_i x)^k}{k!}$

where the probability that horse $j$ wins on the $m+1$ -st dice roll is $m!$ times the coefficient of $x^m$ in $G_j(x)$ . Adding up these probabilities for all possible $m$ yields the overall probability of winning. This boils down to simple polynomial multiplication and addition, allowing relatively straightforward implementation in Python, for example.

The results are shown in the following figure. Each curve corresponds to a race length, from $n=1$ in black– where the outcome is determined by a single dice roll– to $n=6$ in purple.

Probability distribution of each horse winning, with each curve corresponding to a race length n from 1 to 6.

As intuition might suggest, the longer the race, the more likely the favored horse #7 is to win. This is true for any non-uniformity in the single-turn probability distribution. For a contrasting example, consider a race with just 6 horses, with each turn decided by a single die roll. This race is fair no matter how long it is; every horse always has the same probability of winning. But if the die is loaded, no matter how slightly, then the longer the race, the more advantage to the favorite.

4 thoughts on “Horse race puzzle”

Mark on March 21, 2017 at 2:12 am said:

I don’t see how the horses’ positions are independent in the “poissonized” problem. If there was some distribution of the horses positions after n rolls in the original problem, I could just wait however long it is until n rolls have occurred in the poissonized problem and the position of the horses would be the same. It’s exactly the same thing as the original problem, but you randomly make the clock run faster or slower between rolls, when nothing happens. That doesn’t change the problem at all! If the horses positions aren’t independent in the original problem, they shouldn’t be in the poissonized problem either.

Reply ↓
- Mark on March 21, 2017 at 5:30 am said:
  
  Oh, never mind, a friend straightened me out! “Independence” here means independent after a certain amount of time has passed, not after a certain number of rolls. It’s possible to have one without the other.
  
  Reply ↓
Mike on March 21, 2017 at 4:40 am said:

I just wanted to say that your blog is incredible and is exactly the type of work that I am trying to emulate in my own. Thanks for all the thoughtful and incredible content.

Reply ↓
Pingback: Analysis of horse racing board game | Possibly Wrong