Question 3.27: In an election, candidate A receives n votes, and candidate ......
In an election, candidate A receives n votes, and candidate B receives m votes where n > m. Assuming that all orderings are equally likely, show that the probability that A is always ahead in the count of votes is (n − m)/(n + m).
Let P_{n,m} denote the desired probability. By conditioning on which candidate receives the last vote counted we have
P_{n,m}= P{A always ahead|A receives last vote} \frac{n}{n+m}
+ P{A always ahead|B receives last vote} \frac{m}{n+m}
Now, given that A receives the last vote, we can see that the probability that A is always ahead is the same as if A had received a total of n − 1 and B a total of m votes. Because a similar result is true when we are given that B receives the last vote, we see from the preceding that
P_{n,m}={\frac{n}{n+m}}P_{n-1,m}+{\frac{m}{m+n}}P_{n,m-1} (3.15)
We can now prove that P_{n,m}= (n − m)/(n + m) by induction on n + m. As it is true when n + m = 1, that is, P_{1,0}=1, assume it whenever n + m = k. Then when n + m = k + 1, we have by Equation (3.15) and the induction hypothesis that
P_{n,m}={\frac{n}{n+m}}\,{\frac{n-1-m}{n-1+m}}+{\frac{m}{m+n}}\,{\frac{n-m+1}{n+m-1}}={\frac{n-m}{n+m}}
and the result is proven.