Guaranteed to arrive, yet the average wait is infinite

Question

A fair random walk starts at 0 and steps +1 or -1 with probability 	frac12 each. Let T be the first time it reaches +1. Show that the walk reaches +1 with probability 1, yet the expected time E[T] to get there is infinite.

Accepted Answer

It arrives with certainty. A one-dimensional symmetric walk is recurrent, it returns to every level infinitely often. One clean argument: let r be the probability of ever reaching +1 from 0. By the self-similar step logic, reaching +1 from -1 means going up two levels, so r = 	frac12 + 	frac12 r^2 (go up now, or go down and then climb two levels each with probability r). This gives r^2 - 2r + 1 = 0, i.e. (r-1)^2 = 0, so r = 1. The walk is guaranteed to touch +1 eventually. But the average wait is infinite. Suppose, for contradiction, that m = E[T] were finite. Condition on the first step: -…

Guaranteed to arrive, yet the average wait is infinite

Your answer

More Probability questions