The counting problem of paths

Question

Consider a one-dimension $10$-step random walk with step size $1$, namely $S_n=\sum_{n=1}^{10} X_n$ and $X_i = 1$ or $-1$ for all $i\in\{1,2,...,10\}$. Further we require $S_i \geq 0$ for any $i$. And we have $S_{10} = 4$. How many paths satisfy this condition?

Actually it is a counting problem. It troubles me due to the requirement of $S_i \geq 0$. Could anyone give me some hint? Thank you!

Answer 1

Method I (brute force): Clearly we must have seven $+1's$ and three $-1's$. Also clearly, $X_1=1$. If the third $+1$ occurs after the third $-1$ then we violate positivity, so the third $+1$ can only occur at $X_3,X_4,X_5$. Easy to count each case.

If it occurs at $X_3$ all subsequent paths are good, so this case contributes $\binom 74=35$

if it occurs at $X_4$ then there are $2$ ways to place the first $-1$ and after that all subsequent paths are good, so $2\times \binom 64=30$.

if it occurs at $X_5$ then there are $2$ ways to place the second $+1$ and after that all subsequent paths are good, so $2\times \binom 54=10$.

Thus the final answer is $$35+30+10=\boxed {75}$$

Method II (reflection): if you ignore positivity there are $\binom {10}7=120$ paths. The bad ones touch the line $y=-1$. From the first point of contact with that line we could reflect our path to get a path that ends at $(10,-6)$. Thus there is a bijection between bad paths in our problem and paths that end at $(10,-6)$. There are $\binom {10}8=45$ paths that end at $(10,-6)$ so the answer is $$\binom {10}7-\binom {10}8=120-45=\boxed {75}$$

Answer 2

This is a pretty big spoiler but you could try to go check up the Catalan numbers

Answer 3

If there are $n$ step 1 and $m$ step $-1$ to be placed in a row such that number of 1s is always equal or more than the number of $-1$s, the number of ways is $\frac{n-m+1}{n+1}\binom{n+m}{m}$. In this case, $n=7, m= 3$ and hence equals $\frac{5}{8}\binom{10}{3} = 75$.