Simple Symmetric Random Walk : $P_{00}^{2n}=\binom{2n}{n}\left(\dfrac{1}{2}\right)^{2n}$

Question

I was studying Simple Symmetric Random Walks and my notes state (without proof) that $$P_{00}^{2n}=\binom{2n}{n}\left(\dfrac{1}{2}\right)^{2n}$$ That is the probability of going from $0$ to $0$ in $2n$ steps is the RHS.

Stuff I know:

• Simple Symmetric RVs have a period of 2.
• Probability of going left or right is equal to $0.5$
• I understand that the $\left(\dfrac{1}{2}\right)^{2n}$ has to do with the $2n$ steps I take in order to get back to $0$.

Stuff I don't know:

• Where does the $\binom{2n}{n}$ come from?

Answer 1

Let $\{s_n\}_{n\in\mathbb N}$ be a simple symmetric random walk, then $s_{2n}=0$ iff there exist $u,d\in\mathbb N$ ($u$=#up-steps, $d$=#down-steps) such that $$ \begin{cases} u+d = 2n \\ u-d = 0 \end{cases} \quad\longrightarrow\quad \begin{cases} u = n \\ d = n \end{cases} $$ Now, since $s_{2n}$ does not depend on the order in which up-steps or down-steps occurred, you have exactly $\binom{2n}{n}$ choices of taking $n$ up-steps and $n$ down-steps, each with probability $2^{-2n}$, which proves your result.

More generally, the same reasonings shows that if you consider a simple random walk $\{s_n\}_{n\in\mathbb N}$ in which you go up with probability $p$ and down w.p. $1-p$ you have $$ \mathbb P(s_n=n-2x) = \binom nxp^x(1-p)^{n-x} $$ for $x=0\ldots n$.

Answer 2

There are $2n \choose n$ ways to go from 0 to 0 in $2n$ steps.

If $n=1$, 2 ways: 0->-1->0 or 0->-1->0

If $n=2$, 6 ways: 0->1->2>1->0, 0->1->0->1,0, and so on.

Essentially it is a simple counting argument: out of $2n$ choices you make for the direction of traversal, you could choose exactly $n$ of them for, say moving in -> direction. In the remaining $n$ steps, you move in <- direction and reach 0 again in $2n$ steps.