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 (n+m)! /n! m! orderings of the votes are equally likely, let
pn, m
denote the probability that a is always ahead in the counting of the votes.(a) compute
p2,1,p3,1,p3,2,p4,1,p4,2,p4,3
. (b) find
pn,1,pn,2
. (b) find pn,1,pn,2.
(c) on the basis of your results in parts (a) and (b), conjecture the value of
pn, m
. (d) derive a recursion for
pn, m
in terms of
pn−1,m
and
pn, 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.