Back and forth on a line, return guaranteed?

Question

A token starts at 0 on the number line. Each step it moves +1 or -1, each with probability 1/2, and it walks forever. What is the probability the token eventually returns to 0?

Accepted Answer

A one-dimensional symmetric walk is recurrent. One way to feel it: after 2n steps the chance of being exactly at 0 is \binom{2n}{n}/2^{2n}, which shrinks only like 1/\sqrt{\pi n}. Summing these over all n diverges, and a diverging sum of return chances is exactly the condition for the walk to return with certainty (and then infinitely often). P(	ext{eventual return}) = 1. Takeaway. The 1D symmetric walk is recurrent, so returning to the start is certain; the slow 1/\sqrt{n} decay of the return chance is what guarantees it.

Back and forth on a line, return guaranteed?

Your answer

Discussion

Learn the concepts

Related questions