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