Proving that 11- and 2D2D simple symmetric random walks return to the origin with probability 11

How does one prove that a simple (steps of length 1 in directions parallel to the axes) symmetric (each possible direction is equally likely) random walk in 1 or 2 dimensions returns to the origin with probability 1?

Edit: note that while returning to the origin is guaranteed (p=1) in 1 and 2 dimensions, it is not guaranteed in higher dimensions; this means that something in a correct justification for the 1– or 2D cases must fail to extend to 3D (or fail when the probability for each direction drops from 14 to 16).

Answer

See Durrett, Probability: Theory and Examples (link goes to online copy of the fourth edition; original defunct link). On p. 164 Durrett gives a proof that simple random walk is recurrent in two dimensions.

First find the probability that simple random walk in one dimension is at 0 after 2n steps; this is clearly \rho_1(2n) = \binom{2n}{n}/2^{2n}, since \binom{2n}{n} is the number of paths with n right steps and n left steps.

Next, the probability that simple random walk in two dimensions — call this \rho_2(2n) — is at 0 after 2n steps is the square of the previous probability. Consider the simple random walk which makes steps to the northeast, northwest, southeast, and southwest with equal probability. The projections of this walk onto the x- and y-axes are independent simple random walks in one dimension. Rotating and rescaling gives the “usual” SRW in two dimensions (with steps north, east, south and west) and doesn’t change the probability of being at 0.

So \rho_2(2n) = \left(\binom{2n}{n}/2^{2n}\right)^2. This is asymptotic to 1/(\pi n), and the expected number of returns to the origin is the \sum_{n \geq 1} \rho_2(2n), so the expected number of returns to the origin is infinite. It’s not hard to show (and is in fact true, but the proof is unenlightening so I’ll leave it to Durrett) that in this case the probability of eventually returning to the origin is 1.

Attribution
Source : Link , Question Author : Isaac , Answer Author : Jam

Leave a Comment