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