How Long Would It Take to Pick a Speaker at Random?

The $221$ members of the majority party must choose a Speaker from three candidates. Each member votes for one of the candidates completely at random, even the candidates themselves. If someone wins a majority, they become Speaker. Otherwise the candidate with the fewest votes is eliminated (one of them at random if several tie for fewest) and the party votes again, at random, among the rest. A second round, if needed, is sure to produce a Speaker. What is the average number of rounds?

The Fiddler, Zach Wissner-Gross, October 27, 2023(original post)

The official solution appeared in the post of November 3, 2023 and gives about $1.99999951$ rounds for the main puzzle and about $8.99999951$ for the Extra Credit. Both agree with the answers below.

Solution

A second round has two candidates and an odd number of voters, $221$, so one of them must get at least $111$ votes. The only question is how often the first round already has a winner. Call that probability $p$. Then the number of rounds is $1$ with probability $p$ and $2$ otherwise, and the average is $$p \cdot 1 + (1 - p) \cdot 2 \;=\; 2 - p .$$

A majority means at least $111$ of the $221$ votes. Two candidates cannot both have that many, so the chance that somebody has a majority is just three times the chance that a particular candidate, A, does. Each voter picks A with probability $\tfrac13$, independently, so the number of votes for A follows the binomial distribution: $$p \;=\; 3 \sum_{k=111}^{221} \binom{221}{k} \left(\frac13\right)^{k} \left(\frac23\right)^{221-k} .$$

How big is this? A expects $221/3 \approx 73.7$ votes, with a standard deviation of $\sqrt{221 \cdot \tfrac13 \cdot \tfrac23} \approx 7.0$. A majority needs $111$, more than five standard deviations above the average, so $p$ is tiny. The sum is a finite one that can be evaluated exactly; its first term, $k = 111$, already supplies about half of it, and the total is $p \approx 4.889 \times 10^{-7}$. So $$\boxed{\ 2 - p \;\approx\; 1.99999951 \text{ rounds}. \ }$$ Almost always it takes both rounds.

The computation

The program counts ballots exactly. For $c$ candidates it builds, one voter at a time, the number of ways the voters can cast their ballots so that A gets each possible number of votes; the count of ballot lists in which A has a majority, times $c$, over all $c^{221}$ ballot lists, is the chance of a winner. It then runs the elimination process as a recursion: one round, and if nobody won, the same race with one fewer candidate.

from fractions import Fraction

VOTERS = 221

def majority_chance(c):
    """Exact chance that some candidate gets a majority when
    each of the 221 voters picks one of c candidates at
    random. ways[a] counts ballot lists giving candidate A
    exactly a votes, built up one voter at a time; at most
    one candidate can hold a majority, so multiply by c."""
    ways = [1]
    for _ in range(VOTERS):
        new = [0] * (len(ways) + 1)
        for a, w in enumerate(ways):
            new[a + 1] += w              # this voter picks A
            new[a] += w * (c - 1)        # picks someone else
        ways = new
    wins = sum(ways[VOTERS // 2 + 1:])
    return Fraction(c * wins, c ** VOTERS)

def expected_rounds(c):
    """Rounds needed starting from c candidates: one round,
    then (if nobody won) the race with one fewer."""
    if c == 1:
        return Fraction(0)
    p = majority_chance(c)
    return 1 + (1 - p) * expected_rounds(c - 1)

print(f"main: {float(expected_rounds(3)):.10f}")

It prints

main: 1.9999995111

Extra Credit

Now there are $10$ candidates. On average, how many rounds until someone wins a majority of the $221$ votes?

Solution

Each round either produces a Speaker or removes exactly one candidate, and the next round starts afresh with random votes among those left. Which candidate was eliminated does not matter, only how many remain. Write $E(c)$ for the average number of rounds starting with $c$ candidates and $p_c$ for the chance of a majority in a round with $c$ candidates. Then $E(2) = 1$, and $$E(c) \;=\; 1 + (1 - p_c)\,E(c - 1) .$$ As in the main puzzle, $p_c = c \sum_{k \ge 111} \binom{221}{k} \left(\frac1c\right)^k \left(1 - \frac1c\right)^{221-k}$, and with more candidates a majority is even more out of reach: $p_4$ is about $3 \times 10^{-15}$, and $p_{10}$ is about $2 \times 10^{-50}$. So the race almost surely runs all the way down to two candidates: seven rounds take it from $10$ candidates to $3$, and from there it behaves like the main puzzle, needing $2 - p_3$ more rounds on average. Unrolling the recursion, $$E(10) \;=\; 9 - p_3 - (\text{terms below } 10^{-14}),$$ since the main effect of each tiny $p_c$ is to save the rounds that would have followed, and only $p_3$ is large enough to show. So $$\boxed{\ E(10) \;\approx\; 8.99999951 \text{ rounds}. \ }$$

The computation

The same recursion from The computation above, started from $10$ candidates:

print(f"extra credit: {float(expected_rounds(10)):.10f}")

It prints

extra credit: 8.9999995111