A drunkard takes a simple symmetric random walk on the integer lattice, one step per minute to a uniformly chosen neighbour. Compare the probability of ever returning to the starting point in one, two and three dimensions, and give the three dimensional value.

A drunkard takes a simple symmetric random walk on the integer lattice, one step per minute to a uniformly chosen neighbour. Compare the probability of ever returning to the starting point in one, two and three dimensions, and give the three dimensional value.

Approach: Decide recurrence by asking whether the expected number of visits to the origin is finite, using the decay rate of the probability of being at the origin after 2n steps.

0.3405. The return probability is 1 in one and two dimensions and about 0.3405 in three. The test is whether u = sum_n P(S_n = 0), the expected visits to the origin, is finite. The local central limit theorem gives P(S_{2n} = 0) of order n^{-d/2}, so the sum diverges for d = 1 and d = 2, forcing infinitely many returns, and converges for d = 3. Since the number of visits is geometric with success probability equal to the return probability p, u = 1/(1 - p). In three dimensions u = 1.5164, so p = 1 - 1/1.5164 = 0.3405. The walk is recurrent in the plane and transient in space, so a walker on a grid of streets always gets home and one in space usually does not.

Follow-up: What is the expected number of returns to the origin for the three dimensional walk, and how does it change if the walk is on a lattice of dimension 4?

Key concepts: recurrence, expected visits, local central limit theorem.