Can You Ride out the Slow Car Chase?

You are in a car chase in which both cars obey every traffic law and stop at every red light. You are one block ahead of your pursuer, and both of you are waiting at red lights. The lights turn green together, and both cars head east at one block per minute.

At every intersection the light is green with probability $\tfrac12$, and you coast through, or red with probability $\tfrac12$, and it turns green after exactly one minute. Your pursuer’s lights behave the same way, independently of yours, even at the same intersections. Counting the light you are stopped at, there are five lights between you and the city limit, so six for your pursuer. How likely are you to cross the city limit without being caught?

The Fiddler, Zach Wissner-Gross, October 20, 2023(original post)

The official solution appeared in the post of October 27, 2023 and gives $63/128$ for the main puzzle and an infinite average for the Extra Credit. Both agree with the answers below.

Solution

Number the blocks so that you start at block $1$ and your pursuer at block $0$; the city limit is just past block $5$. Both cars move at the same speed, so the pursuer can never close the gap on the road. It can only catch you while you are waiting at a red light.

When are you caught? Call your lights at blocks $2, 3, 4, 5$ your first, second, third and fourth lights, and the pursuer’s lights at blocks $1, 2, 3, 4$ its first to fourth. Let $Y_N$ and $P_N$ be the number of reds you and the pursuer meet among your first $N$ lights. You leave block $N + 1$ at time $N + Y_N$: $N$ minutes of driving and $Y_N$ minutes of waiting, the last possibly at block $N + 1$ itself. The pursuer reaches block $N + 1$ at time $N + 1 + P_N$. So it catches you there exactly when $$N + 1 + P_N \;\le\; N + Y_N, \qquad\text{that is,}\qquad D_N = P_N - Y_N \le -1 .$$ (When it happens, the pursuer pulls up just as your light turns green: the official solution counts that as caught, and so does this one.) So you escape exactly when the pursuer’s extra waiting, $D_N$, stays at $0$ or more for $N = 1, 2, 3, 4$.

A walk made of coin flips. At each light $D$ goes up by $1$ (your light green, theirs red), down by $1$ (the reverse), or stays put (both the same), with probabilities $\tfrac14, \tfrac14, \tfrac12$. Here is the one idea of the solution. Score each light as a fair coin flip of $\pm 1$: the pursuer’s light $+1$ for red and $-1$ for green, and yours $+1$ for green and $-1$ for red. Half the sum of the two scores is exactly the change in $D$ (check the four cases). So after $N$ pairs of lights, $$D_N \;=\; \tfrac12 S_{2N},$$ where $S_j$ is the running total of $j$ fair coin flips of $\pm 1$: a simple random walk, taking $8$ steps in all for the four pairs of lights. You escape exactly when $S_2, S_4, S_6, S_8$ are all at least $0$. A walk of $\pm 1$ steps is even after an even number of steps and odd after an odd number, so this is the same as saying that the walk never reaches $-2$ in its $8$ steps.

Counting with a mirror. Of the $2^8 = 256$ walks, those ending at $e$ number $\binom{8}{(8 + e)/2}$:

An escaping walk ends at $0$ or above. Some walks that end at $0$ or above do reach $-2$ along the way. Take such a walk and reflect everything after its first visit to $-2$, mirroring it in the level $-2$; it now ends at $-4 - e$, which is $-4$ or below. Every walk ending at $-4$ or below must pass $-2$, and reflecting it back recovers the original, so these bad walks match up one to one with the $28 + 8 + 1 = 37$ walks ending at $-4$ or below. The escapes are the $70 + 56 + 28 + 8 + 1 = 163$ walks ending at $0$ or above, less these $37$: that is $126$, exactly the walks ending at $0$ or $2$. So $$\boxed{\ P(\text{escape}) \;=\; \frac{126}{256} \;=\; \frac{63}{128} \;\approx\; 49.2\% . \ }$$

The computation

The check makes no use of the walk. It replays the chase minute by minute for all $2^9$ equally likely patterns of red and green at the lights that matter (your four after the start, the pursuer’s five) and adds up the probability of the patterns in which the pursuer never reaches you while you are still at an intersection.

from fractions import Fraction
from itertools import product

