Multi Dimensions

Solution

Let \(S_n\) be your position after \(n\) moves. The question is asking for the probability that the random walk ever returns to the starting point, which we take to be the origin. The clean way to study this is to look at \[ P(S_n=0), \] the probability that after exactly \(n\) moves you are back where you started. What matters is how these probabilities add up over time. If the total sum \[ \sum_{n=0}^{\infty} P(S_n=0) \] diverges, then the walk returns to the origin with probability \(1\). If the sum converges, then there is a genuine chance that the walk drifts away forever, so the return probability is strictly less than \(1\). The whole problem is therefore about how quickly \[ P(S_n=0) \] shrinks as \(n\) becomes large. \[ \text{2D case} \] In two dimensions, each move is one of \[ (1,0),\; (-1,0),\; (0,1),\; (0,-1), \] each with probability \(1/4\). You can only return to the origin after an even number of moves, because every move changes the parity of the total distance from the origin. So we only need to look at times \(2n\). To be back at the origin after \(2n\) moves, the horizontal moves must cancel and the vertical moves must cancel. Suppose exactly \(2k\) of the \(2n\) moves are horizontal. Then the remaining \(2n-2k\) moves are vertical. Among those \(2k\) horizontal moves, you must have \[ k \text{ right moves and } k \text{ left moves}. \] The number of ways this can happen is \[ \binom{2k}{k}. \] Among the \(2n-2k\) vertical moves, you must have \[ n-k \text{ forward moves and } n-k \text{ backward moves}. \] The number of ways this can happen is \[ \binom{2n-2k}{\,n-k\,}. \] You also have to choose which \(2k\) of the \(2n\) time slots are used for horizontal motion, which can be done in \[ \binom{2n}{2k} \] ways. So the total number of return paths of length \(2n\) is \[ \sum_{k=0}^{n} \binom{2n}{2k} \binom{2k}{k} \binom{2n-2k}{n-k}. \] Each path of length \(2n\) has probability \[ \left(\frac14\right)^{2n}, \] so \[ P(S_{2n}=0) = \left(\frac14\right)^{2n} \sum_{k=0}^{n} \binom{2n}{2k} \binom{2k}{k} \binom{2n-2k}{n-k}. \] This simplifies to the exact formula \[ P(S_{2n}=0)=\frac{1}{4^{2n}}\binom{2n}{n}^2. \] That is the exact probability of being back at the origin after \(2n\) moves in \(2\)D. Now use the standard approximation for the central binomial coefficient: \[ \binom{2n}{n}\sim \frac{4^n}{\sqrt{\pi n}}. \] Substituting this into the formula gives \[ P(S_{2n}=0) = \frac{1}{4^{2n}}\binom{2n}{n}^2 \sim \frac{1}{4^{2n}} \cdot \frac{16^n}{\pi n} = \frac{1}{\pi n}. \] So for large \(n\), \[ P(S_{2n}=0)\sim \frac{1}{\pi n}. \] Now sum over all even times: \[ \sum_{n=1}^{\infty} P(S_{2n}=0) \sim \sum_{n=1}^{\infty} \frac{1}{\pi n}. \] But \[ \sum_{n=1}^{\infty} \frac{1}{n} \] is the harmonic series, and it diverges. So \[ \sum_{n=0}^{\infty} P(S_n=0)=\infty. \] That means the walk is recurrent, so the probability of ever returning to the starting point is \[ 1. \] So in two dimensions, the odds of eventually returning are \[ 100\%. \] The intuition is that in a plane, the walk keeps wandering across territory it has already visited. It does not have enough room to escape permanently. \[ \text{3D case} \] Now add a third dimension. The possible moves are \[ (\pm1,0,0),\; (0,\pm1,0),\; (0,0,\pm1), \] each with probability \(1/6\). The same general idea applies: we study \[ P(S_n=0). \] In three dimensions, the exact counting is more complicated, but the important large-\(n\) behavior is known: \[ P(S_{2n}=0)\sim \frac{C}{n^{3/2}} \] for some constant \(C>0\). The exponent is the crucial part. In \(2\)D the decay was like \[ \frac{1}{n}, \] but in \(3\)D it decays faster, like \[ \frac{1}{n^{3/2}}. \] Now look at the sum: \[ \sum_{n=1}^{\infty} P(S_{2n}=0) \sim \sum_{n=1}^{\infty} \frac{C}{n^{3/2}}. \] This converges, because \[ \sum_{n=1}^{\infty} \frac{1}{n^{3/2}} < \infty. \] So in three dimensions, \[ \sum_{n=0}^{\infty} P(S_n=0)<\infty. \] That means the walk is transient, so the probability of ever returning is strictly less than \(1\). For the simple random walk on \(\mathbb{Z}^3\), the actual return probability is approximately \[ 0.3405. \] So in three dimensions, the odds of ever returning to the starting point are about \[ 34.05\%. \] The probability of never returning is therefore about \[ 1-0.3405=0.6595. \] So there is about a \[ 65.95\% \] chance of drifting away forever.