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

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

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

-
When you say you have choose(2n,n) choices of going up n and going down n, how do you make sure all these choices are valid? Like, if n=1 and I choose a million as the node I visit. – Inquest Mar 4 '13 at 15:07
Indeed, all the possibilities for $s_n$ (i.e. its distribution) are in the set $\{-n,-n+2,-n+4,\ldots n-2,n\}$: in fact these are the only possible values $x$ for which the system $$\begin{cases} u+d = n \\ u-d=x \end{cases}$$ has non-negative integer solutions $u,d\in\mathbb N$. – AndreasT Mar 4 '13 at 15:15
And since $2n$ is even in your question, $x=0$ is in the set $\{-n,n+2,\ldots n-2,n\}$ – AndreasT Mar 4 '13 at 15:18
If $n=1$ as in your comment, then $x$ (the final position) can only take values in $\{-2,0,2\}$ (since you consider $2n$ rather than $n$). – AndreasT Mar 4 '13 at 15:43

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.

-
How do you know that there are $\binom{2n}{n}$ steps? – Inquest Mar 4 '13 at 14:51
@Inquest: Think about it this way: you need $n$ steps in positive direction and another $n$ in negative direction. So you could fill the each of the $2n$ slots with a + or a -, but the number of + and - should be equal to $n$. – Bravo Mar 4 '13 at 14:54
By this logic, if $n=1$, what prevents me from choosing $0>10000000>0$ which is clearly not a valid path – Inquest Mar 4 '13 at 15:05
@Inquest: Because when $n=1$ you can only take 2 steps. There is no direct path between 0 and 100000 -you go from 0 to 1 and have to return back to 0. – Bravo Mar 4 '13 at 15:09