First-Return Probabilities of a Random Walk

The problem. Start at position 0. Flip a fair coin repeatedly; step $+1$ on heads, $-1$ on tails. What's the probability the walk returns to 0 for the very first time exactly at step $n$? And a follow-up that surprises most people: is the walk guaranteed to eventually return to 0, and if so, what's the expected number of steps until it does?

Why "first return" is different from "any return"

It's straightforward to compute the probability of being back at 0 at step $2k$ (returns can only happen at even steps, since parity has to match): that's $P(S_{2k}=0) = \binom{2k}{k} \left(\frac12\right)^{2k}$, just the probability of exactly $k$ heads and $k$ tails in $2k$ flips. But "first return" is stricter — it excludes any path that touched 0 earlier and came back a second time. Counting only paths that avoid 0 in between requires the reflection principle, a symmetry trick from combinatorics for counting paths that avoid a barrier.

The formula and what it says

The probability of first return to 0 exactly at step $2n$ works out to:

$$f_{2n} = \frac{1}{2n-1}\binom{2n}{n}\left(\frac12\right)^{2n}.$$

In plain English: it's the plain "back at zero at step $2n$" probability, scaled down by a factor of $\frac{1}{2n-1}$ to account for excluding paths that already visited zero earlier. As $n$ grows, $f_{2n}$ decays like $n^{-3/2}$ — slower than exponential, which is the source of the walk's strange long-run behavior.

Worked example: first return at step 2 vs step 4

At $n=1$ (step 2): $f_2 = \frac{1}{1}\binom{2}{1}\left(\frac12\right)^2 = 2 \times \frac14 = \frac12$. Check directly: the only two paths of length 2 are $(+1,-1)$ and $(-1,+1)$ — both return to 0 at step 2, and neither could have returned earlier (there's no earlier even step), so $f_2 = \frac12$ is exactly right, matching the direct count of 2 out of 4 equally likely 2-flip sequences.

At $n=2$ (step 4): $f_4 = \frac{1}{3}\binom{4}{2}\left(\frac12\right)^4 = \frac13 \times 6 \times \frac{1}{16} = \frac{6}{48} = \frac18$. So 1 in 8 walks makes it away from zero and returns for the very first time exactly at the fourth flip — noticeably rarer than an immediate step-2 return, consistent with the walk "wandering off" more often as time passes before finally coming back.

The surprising punchline: certain to return, but the average wait is infinite

Summing $f_{2n}$ over all $n$ gives exactly 1 — the walk is certain (probability 1) to eventually return to 0, no matter how far it wanders in the meantime. Yet the expected first-return time, $\sum_n 2n \cdot f_{2n}$, diverges to infinity, because $f_{2n}$ only decays like $n^{-3/2}$, which isn't fast enough for that sum to converge. This is the classic "certain but infinite expectation" phenomenon: you're guaranteed to come home eventually, but there's no finite number of steps you should bet on it taking, because rare, very-long excursions contribute enough to the average to blow it up.

Watch a handful of sample paths above: most cross back near zero fairly quickly, but occasionally one wanders far and stays away for a long stretch — those rare long excursions are exactly what makes the average return time infinite even though a return is certain.