The lucky derby

Let’s take a look at a particular horse. Each step, suppose it moves forward with probability $q > \frac{1}{2}$ or backward with probability $1-q$. The horse starts at position $0$ and we would like to know the probability that it will reach position $2n$ in exactly $2k$ steps. The reason for the factor of $2$ is that to reach an even-numbered position (such as $200$, in the problem statement), the horse must take an even number of steps. Let’s call this probability $P(n,k,q)$.

This scenario is known as a 1D random walk, and past posts that deal with similar ideas include The Deadly Board Game and Gambler’s Ruin. This problem is a bit different, however, since we care about the distributions of the number of moves required (not just the expected number of moves).

Back to the task at hand: determining $P(n,k,q)$. If we reach the position $2n$ in $2k$ moves, then clearly we have $k \ge n$. Next, we can deduce that we must have moved forward $(k+n)$ times and backward $(k-n)$ times. The probability of this occurring is $q^{n+k}(1-q)^{n-k}$. The tricky part here is to deal with the order in which we take the steps. The last step we take must always be forward, so we will restrict our attention to arrange the remaining $2k-1$ steps. There is a total of $2k-1 \choose k-n$ ways to do this, but this is not the number we’re looking for! Some of these paths will reach $2n$ too early, so we will count these paths and subtract them.

The quantity we’re counting is closely related to the Catalan Numbers, and we can borrow a similar proof technique (namely André’s reflection method) to arrive at the solution. Here is the argument: imagine the path laid out as a “mountain range” where each of the $2k-1$ steps is a move to the right and either up or down depending on whether the step was forward or backward. The diagram below illustrates a valid path for $n=2$ and $k=5$. Note that we are allowed to go negative!

We would like to exclude “bad paths” that reach $n$ at some earlier point. Consider the first point at which this occurs, and reflect the remainder of the path about the line $y=2n$. This leads to a new path that has $(k+n)$ forward steps, $(k-n-1)$ backward steps, and ends at $2n+1$ instead of $2n-1$. See the figure below for an illustration of the reflection method.

There is a one-to-one correspondence between bad paths and unconstrained paths of length $2k-1$ that reach $2n+1$. So the total number of valid paths (total paths minus bad paths) is given by:
\[
{2k-1 \choose k-n}-{2k-1 \choose k-n-1}=\frac{n}{k}{2k \choose k-n}
\]The simplification follows from (these identities), but can also be easily derived using algebra. Putting everything together, the probability of a horse first reaching $2n$ in exactly $2k$ steps is given by the formula:

$\displaystyle
P(n,k,q) = \frac{n}{k}{2k \choose k-n} q^{k+n} (1-q)^{k-n},\quad\text{for }k=n,n+1,\dots
$

We can plot the distributions for our case of interest, which is $n=100$ and $q$ varies from $0.52$ (for Horse $1$) up to $0.90$ (for Horse $20$). Here is a plot of the distributions for some of the horses:

As we can see, the distributions are normal to very good approximation. Although they are challenging expressions to manipulate, the task is not beyond the capabilities of Mathematica! In fact, we can verify that $P$ is a legitimate probability mass function and we can also compute its mean and variance for the case $\tfrac{1}{2} \lt q \le 1$:
\begin{align}
\sum_{k=n}^\infty P(n,k,q) &= 1 & & \text{(sums to 1)}\\
\sum_{k=n}^\infty k\, P(n,k,q) &= \tfrac{n}{2q-1} & & \text{(computing the mean)}\\
\sum_{k=n}^\infty \bigl(k-\tfrac{n}{2q-1}\bigr)^2 P(n,k,q) &= \tfrac{2nq(1-q)}{(2q-1)^3} & & \text{(computing the variance)}
\end{align}Here is the mean and standard deviation for a few of the horses:
\begin{align}
\text{Horse 4} &\approx 1250 \pm 218\\
\text{Horse 8} &\approx 625 \pm 74\\
\text{Horse 12} &\approx 417 \pm 37\\
\text{Horse 16} &\approx 313 \pm 21\\
\text{Horse 20} &\approx 250 \pm 12
\end{align}Note: we must double the means and standard deviations from the formulas above since those formulas skip over the odd lengths (which are impossible). When making a continuous approximation, we want those spaces filled in!

One thing we notice right away is that the distributions are very well separated (it’s a log scale!). The only horses that stand any chance of beating Horse 20 are the horses that are close behind. Let’s plot the distributions one more time, on a linear scale, but only for the top horses:

If horse $i$ finishes in $h_i$ steps, computing the probability that horse $i$ wins amounts to finding the probability that $h_i > h_j$ for all $i\ne j$. We can approximate this as:
\begin{align}
\mathbb{P}(h_i > h_j\,\,\forall i \ne j)
&\approx \int_{-\infty}^\infty \mathbb{P}(h_i = x) \prod_{j \ne i} \mathbb{P}(h_j > x)\, \mathrm{d} x\\
&= \int_{-\infty}^\infty \frac{1}{\sigma_i}\varphi_i(z_i)\prod_{j \ne i} \left( 1-\Phi(z_j)\right) \, \mathrm{d} x\\
\end{align}where $\varphi$ and $\Phi$ are the probability density (pdf) and cumulative distribution (cdf) of the standard Normal distribution and $z_k = \tfrac{x-\mu_k}{\sigma_k}$ is the standard normal deviate computed for the $k^\text{th}$ horse ($\mu_k$ and $\sigma_k$ are the mean and standard deviations computed earlier).

This is a very messy integral for which there does not exist a closed-form solution, so we must resort to evaluating it numerically. For the solution, read on!

The following table shows the probability of each horse winning the race.

As we can see, it doesn’t look good for horses 1 through 17. The top few horses are the only ones with a legitimate shot of winning!

Note: Since these probabilities were computed using a continuous approximation, I didn’t account for ties at all. If you must be a clear winner in order to be declared the winner, then the probabilities will all shift down. The effect is greatest with the first horse (probability of winning drops by about 5%), but the effect is far smaller for the other horses (Horse 18’s probability only drops by about 0.5%).