Three-Dimensional Random Walk

Question

A particle starts at an origin $O$ in three-space. Thinking of point $O$ as the center of a cube 2 units on a side. One move in this walk sends the particle with equal likelihood to one of the eight corners of the cube. That is to say, at every walk, the particle has a 50/50 chance of moving one unit up or down, one unit left or right, and one unit front or back. If this walk continues infinitely, what is the probability that the particle returns to $O$?

So far, I thought of the following: $$P(\text{particle is at $O$ after $2n$ walks})=\left(\binom{2n}{n}\left(\dfrac{1}{2}\right)^{2n}\right)^3$$ I then applied Stirling's approximation: $n!\sim\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}$ to get $$P(\text{particle is at $O$ after $2n$ walks})\approx\left(\dfrac{1}{\pi n}\right)^{\frac{3}{2}}$$ I then tried to sum this: $$P(\text{particle returns to $O$})=\sum_{n=1}^\infty \left(\dfrac{1}{\pi n}\right)^{\frac{3}{2}}\approx 0.47 $$

Unfortunately, this answer is incorrect and I suspect that there is a problem with the values of my summation.

Answer 1

One mistake is that you have approximated the expected number of times of return to the origin, rather than the probability of at least one return. They are related by $$ P=\frac{<n>}{<n>+1} $$ so your approximation should be giving a probability of about $\frac13$. The real value of the sum you have done is $$ \frac{\pi}{\Gamma\left(\frac34\right)^4}-1 \approx 0.3932$$ giving $$ P = 1 - \frac{\Gamma\left(\frac34\right)^4}{\pi} \approx 0.2822 $$

This would not be be the correct answer for a random walk on the edges of a cubic lattice, since in that case the three distinct dimensions will not necessarily have taken the same number of steps at the time of return to origin. In fact, for that random walk, $$ <n>_{\mbox{cubic}} +1 = \frac{\sqrt{6}}{32\pi^3} \Gamma\left(\frac1{24}\right)\Gamma\left(\frac5{24}\right)\Gamma\left(\frac7{24}\right)\Gamma\left(\frac{11}{24}\right)-1 \approx 1.5164 $$ and $$ P_{\mbox{cubic}} = 1-\frac1{<n>_{\mbox{cubic}}+1}\approx 0.3405$$ Thus the return probability for the walk you presented, which is an octahedral random walk, is somewhat easier to compute in your head than is the probability for a cubic random walk -- you just need a really large and well-oiled head!

Answer 2

The number of ways to get back to $O$ after $2n$ moves is given by

$$\begin{align} \sum_{r+s+t=n}\binom{2n}{r,r,s,s,t,t} &=\sum_{r+s+t=n}\binom {\color{magenta}{2n}}{\underbrace{r,s,t}_{\color{magenta}n},\underbrace{r,s,t}_{\color{magenta}n}}\\ &=\sum_{r+s+t=n}\left[\color{magenta}{\binom {2n}n}\binom nr\binom {n-r}s\color{lightgrey}{\binom {n-r-s}t}\right] \left[\color{magenta}{\binom nn}\binom nr\binom {n-r}s\color{lightgrey}{\binom {n-r-s}t}\right]\\ &=\binom {2n}n\sum_{r=0}^n\binom nr ^2 \;\sum_{s=0}^{n-r}\binom {n-r}s ^2\\ &=\binom {2n}n\sum_{r=0}^n \binom nr ^2\binom {2(n-r)}{n-r}\\ &=\color{red}{\binom {2n}n\sum_{r=0}^n \binom nr ^2\binom {2r}r\qquad\blacksquare}\end{align}$$

Hence, the probability of getting back to $O$ after $2n$ moves is given by $$\color{red}{\frac 1{6^{2n}}\binom {2n}n\sum_{r=0}^n\binom nr^2\binom {2r}{r}}$$

NB: There does not seem to be a closed form for $(*)$. See this OEIS series here. See also this note here on random walks.

---

(Previous answer below) $$\tiny\begin{align} \sum_{r+s+t=n}\binom {2n}{r,s,t,r,s,t} &= \sum_{r+s+t=n}\binom {2n}r \binom {2n-r}s\binom {2n-r-s}t\binom nr\binom {n-r}s\overbrace{\binom {n-r-s}t}^1\\ &=\sum_{r+s+t=n}\binom{2n}{2n-r}\binom {2n-r}{\color{orange}{2n-r-s}}\binom {\color{orange}{2n-r-s}}n\binom nr\binom {n-r}s\\ &=\sum_{r+s+t=n}\binom {2n}{\color{blue}{2n-r}}\binom {\color{blue}{2n-r}}{\color{}n}\binom {n-r}{n-r-s}\binom {n}r\binom {n-r}s\\ &=\binom {2n}n\sum_{r+s+t=n}\binom n{n-r}\binom {n-r}{s}\binom nr\binom {n-r}s\\ &=\binom {2n}n\sum_{r+s+t=n}\binom nr^2\binom {n-r}s^2\\ &=\binom {2n}n\sum_{r=0}^n\binom nr^2\sum_{s=0}^{n-r}\binom{n-r}s^2\\ &=\binom {2n}n\sum_{r=0}^n\binom nr^2\binom {2(n-r)}{n-r}\\ &=\binom {2n}n\sum_{r=0}^n\binom nr^2\binom {2r}{r}\tag{*}\\ \end{align}$$