Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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