Solution Found!
The Ballot Problem. In an election, candidate A receives n
Chapter 3, Problem 21TE(choose chapter or problem)
Problem 21TE
The Ballot Problem. In an election, candidate A receives n votes and candidate B receives mvotes, 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.
(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.
Questions & Answers
QUESTION:
Problem 21TE
The Ballot Problem. In an election, candidate A receives n votes and candidate B receives mvotes, 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.
(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.
ANSWER:
Step 1 of 10
Given that A receives n votes
and B receives m votes where n>m
is the probability that A is always a head in counting the votes
Assuming that
a) We have to compute
For calculating
The sequences where A leads B is {(AAB)}
Then from the equation (1)
=3
Then
=1/3
=0.333