Symmetric Random walk on $\mathbb {Z}^d$

Question

Consider the symmetric random walk on $\mathbb{Z}^d $. Symmetric means that the probability of going into any of the $2^d$ directions is $1/2^d$. Starting in 0, what is the probability of returning to 0 in n steps?

---

My solution is

$$ p_{00}^{(n)}=\binom {n}{n/2}^d \frac{1}{2^{dn}}. $$

Because for each dimension the steps in the one direction have to be the same as in the opposite direction and for each dimension there a $\binom {n}{n/2}$ possibilities to do so.

Am I right?

Answer 1

No. This time, there are $2d$ directions to choose from.

From the formula for $d=2$, you will have to change the binomial coefficient to $$ \frac {n!}{\left(a_1!\right)^2 \left(a_2!\right)^2\dots \left(a_{d}!\right)^2 }$$for every choice of $a_1\dots a_{d}$ so that $\sum_{i=1}^{d} a_i = n/2$ ($a_i$ is the number of moves made in the direction $+ e_i$) and the probability replaced accordingly by $$ \prod_{i=1}^{d} \left(\frac1{2d}\right)^{2a_i} $$

Then the global answer is $$ p_{d,n} = \sum_{\sum_{i=1}^{d} a_i=n/2} \frac {n!}{\left(a_1!\right)^2 \left(a_2!\right)^2\dots \left(a_{d}!\right)^2 } \prod_{i=1}^{d} \left(\frac1{2d}\right)^{2a_i} $$

Answer 2

Your formula works correctly for $d=1$ (of course) and also for $d=2$. The way to see $d=2$ is that each step changes $x+y$ by $\pm 1$ each with probability $\frac{1}{2}$ and also, each step changes $x-y$ by $\pm 1$ each with probability $\frac{1}{2}$, and those results are independent. So it is valid to multiply the two individual probabilities of ending at the origin, which is what your formula does.

Unfortunately, for $d >2$ (random walk in more than 2 dimensions), there is no similar clever reason why your formula would work. And in fact, for a 2-step random walk in 3 dimensions, the probability of ending at the origin is $\frac{1}{6}$ whilst your formula gives an answer of $\frac{1}{8}$.

(I've always wanted to use the word "whilst" in a sentence.)