# Random walk - Solution verification

A particle moves randomly 2n times. Each time it chooses one direction: north, south, west, east with even probability and without effect from previous choices, it then moves one step in that direction. What is the probability that the particle will end up in the same spot it started?

What I did:

There are $4$ choices for each of $2n$ steps. Therefore $|\Omega|=4^{2n}$.

We'll mark $N=|steps\space north|,\space S=|steps\space south|,\space W=|steps\space west|,\space E=|steps\space east|$. To end up in the same spot we started, we need $N=S$ and $W=E$. Therefore $N+W=n$ and $S+E=n$. Therefore if we choose $n$ of the $2n$ steps $[\binom {2n}{n}]$ to only be composed of steps $north\cup west$ ($2$ choices for each of $n$ steps $[2^n]$). Out of the $n$ "leftover" steps, $S$ are south $[\binom {n}{S}]$. Therefore: $$P(\text{The particle ends up where it started})=\frac{ \sum\limits_{S=0}^n\binom {2n} {n} 2^n \binom {n}{S}}{4^{2n}}$$

Thank you for your time and effort.

Assume that $n=2N$. There are ${2N\choose N}$ ways to choose the times of the N-or-W steps. For each $0\leqslant k\leqslant N$, there are ${N\choose k}$ ways of choosing $k$ times of N-steps amongst the $N$ times of the N-or-W steps. Then one must also choose $k$ times of S-steps amongst the $N$ times of the S-or-E steps. There are ${N\choose k}$ ways of doing that. Hence the number of paths of length $2N$ ending at $(0,0)$ is $$P_N={2N\choose N}\sum_{k=0}^N{N\choose k}^2,$$ and the probability you are after is $P_N/4^{2N}$. (Of course, the sum over $k$ in $P_N$ has a simpler expression and the resulting formula for $P_N$ can be recovered more directly but I am not sure you are after this...)

• That's the same answer, as ${2N\choose N}\sum_{k=0}^N{N\choose k}^2 = {2N\choose N}2^N\sum_{k=0}^N{N\choose k}$. Thank you. – yuvalz May 24 '13 at 11:37
• Sorry but $\sum\limits_{k=0}^N{N\choose k}^2={2N\choose N}$ while $2^N\sum\limits_{k=0}^N{N\choose k}=4^N$. – Did May 24 '13 at 11:50
• Right, I got the binomial thing messed up. What's the fault with my original solution then? – yuvalz May 24 '13 at 12:01
• If one knows the number of S steps, each N-or-W step is not free since one needs the exact same number of N steps. Hence your factor $2^n$ is bogus. – Did May 24 '13 at 12:50