Random walks and using the reflection principle

Question

Consider exercise 5.5 from Shreve volume 1:

For part (I), I understand how you can use reflection to show that $P(M_n^*\geq m, M_n=b)=P(M_n=2m-b)$. However, it seems to me that this latter probability is just a binomial, and hence:

$$P(M_n=2m-b)={n\choose 2m-b}(1/2)^n$$

This is not equal to the equation given; for example $n=6,m=2,b=0$ is a counterexample. What am I missing?

Answer 1

If you go up $u$ times and down $d$ times, your random walk ends up at $u-d$ at time $u+d$. Since there are ${u+d \choose u}$ ways to distribute the $u$ up moves among the $u+d$ moves $$ P(M_{u+d} = u-d) = {u+d \choose u} \frac{1}{2^{u+d}} $$ Setting $n = u+d$, $x = u-d = 2u-n$, so $u = n+x/2$, this is equivalent to $$ P(M_n = x) = {n \choose (n+x)/2} \frac{1}{2^n}. $$ So $$ P(M_n = 2m-b) = {n \choose (n-b)/2+m} \frac{1}{2^n} $$ as announced.