#The Problem

The Fiddlerian government is in crisis. In particular, the Elephant Party, which possesses a majority of seats in the House (one of the two congressional chambers), can’t seem to select a new Speaker. At the moment, there are three candidates who want the job.

So here’s their new plan to select a Speaker. All 221 members of the Elephant Party will get in a room and vote for one of the three candidates. Now, the party is known for its chaotic behavior, and sure enough, each voter will pick randomly from among the candidates—even if they themselves are one of 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 they repeat the process 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.

They might be able to select their speaker in the first round of voting. After a second round, if it occurs, they would definitely have a Speaker. That means the average number of rounds needed is somewhere between one and two. What is this average?

#My Solution

I attempted to solve this with a Monte Carlo simulation. I quickly realized that a single-round incident was so unlikely that the experiment has to include a ridiculous number of trials.

~/dev/fiddler-231027$ python -m vote -t 100
Majority in 2 rounds on average
~/dev/fiddler-231027$ python -m vote -t 10000
Majority in 2 rounds on average
~/dev/fiddler-231027$ python -m vote -t 1000000
Majority in 2 rounds on average
~/dev/fiddler-231027$ python -m vote -t 100000000
Majority in 1.9999994 rounds on average

The true answer is approximately 1.99999951. So my simulated estimate was still about 0.000001 off and lacked a significant digit. Altogether, a great demonstration of when this approach isn't a good idea.

The advantage (I thought) to my approach is that I can easily adjust parameters for the 'extra credit'. Given 10 candidates instead of 3:

~/dev/fiddler-231027$ python -m vote -c 10 -t 100
Majority in 9 rounds on average
~/dev/fiddler-231027$ python -m vote -c 10 -t 10000
Majority in 9 rounds on average
~/dev/fiddler-231027$ python -m vote -c 10 -t 1000000
Majority in 9 rounds on average

So in actuality I am running into the same problem. The true answer is approximately 8.99999951. Of course, after 7 elimination rounds, this situation is the exact same problem as the original 3 candidate situation. So it's only necessary to determine the probability of the game terminating earlier than that, and incorporate that into the original solution. And given how small the likelihood is for forming a majority given 3 candidates, the likelihood for forming a majority given 4+ candidates is infinitesimal. In the end, it's the exact same solution plus 7 more elimination rounds.

Again, a great demonstration of when I should just use textbook statistics.