A simple symmetric random walk on the integers starts at 0. Show that it returns to 0 with probability 1 while the expected time of the first return is infinite, and give the decay rate of P(first return > 2n).

A simple symmetric random walk on the integers starts at 0. Show that it returns to 0 with probability 1 while the expected time of the first return is infinite, and give the decay rate of P(first return > 2n).

Approach: Use the exact identity for the probability of no return by time 2n that comes from the reflection principle, then apply Stirling to read off both the certainty of return and the tail exponent.

Return is certain and the expected first return time is infinite, with P(T > 2n) = C(2n,n)/4^n ≈ 1/sqrt(pi n). The reflection principle gives the exact identity P(S_1 ≠ 0, ..., S_{2n} ≠ 0) = C(2n,n)/4^n, which tends to 0, so the walk is recurrent and returns with probability 1. Stirling turns that expression into (pi n)^{-1/2}, and E[T] = sum_n P(T > n) then diverges like sum n^{-1/2}. The same tail drives the arcsine law: excursions away from 0 are dominated by a few very long ones, so time-averaged behaviour never settles. In two dimensions return is still certain with a slower 1/log(n) tail, and in three dimensions the return probability falls to about 0.3405.

Follow-up: Why does the same walk in three dimensions have a finite expected number of returns?

Key concepts: recurrence, reflection principle, arcsine law, first return time.