# Tag Info

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