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?

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