The probability of a drunk person/random walk A drunk person wonders aimlessly along a path by going forward 1 step and backward 1 step with equal probabilities of $\frac12$. 
a) After 10 steps, what is the probability that he has moved 2 steps forward?
b) What is the probability that he will make it to his front door within 20 steps before he collapses with the door being 6 steps in front of him.
My approach was to use Binomial in both cases:
a)${10\choose6} 0.5^{10}$. I can move 6 steps forward and 4 backwards and I will be in spot +2.
b)${20\choose6} 0.5^{20}$
I believe I have part a) correct but not b). I don't know how to handle the fact that in the spot 6+ is the house, a stop.
Can someone help me with part b)? I am seeing this wrong? I am thinking he is at zero but he can go -1 spot. Actually I am not sure if he can go from 0 to -1.
 A: Consider Pascal's triangle for a moment.
$$
\begin{matrix} & & & & & & 1 \\ & & & & & 1 & & 1\\ & & & & 1 & & 2 & & 1 \\ & & & 1 & & 3 & & 3 & & 1 \\ & & 1 & & 4 & & 6 & & 4 & & 1 \\ & 1 & & 5 & & 10 & & 10 & & 5 & & 1\\ 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1\end{matrix}
$$
Now, each number is the number of paths from the initial $1$ at the top to the respective point, such that each step is downwards.
What we seek is the number of paths that reach the sixth column to the right (or left) of centre. Let us look at the case of going two columns to the right in four steps. In this case, there are ${4\choose 3}=4$ paths that end in the second column. Then there's one path directly to the second column, from which two do not then finish in the second column, giving a total of $6$.
Now consider the case of two and six. In this case, we have 15 paths finishing in the second column, then there are 4 paths to the second column in four steps with two paths from there that do not then finish in the second column, and there is one path to the second column in two steps and then six paths from there that do not touch the second column again. This produces a total of $15\cdot1+4\cdot2+1\cdot6=29$. For confirmation, here are the 29 possible paths of length six reaching position 2:
$$\begin{matrix}++++++,& +++++-,& ++++-+,& \color{red}{++++--},& +++-++,\\ +++-+-,& \color{red}{+++--+}, &+++---,& ++-+++,& \color{red}{++-++-},\\ \color{red}{++-+-+},& ++-+--,& \color{red}{++--++},& ++--+-,& ++---+,\\ ++----,& +-++++,& \color{red}{+-+++-},& \color{red}{+-++-+},& +-++--,\\ \color{red}{+-+-++},& \color{red}{+--+++},& +--++-,& \color{red}{-++++-},& \color{red}{-+++-+},\\ -+++--,& \color{red}{-++-++},& \color{red}{-+-+++},& \color{red}{--++++}\end{matrix}$$
I have coloured the ones that end in position two in red. Now we can express the sum itself in the form
$$
{6\choose4}\cdot1+{4\choose3}\cdot2+{2\choose2}\cdot6
$$
We can generalise this without too much trouble (we'll restrict it to even position targets). We can express the summation in the form
$$
S_{M,N} = \sum_{k=N}^{M} {2k\choose k+N}{2(M-k)\choose M-k}
$$
where $N=n/2$ is half the distance to the door (as the distance is even) and $M=m/2$ is half the total number of steps. Why the second combinatorial? Because if you work it out, the number of paths of length $2n$ that don't return to the centre column happens to be $2n\choose n$.
Now, just to demonstrate it working, notice that
$$
S_{2,1} = 6\\
S_{3,1} = 29\\
S_{3,2} = 8
$$
Also note that, as expected, $S_{n,n}=1$.
Now, we're looking at $n=6$ and $m=20$, so $N=3$ and $M=10$, giving
$$
S_{10,3} = 198440
$$
And of course, the total number of paths over 20 steps is $2^{20}$, so the probability works out to be 
$$
P = \frac{198440}{2^{20}} = \frac{198440}{1048576} \approx 0.189
$$
So there's roughly a 19% chance of the drunk reaching the door.
