# Random walk returning probability: Back to the origin

Considering a discrete random walk in 2D starting from $$(0,0)$$ with 1/4 probability of moving in each of the four directions for each step, calculate the probability of returning to $$(0,0)$$ after $$2n$$ moves.

For instance, the probability for the point returing to its origin (0,0) after $$2$$ moves is: $$4/4^2 = 0.25$$.

I have got an answer as follows, but I think it is not elegant:

1. After 2n moves, there are $$4^{2n}$$ outcomes.
2. Let A be the event in which the point returns, and $$n(A_{n})$$ be the number of outcomes in event A. Suppose A include the point moving upwards and downwards $$k$$ times(so that the point will not shift in the y-axis direction), and rightwards and leftwards $$(n-k)$$ times. In such case, there are $$\displaystyle{\frac{(2n)!}{[k!k!(n-k)!(n-k)!]}}$$ outcomes.
3. Sum up to get event A: $$\begin{eqnarray} n(A_{n}) &=& \displaystyle{\sum^{n}_{k=0}\frac{(2n)!}{(k!)^2[(n-k)!]^2}}= \displaystyle{\frac{(2n)!}{(n!)^2}}\sum_{k=0}^{n} \left[ \frac{n!}{k!(n-k)!} \right]^2 \\ &=& \displaystyle{ \binom{2n}{n} \sum_{k=0}^{n}}\binom{n}{k}^2 = \displaystyle{\binom{2n}{n}^2} \\ \text{because} \displaystyle{ \sum_{i=0}^{n}\binom{n}{i}^2=\binom{2n}{n}} \end{eqnarray}$$
4. Hence, the probability of returning is $$P(A_n)=\displaystyle{\frac{ \binom{2n}{n}^2}{4^{2n}} }$$

Obseving the numerator I think there might be some easy ways to figure out the answer:

Since the point " moves upwards and downwards $$k$$ times ", and " leftwards and rightwards $$(n-k)$$ times ", if combining the number of steps moving $$\color{red}{up}$$ and $$\color{red}{right}$$ it would be $$\color{red}{n}$$ steps in total, and choose $$\color{red}{n}$$ steps from $$2n$$, there would be $$\color{fuchsia}{\binom{2n}{n}}$$ possibilities.

Considering the answer above $$P(A_n)=\displaystyle{\frac{ \binom{2n}{n}^2}{4^{2n}} }$$, the product and numerator $$\binom{2n}{n} \binom{2n}{n}$$ must contain the event $$A$$, which is "the point moves upwards and downwards $$k$$ times , and leftwards and rightwards $$(n-k)$$ times.

Let the first part $$\binom{2n}{n}$$ contain "moving $$n$$ steps leftwards and upwards in total", and let the second part $$\binom{2n}{n}$$ contain "moving $$n$$ steps rightwards and upwards in total". Together, I get the event $$A$$, but I don't know how to proceed...

• This looks fine to me. Simple and straightforward. Jul 28, 2021 at 13:59
• @saulspatz Looking forward to your solutions ;)
– Tim
Jul 29, 2021 at 11:58

Consider the North-west and north-east directions, each step must increase/decrease the random walk in these directions by one unit. To get back to the origin then, we need both to cancel out, so you need $${{2n} \choose {n}}^2/{4^{2n}}$$