def caught(mine, theirs):
    """Replay the chase minute by minute. I wait at block 1
    and the pursuer at block 0; both lights turn green at time
    0 and the city limit is just past block 5. mine[k] and
    theirs[k] are 1 if the light at block k is red when that
    car arrives (a red light costs one minute), else 0."""
    leave_me, t = {1: 0}, 0
    for k in range(2, 6):
        t = t + 1 + mine[k]            # one block, then wait
        leave_me[k] = t
    t = 0
    for k in range(1, 6):
        t = t + 1                      # pursuer arrives at k
        if k >= 2 and t <= leave_me[k]:
            return True                # I am still there
        t = t + theirs[k]
    return False

escapes = Fraction(0)
for bits in product([0, 1], repeat=9):
    mine = dict(zip(range(2, 6), bits[:4]))
    theirs = dict(zip(range(1, 6), bits[4:]))
    if not caught(mine, theirs):
        escapes += Fraction(1, 2 ** 9)
print("main: escape with probability", escapes)

It prints

main: escape with probability 63/128

Extra Credit

Now the city goes on for ever. Starting as before, how many minutes, on average, until you are caught?

Solution

The mirror argument works for any number of lights. You are still free after $n$ pairs of lights exactly when the walk of $2n$ steps has not reached $-2$, and the same reflection shows that these walks are the ones ending at $0$ or $2$. So $$P(\text{free after } n \text{ lights}) \;=\; \frac{\binom{2n}{n} + \binom{2n}{n+1}}{4^n} \;\ge\; \frac{\binom{2n}{n}}{4^n} .$$ This shrinks to zero, so you are caught in the end with certainty. But it shrinks slowly. Write $\binom{2n}{n}/4^n$ as a product, $$c_n \;=\; \frac12 \cdot \frac34 \cdot \frac56 \cdots \frac{2n - 1}{2n} .$$ Each factor $\frac{2k-1}{2k}$ with $k \ge 2$ is at least $\frac{2k-2}{2k-1}$, since $(2k - 1)^2 \ge 2k(2k - 2)$. So $c_n$ is at least $\frac12 \cdot \frac23 \cdot \frac45 \cdots \frac{2n-2}{2n-1}$, and multiplying $c_n$ by this second product makes almost everything cancel: $$c_n^2 \;\ge\; \frac12 \cdot \frac12 \cdot \frac24 \cdot \frac46 \cdots \frac{2n - 2}{2n} \;=\; \frac{1}{4n}, \qquad\text{so}\qquad c_n \;\ge\; \frac{1}{2\sqrt{n}} .$$ The average number of lights $T$ you pass before being caught is the sum of the chances of still being free after $0, 1, 2, \dots$ lights (each light you get past adds one to $T$). So $$E[T] \;\ge\; 1 + \sum_{n \ge 1} \frac{1}{2\sqrt{n}} ,$$ and this sum has no limit: its terms shrink too slowly (the first $m$ of them add up to more than $\tfrac12\sqrt{m}$, since each is at least $\frac{1}{2\sqrt m}$). Every light passed takes at least a minute, so $$\boxed{\ \text{the average time until you are caught is infinite}. \ }$$ Capture is certain, yet its average time is infinite: long escapes are rare, but not rare enough. The median, by contrast, is short. You are still free after three lights with chance $35/64$ and after four with $63/128$, so half of all chases are over by the fourth light.

The computation

An infinite average cannot be printed, but its signature can. The program tracks the exact distribution of the pursuer’s extra waiting, light by light, as the replay above defines it, dropping the cases in which you have been caught. It reports the chance of still being free after $n$ lights and the lower bound for the average number of lights given by the first $n$ of them. The chance falls roughly like $1/\sqrt{n}$, and the bound keeps climbing, roughly like $\sqrt{n}$, with no sign of levelling off.

# Endless city. As the replay shows, after each pair of lights
# the pursuer's lateness behind me changes by (their red) minus
# (my red); I am caught once it drops below zero. Track its
# distribution exactly, light after light.
lead = {0: 1.0}           # lateness -> probability, not caught
survive = []
for n in range(1, 2001):
    new = {}
    for d, p in lead.items():
        for step, q in ((-1, 0.25), (0, 0.5), (1, 0.25)):
            if d + step >= 0:
                new[d + step] = new.get(d + step, 0) + p * q
    lead = new
    survive.append(sum(lead.values()))
for n in (10, 100, 1000, 2000):
    s, low = survive[n - 1], 1 + sum(survive[:n])
    print(f"{n:4} lights: free {s:.4f}, mean >= {low:.1f}")

It prints

  10 lights: free 0.3364, mean >= 5.7
 100 lights: free 0.1121, mean >= 20.8
1000 lights: free 0.0357, mean >= 69.4
2000 lights: free 0.0252, mean >= 99.0