This week’s Fiddler is about selecting a speaker of the house at random. How long will it take?

There are three candidates who want the job of Speaker. All 221 members of the party vote by picking randomly from among the candidates. If one candidate earns the majority of the votes, they become the next Speaker. Otherwise, the candidate with the fewest votes is eliminated and the process is repeated with one less candidate. If two or more candidates receive the same smallest number of votes, then exactly one of them is eliminated at random. What is the average number of rounds needed to select a new Speaker?

*Extra Credit*

What if there were 10 candidates running for Speaker?

My solution:

[Show Solution]

We will consider a more general case; suppose there are $n$ candidates and $2m+1$ voting members in the party. We write $2m+1$ since there should be an odd number of party members to break ties. Define the following probability:

\[

p(n,m) = \left\{

\begin{array}{l}

\text{Probability that one of the $n$ candidates} \\

\text{wins a majority of the $2m+1$ votes.}

\end{array}

\right\}

\]Let’s find a formula for $p(n,m)$. For a particular candidate to win $k$ votes, $k$ members must vote for the candidate and the remaining members must vote for one of the other $n-1$ candidates. This occurs with probability $\binom{2m+1}{k}\left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{2m+1-k}$. The candidate wins a majority if they garner at least $m+1$ of the $2m+1$ votes. We multiply the final result by $n$ since we are counting the probability that *any* of the $n$ candidates wins a majority. Therefore,

\[

p(n,m) = n\sum_{k=m+1}^{2m+1} \binom{2m+1}{k}\left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{2m+1-k}

\]*Note:* We can add the probabilities of the different candidates winning as we did because the events are disjoint; it is impossible for two candidates to simultaneously win a majority of the votes. If the criteria allowed for overlap, e.g., one candidate winning at least 40% of the vote, then two candidates could win simultaneously, and we would have to account for this case to avoid double-counting.

Making the change of variables $k \mapsto 2m+1-k$, we obtain

$\displaystyle

p(n,m) = n \sum_{k=0}^m \binom{2m+1}{k} \left(1-\frac{1}{n}\right)^{k}\left(\frac{1}{n}\right)^{2m+1-k}

$

We recognize this as $n$ times the CDF of a binomial distribution with $2m+1$ trials and probability $1-\frac{1}{n}$.

What we’re really after is the expected number of rounds required for a candidate to secure a majority of the vote.

\[

f(n,m) = \left\{

\begin{array}{l}

\text{Expected number of rounds until one of the } \\

\text{that one of the $n$ candidates is elected.}

\end{array}

\right\}

\]This will happen in one round with probability $p(n,m)$. It will happen in $k$ rounds if it does not happen in the first $k-1$ rounds, and happens in the $k^\text{th}$ round. Putting this together, we get:

$\displaystyle

f(n,m) = \sum_{k=1}^{n-1} k\cdot p(n-k+1,m) \prod_{i=0}^{k-1} \bigl( 1-p(n-k+1+i,m) \bigr)

$

Unfortunately, these formulas do not simplify in any meaningful way, so we must evaluate them numerically. The first question asks us to compute $f(3,110)$ and the extra credit asks for $f(10,110)$. Calculating these, we obtain:

\begin{align}

f(3,110) &\approx 1.9999995110943353682 \\

f(10,110) &\approx 8.9999995110943296464

\end{align}These are rational numbers, of course, but $f(3,110)$ and $f(10,110)$ have 105-digit and 1357-digit denominators, respectively, when expressed as irreducible fractions, so I will not write them out here! One thing for sure is that it is *very unlikely* that the voting will end early. It is a virtual certainty that it will go the full $n-1$ rounds until there are only two candidates remaining.

### Bonus: Changing the number of voters

The reason it is so difficult to elect a Speaker early is that there are so many voting members, and therefore it is unlikely that one candidate will obtain a majority of the votes by random chance. We can see how this probability would scale if we changed the number of voting members. Here is a plot of $f(n,m)$ for different values of $n$ (number of candidates), as a function of $2m+1$ (number of voting members). In all cases, we see that the expected number of rounds rapidly approaches $n-1$.