Chapter 3, Problem 3.21TE

The Ballot Problem. In an election, candidate A receives n votes and candidate B receives m votes, where $n>m$. Assuming that all of the $\frac{\left(n+m\right)!}{n!m!}$ orderings of the votes are equally likely, let $P_{n,m}$ denote the probability that A is always ahead in the counting of the votes.

a. Compute $P_{2,1},P_{3,1},P_{3,1},P_{3,2},P_{4,1},P_{4,2},P_{4,3}$.

b. Find $P_{n,1},P_{m,2}$.

c. On the basis of your results in parts (a) and (b), conjecture the value of $P_{n,m}$.

d. Derive a recursion for $P_{n,m}$ in terms of $P_{n-1,m}$ and $P_{n,m-1}$ by conditioning on who receives the last vote.

e. Use part (d) to verify your conjecture in part (c) by an induction proof on $n+m$.