3
$\begingroup$

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...

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

1 Answer 1

1
$\begingroup$

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}}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.