This week’s Fiddler is a problem about probability and a slow car chase!
You and your pursuer are stopped at traffic lights one block away from each other, as shown below. For both cars, it takes 1 minute to get to each subsequent light, and there is a 50-50 chance any light will be red upon arrival (independent of what happened previously). If a light is red, you must wait one minute before it turns green. What is the probability you will make it to the city limits without being caught by your pursuer?
Extra Credit
In the same scenario as before, imagine there are infinitely many lights. On average, how many minutes will it be until you are ultimately caught?
My solution:
[Show Solution]
Can we escape before getting caught?
Let $P(n)$ be the probability that our pursuer will catch us at the $n^\text{th}$ light. To compute this probability, consider the gap between both cars. Initially, this gap is 1, and every time we reach a new light, depending on whether we got a red light and had to wait, or whether our pursuer got a red light and had to wait, the gap can change. Specifically,
- The gap does not change if we both get red lights or both get green lights, which occurs with probability $\frac{1}{4}+\frac{1}{4} = \frac{1}{2}$.
- The gap decreases by one if we get a red light and our pursuer gets a green light, which occurs with probability $\tfrac{1}{4}$.
- The gap increases by one if we get a green light and our pursuer gets a red light, which occurs with probability $\tfrac{1}{4}$.
Initially, both cars have green lights, and since we get caught on the $n^\text{th}$ light, our final light must be red and our pursuer’s final light must be green. This leaves $n-2$ intermediate lights, at which the distance can either increase, decrease, or stay the same. If the distance could only increase or decrease, the total number of ways would be given by $C_{(n-2)/2}$, where $C_n$ is the $n^\text{th}$ Catalan number (see the interpretation of Catalan numbers as “counting mountain ranges”).
In our case, the gap can also stay constant, which complicates matters slightly. If we assume there are $k$ “ups” and $k$ “downs”, this leaves $n-2-2k$ “flats”. It follows that the total number of mountain ranges that may include plateaus is given by:
\[
\sum_{k=0}^{\left\lfloor \tfrac{n-2}{2} \right\rfloor} C_k \binom{n-2}{2k}
\]Each such path has a probability of occurring that depends on the number of flats, namely, it is
\[
\left(\frac{1}{4}\right)^{2k+1} \left(\frac{1}{2}\right)^{n-2-2k}
\]The reason for the $2k+1$ in the first term is that we must account for the “down” at the very end of the path. Putting everything together and substituting the formula for the Catalan number in, we obtain:
\[
P(n) = \sum_{k=0}^{\left\lfloor \tfrac{n-2}{2} \right\rfloor}
\frac{1}{k+1}\binom{2k}{k} \binom{n-2}{2k} \left(\frac{1}{4}\right)^{2k+1} \left(\frac{1}{2}\right)^{n-2-2k}
\]Amazingly, this sum has a closed-form formula, which I found using Mathematica. The probability that our pursuer will catch at the $n^\text{th}$ light is given by:
$\displaystyle
P(n) = \begin{cases}
\displaystyle\frac{1}{4^n\bigl(n-\tfrac{1}{2}\bigr)} \binom{2n}{n} & \text{for }n=2,3,4,\dots \\[1mm]
0 & \text{otherwise}
\end{cases}
$
We can double check that this is a legitimate probability distribution by verifying that $\sum_{n=2}^\infty P(n) = 1$. In other words, we will eventually be caught, it’s just a matter of when. I used Mathematica to evaluate the infinite sum, and it is indeed equal to one!
If we have $n$ lights to go before we reach the city limit, the probability we will escape before getting caught is $1-\sum_{k=2}^n P(k)$, or in other words:
\[
\text{Prob}(\text{escape}) = 1-\sum_{k=2}^n \frac{1}{4^k\bigl(k-\tfrac{1}{2}\bigr)} \binom{2k}{k}
\]Amazingly, this also has a closed-form expression… and thanks again to Mathematica, it is given by:
$\displaystyle
\text{Prob}(\text{escape}) = \begin{cases}
\displaystyle\frac{2}{4^n} \binom{2n}{n} & \text{for }n=2,3,4,\dots \\[1mm]
0 & \text{otherwise}
\end{cases}
$
This is an embarrassingly simple-looking expression, so there is likely a more elegant solution waiting to be found. The solution includes a denominator $4^n$ which is the total number of ways of assigning $\{\text{red},\text{green}\}$ to each of the $2n$ lights. The numerator is $2\binom{2n}{n}$, which must be the number of light assignments that do not lead to capture. If you can figure this out, please let me know in the comments!
In the original problem, we had 5 lights ahead of us, so substituting $n=5$, we obtain a probability of escape of $\frac{63}{128}$, or approximately 49.2%.
We can also check whether our formula holds up numerically. In the plot below, I compare the empirical probability from running 1,000,000 Monte Carlo simulations, and the analytic formula produced above, and we observe that we have a perfect match.
Note: This problem is somewhat similar to an old Riddler problem from 2017 about a horse race. You can check out my write-up for that problem if you’re interested!
Extra credit: time until caught
It takes at least one minute per light to visit all the lights (possibly more, depending on how many times we stop for red lights). Therefore, whenever we are eventually caught, the number of minutes that elapsed must be at least as much as the number of lights we saw.
We are asked to calculate the expected time elapsed until capture. Based on the argument above, we must have:
\[
\mathbb{E}(\text{lights seen until capture}) \leq
\mathbb{E}(\text{time until capture})
\]Let’s calculate the left-hand side. We already calculated $P(n)$, which is the the probability that we will be captured after seeing exactly $n$ lights. Therefore, the left-hand side is equal to $\sum_{n=2}^\infty n P(n)$. It turns out that this sum does not converge!. To see why, we can use the following asymptotic formula (source), which holds as $n\to\infty$.
\[
\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}
\]This leads us to the approximation
\[
P(n) \sim \frac{1}{\bigl(n-\tfrac{1}{2}\bigr)\sqrt{\pi n}}
\]And now we see why there is no convergence… The function $n P(n)$ decays like $\frac{1}{\sqrt{n}}$, and therefore is not summable (it is a $p$-series with $p=\tfrac{1}{2}$). Since the expected number of lights is unbounded, then the time until capture must also be unbounded.
But does this make any sense? A probability distribution that has no average? Yes! In general, distributions for which some of the moments are unbounded are called heavy-tailed distributions, and there are many well-known examples. In particular, examples of distributions with unbounded first moments (average does not exist) include the Cauchy distribution, the Pareto distribution, and $P(n)$ defined above.