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:
- After 2n moves, there are $4^{2n}$ outcomes.
- 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.
- 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} $
- 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...