Question

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 $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,2},P_{4,1},P_{4,2},P_{4,3}$.

(b) Find $P_{n,1},P_{n,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$.

Short answer

(a) To compute $P_{2,1},P_{3,1},P_{3,2},P_{4,1},P_{4,2},P_{4,3}$use the method of counting

(b) The value of $P_{n,1}=\frac{n-1}{n+1},P_{n,2}=\frac{n-2}{n+2}$

(c) To conjecture the value of $P_{n,m}$is $P_{n,m}=\frac{n-m}{n+m},n>m$

(d) Derive recursion of $P_{n,m}$in terms of $P_{n-1,m}$and $P_{n,m-1}$is $P_{n,m}=\frac{n}{n+m}\times P_{n-1,m}+\frac{m}{n+m}\times P_{n,m-1}$

(e) by mathematical induction, for some$k\in N$and$m\in \left\{0,1,2,3...\right\},n>m$such that$n+m=k$, the formula is true

Step-by-step solution

Find the values of P2,1,P3,1,P4,1 (part a)

Problem with the ballot box

The votes are read in a random sequence once $n+m$persons have voted for $A$or $B$.

$A_{n,m}-$in the scenario that candidate $S$($n$votes) always wins over candidate $B$($m<n$votes).

$P_{n,m}=P\left(A_{n,m}\right)$

Candidate $A$receives the $L$-last vote read.

This is accomplished by counting events that are equally likely (ordering of reading the $n+m$votes).

Find $P_{2,1}$

These are the possible orders of reading the votes:

$$\begin{gathered} AAB \\ ABA \\ BAA \end{gathered}$$

Only in the first case, A is the lead in every moment of counting. Taking the ratio:

$P_{2,1}=\frac{1}{3}$

Find $P_{3,1}$

$$\begin{gathered} AAAB \\ AABA \\ ABAA \\ BAAA \end{gathered}$$

$P_{3,1}=\frac{1}{4}$

Find $P_{4,1}$

$$\begin{gathered} AAAAB \\ AAABA \\ AABAA \\ ABAAA \\ BAAAA \end{gathered}$$

$P_{2,1}=\frac{1}{3}$

Find the value of P3,2,P4,2,P4,3 (part a)

The order of reading the votes, defined by the placement of votes for one candidate $A/B$, has a total of $\left(\begin{array}{c}2+3\\ 2\end{array}\right)=\left(\begin{array}{c}2+3\\ 3\end{array}\right)=10$equally likely alternatives.

$$\begin{gathered} AAABB \\ AABAB \\ AABBA \\ ABAAB \\ ABABA \\ ... \end{gathered}$$

The events that lead to $P_{3,2}$are only mentioned here; a more systematic approach is required.

$\Rightarrow P_{3,2}=\frac{2}{10}=\frac{1}{5}$

$P_{4,2}$

There are a total of $\left(\begin{array}{c}2+4\\ 2\end{array}\right)=\left(\begin{array}{c}2+4\\ 3\end{array}\right)=15$events that are equally likely.

$$\begin{gathered} AABABA \\ AABAAB \\ AAABBA \\ AAABAB \\ AAAABB \\ AABBAA \\ ABABAA \\ ... \end{gathered}$$

$\Rightarrow P_{4,2}=\frac{5}{15}=\frac{1}{3}$

$P_{4,3}$

There are a total of$\left(\begin{array}{c}3+4\\ 2\end{array}\right)=\left(\begin{array}{c}3+4\\ 3\end{array}\right)=35$ events that are equally likely.

$$\begin{gathered} AABABAB \\ AABAABB \\ AAABABB \\ AAABBAB \\ AAAABBB \\ AABBAAA \\ ABABAAA \\ ... \end{gathered}$$

$\Rightarrow P_{4,3}=\frac{5}{35}=\frac{1}{7}$

Find Pn,1,Pn,2 (part b)

Generalized logic form

$P_{n,1}$

There are a total of $\left(\begin{array}{c}n+1\\ 1\end{array}\right)=\left(\begin{array}{c}n+1\\ n\end{array}\right)=n+1$equally likely outcomes (orders of counting votes),

When $B$'s vote is counted, it is defined.

Counting of the events in which $A$is in the lead after each vote is counted

Because $A$is in the lead after the first vote is counted, the first vote goes to $A$.

Because $A$is in the lead after the second count, the first two votes cannot be $AB$- a tie.

$A$is the second vote.

Regardless of how the remaining votes are distributed, $A$will be in the lead because $B$has only one vote.

As a result, which of the $n+1-2$votes following the first two are for $B=n-1$events distinguishes the events that contribute to $P_{n,1}$is not affected by any other occurrence.

$\Rightarrow P_{n,1}=\frac{n-1}{n+1}$

$P_{n,2}$

When $B$'s vote is counted, there are a total of$\left(\begin{array}{c}n-1\\ 2\end{array}\right)=\frac{(n-1)(n-2)}{2}$
equally likely potential outcomes.

Counting of the events in which $A$is in the lead after each vote is counted

Counting of the events in which $A$is in the lead after each vote is counted

Because $A$is in the lead after the first vote is counted, the first vote goes to $A$.

Because $A$is in the lead after the second count, the first two votes cannot be $AB$- a tie.

$A$is the second vote.

If the third vote is a $B$, the fourth cannot be a $B$because it will result in an $AABB$tie.

Then the order would be $AABA$, and whenever $B$is $=n-2$potential orders, $A$will take the lead because $B$can only have two possible orders.

$\Rightarrow P_{n,2}=\frac{\frac{(n-1)(n-2)}{2}+(n-2)}{\frac{(n+2)(n+1)}{2}}=\frac{n-2}{n+2}$

Conjecture the value of Pn,m (part c)

Using the formulae,

$P_{n,m}=\frac{n-m}{n+m}$

Stating independence with:

$P_{n,m}=P\left(A_{n,m}\cap L\right)+P\left(A_{n,m}\cap L^c\right)$

and therefore,

$P\left(A_{n,m}\cap L\right)=\frac{n\times P_{n-1,m}\times (n-1+m)!}{(n+m)!}=\frac{n}{n+m}\times P_{n-1,m}$

Same things leads to,

$P\left(A_{n,m}\cap L^c\right)=\frac{m\times P_{n,m-1}\times (n-1+m)!}{(n+m)!}=\frac{m}{n+m}\times P_{n,m-1}$

This gives,

$P_{n,m}=\frac{n}{n+m}\times P_{n-1,m}+\frac{m}{n+m}\times P_{n,m-1}$

Recursion for Pn,m in terms of Pn-1,m and Pn,m-1 (part d)

By recursive formula,

$P_{n,m}=\frac{n}{n+m}\times P_{n-1,m}+\frac{m}{n+m}\times P_{n,m-1}$

The formula$P_{n,m}=\frac{n-m}{n+m}$will be proved.

If $n+m=1$, This gives:

$P_{1,0}=\frac{1-0}{1+0}=1$

Because $n+m\in \{0,1,2,3....\}$,the real case would be $n+m=0$, but since it is undefined, that is right for all $n+M\in N$.

Assume that the formula holds for every $n,m$with$n+m=k$for $k\in N$.

If $n,m$are such that $n+m=k+1$, then the following is true:

$P_{n,m}=\frac{n}{n+m}\times P_{n-1,m}+\frac{m}{n+m}\times P_{n,m-1}$

Verify the conjecture by an induction proof n+m (part e)

By $(n-1)+m=(n+m)-1=k+1-1=k$and $n+(m-1)=1$, apply the mathematical induction. Then,

$P_{n,m}=\frac{n}{n+m}\times \frac{n-1-m}{n-1+m}+\frac{m}{n+m}\times \frac{n-(m-1)}{n+m-1}$

$=\frac{n(n-m-1)+m(n-m+1)}{(n+m)(n+m-1)}$

$=\frac{(n-m)(n+m-1)}{(n+m)(n+m-1)}$$=\frac{(n-m)}{(n+m)}$

This establishes that for all $n,m$ that $n+m=k+1$, and this is based on the mathematical induction principle.