Experience with recent contested close elections,
in particular the US Presidential Election of 2000 and the
Minnesota Senatorial Election of 2008, suggests that the
US system doesn't do that great a job of handling elections
where the margin of victory is very small. There are at
least two problems here:

- It's not clear that we really have efficient techniques
for counting millions of ballots to four nines of accuracy
(the difference between Coleman and Franken currently
stands at 312 votes out of 2.8 million).
[*]).
- Even if we assume we could count an agreed upon set of
ballots accurately, there's significant enough agreement about
which ballots should be counted that this can become the deciding
factor in close races.

The bottom line, then, is that it's very difficult to get a consensus
count in a close race, especially as the apparently losing side
has a real incentive to muddy the water as much as possible.
What we're left with, then, is a lot of fighting about individual
votes and no agreed upon count that reflects a specific winner,
allowing partisans of each side to insist that if only the votes
were counted correctly their candidate would have won.

*Coin-Flipping*

This isn't a new observation and I've more than once heard suggestions
that since there's no way to uncontroversially choose a winner in
close races based purely on the vote count, we should resolve such
races using an element of randomness, for instance by flipping a coin.
(Charles Seife's op-ed
in the NYT is one example, as is Michael Pitts's SSRN
paper). [Note that some states, and Minnesota in particular,
already have a provision in election law for coin flips to resolve
exact ties.] However, it should be immediately obvious that this just
moves the problem: whatever margin of error you choose to trigger the
election now becomes the litigation point. Pitt suggests a solution to
this (require any challenges to show there is a real chance of
prevailing in the entire election, not just pushing you over the
threshold), but as Nathan Cemenska observes,
you can just contest even earlier to prevent the preliminary count
from creating facts on the ground.
This seems like a problem with any scheme with a sharp threshold.

A second problem with proposals like Pitts's is the use of an unbiased
coin. Say we have an election where there were 10,000,000 votes and
Jefferson appears to have beaten Burr by 3,000 (.03%). Now, this may not
be enough to *convince* you that Jefferson won, but it's certainly
*evidence* that Jefferson is more likely to have won. To
give you a feel for the situation, if we treat this as a sampling problem
with a sample size of 10,000,000, the 90% confidence interval around
the estimate is +/- .025%--so we're outside the margin of error.
Any random selection procedure should somehow
reflect this information, not just act
like we don't know anything about the vote counts.

The bottom line, then, is that I don't think that the coin idea holds
up.

*A better procedure?*

Instead of flipping a coin, the natural thing to do is to treat
the nominal election results as an estimator of the true results
and then do a random sample that is appropriately biased in favor
of the nominal winner. This potentially solves both problems at once:

- It favors the nominal winner so that it takes
into account available information about the vote count.
- It doesn't have a sharp threshold effect so there is less
incentive to litigate at the margin.

However this depends on having an appropriate randomized algorithm.

One natural approach is to treat this is a statistical inference problem.
I.e., we treat the election as a very large poll with the
the nominal election results being a random
sample out of a universe of many more voters (or
many more elections). What we are interested in is the
probability *R* that the "true" number of voters who prefer
the nominal winner is really greater than those who prefer the nominal loser
(this will always be greater than .5, since otherwise the
nominal winner would be the nominal loser).
This is much the same as computing the margin of error
of a poll, for which we have good statistical techniques.
So, we just compute *R* and then flip a biased coin
(really you'd use some better technique) which has
chance *R* of coming up for the nominal winner and
chance *1-R* of coming up for the nominal loser.

Technical note: the way to think of this is that we're sampling out of
a binomial process with unknown probability *P*,
which corresponds to the fraction of voters who prefer
the nominal winner. We draw a sample of size *N*
(the number of voters) and get *pN* votes
for the nominal winner and *(1-p)N* for the nominal
loser. (The treatment can be readily extended to third party
candidates and voting errors). So, *p* is our estimate of
*P* and the distribution of results is just the binomial
distribution. With a large enough *N* (and a hundred
or so is plenty large), we can use the normal approximation
with the variance of *P* being the familiar *Np(1-p)*.
It's easy enough to determine what fraction of the distribution
of lies to the left of *.5*, and hence the probability
(speaking loosely here) that our election results are wrong.

This statistical inference treatment is fairly unsatisfactory
philosophically: we're not sampling out of some infinite universe of
elections and the number of voters isn't very large compared to our
sample size. On the contrary, we have a single election that captures
almost everyone in the relevant region but has some error around the
margin. We could try to salvage this by inverting the question and
asking "if we treat these results as the true proportions" but ran a
new election, what's the probability that the result would be
different? This is just more binomial distribution and gives us the
same formula, however, so we're just cleaning up the philosophical
groundwork a bit and it still isn't very satisfactory.
It doesn't get at the core problem which is
the underlying assumption that whatever process we see that causes
some votes to be included as part of our sample and others not to
be is random. It's easy to imagine this not being true: what if
the ballots in precincts that go Democratic are for some
reason harder to vote correctly than those that go Republican?
This sort of error is very hard to account for in some
clearly fair systematic way.

The figure below should give you a feel for the amount of
uncertainty introduced by this method.

It's important to note here that the larger the election the
lower the probability that an election with a given apparent
margin of victory (represented as a fraction of the number of
votes) will be reversed. This is a natural consequence of the
statistics of sampling, where the sample mean more tightly
approaches the true mean as sample size increases.

*How to generate the random numbers?*

One question you might want to ask is: if we're not going to
use a coin, how do we generate the random numbers in some verifiably
fair way. This is
actually fairly easy: we can use ping pong ball style lottery
machines where we label the appropriate fraction of ballots
for each candidate. This can be done arbitrarily or
(if the candidates don't trust the assignment), we can
alternate ball selection so that each candidate can choose
the balls he likes best.

*Is this good enough?*

As I said above, there are some philosophical problems here. The
statistical model we're using only imperfectly (at best)
reflects the situation. We know
our data wasn't derived from a random sampling process and worse
yet we're discarding all sorts of information (polling,
the disposition so far of challenged ballots, etc.) that could
tell us something if we knew how to incorporate it in a fair
way. However, what we're getting for that is a straightforward
method that is easy to apply in a systematic fashion.

We also need to ask whether this method reduces the threshold
effect I mentioned above.
As a concrete example, let's take the Minnesota 2008 Senate Race.
If we pretend that Coleman and Franken were the only candidates
in the Minnesota election, we would give Coleman about a 42% chance
of prevailing. If Coleman could remove 100 of Franken's votes,
this would up his chances to 44.6%. Is that enough to
make it worth litigating those 100 votes? I don't know.
Obviously, we could make the distribution wider by some
ad hoc factor (though I don't know of any principled way
to do so), but that seems unfair to the nominal winner, since
we're basically choosing to ignore evidence in his favor.

The bottom line, then, is that this really isn't that
great a method: I just don't have a better one.

**UPDATE:** Minor grammatical fixes due to Steve Checkoway.