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 $\frac{1}{4}$ to $\frac{1}{6})$.
Best 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$.