Proof of the Ballot Theorem Random Walks

698 Views Asked by At

Ballot Theorem: For $b>0$ the number of paths (0,0) to (n,b) that do not revisit the x axis is $\frac{b}{n}\mathbb{P}_{0}(S_n=b)$.

MY ATTEMPT
Now the first step of this path is to the point (1,1) so we want to find $$\mathbb{P}_{1}(S_{n-1}=b)- \mathbb{P}^{0}_{1}(S_{n-1}=b)$$ DEFINE $\mathbb{P}^{0}_{1}$ AS PROBABILITY STARTING AT 1 TO HIT b IN N-1 MOVES AND HITTING ZERO ON THE WAY

This by the reflective property is equivalent to $$\mathbb{P}_{1}(S_{n-1}=b)- \mathbb{P}_{-1}(S_{n-1}=b)$$ Now by using the formula $$\mathbb{P}_{a}(S_{n}=b)=\binom{n}{\frac{n+b-a}{2}}p^{\frac{n+b-a}{2}}q^{\frac{n-b+a}{2}}$$ But when I plug the numbers into the functions I am having a hard time rearragning it to give me the desired $\frac{b}{n}\mathbb{P}_{0}(S_n=b)$.
Is this proof reliant on all that algebra or is there a simply way of deriving the result?