Find the number of paths in random walk Find the number of paths in random walk from $S_0$ to $S_{4n}$ satisfying all of the following terms:
a)$S_0 = S_{2n}=0$,
b)$S_k \ge 1 \; for \;1 \le k \le 2n-1$,
c)$S_{4n}=2$.
I need help with the above. I'm new to this subject so I'll be glad if anyone can help me with this exercise and explain this matter simply.
I know that $S_n=S_0 + \sum_{i=1}^{n} X_i$, where $P(X_i=1)=p$ is the probability of success, and $P(x_i=-1)=q=1-p$ is the probability of failure, and also $X_i$ are independent, but I think that I need other formulas to solve my problem.
Anyway, any help will be much appreciated.
 A: Something to note here is that you are counting paths so the probabilities are not actually important, especially since the $X_i$ are independent.
If we throw out condition (c) for a moment and just consider a random walk from $S_0$ to $S_{2n}$, we can actually break this problem into two halves. To satisfy condition (b) we must have $X_1 = 1$ and $X_{2n} = -1$. Between those moves we just need to make sure $S_k$ does not fall below $1$. To count this number of paths we can use the $n-2$nd Catalan number, denoted $C_{n-2}$. If you're interested in computing this thing, it has a closed form $C_n = \displaystyle\frac{1}{n+1}\binom{2n}{n}$ and some Googling or reading on Wikipedia can lead you to a proof of that.
So we have $\displaystyle\frac{1}{n-1}\binom{2(n-2)}{n-2}$ to make the first $2n$ moves of our random walk, and then we have to make $2n$ moves that give us a net $+2$ to our position. This means we have $2$ more successes than failures, but we know that successes and failures combined add to $2n$. So we have $n+1$ successes and $n-1$ failures. They can come in any order so the number of paths to do this is $\displaystyle\binom{2n}{n+1}$.
These 'halves' were independent of each other because the $X_i$ are independent, so our total number of paths is $\displaystyle\frac{1}{n-1}\binom{2n-4}{n-2}\binom{2n}{n+1}$ which maybe gets a little nicer if you expand out the binomial coefficients, though I haven't tried.
