Q. 3.21 - A First Course in Probability

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$. 

Step-by-Step Solution

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

Step1: Find the values of P 2 , 1 , P 3 , 1 , P 4 , 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}$

Step2: Find the value of P 3 , 2 , P 4 , 2 , P 4 , 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}$

Step3: Find P n , 1 , P n , 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}$ 

Step4: Conjecture the value of P n , 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}$

Step5: Recursion for P n , m in terms of P n - 1 , m and P n , 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}$

Step6: 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.