How Big Should an Election Audit Be?

How Big Should an Election Audit Be?

Fixed Rate Audits Do Not Work For Elections
http://electionarchive.org/ucvAnalysis/US/paper-audits/ElectinonAuditEstimator.doc
Kathy Dopp
[email protected]

January 17, 2007

This paper presents a simple formula for estimating vote count audit sample sizes to achieve any desired
certainty for ensuring the integrity of election outcomes. The formula described in this paper for
estimating election audit sample sizes, was derived first by Ronald Rivest.1
In particular, this paper briefly shows how to derive an estimate for vote count audit sample sizes:

1. to achieve any desired probability of detecting vote miscount that could alter an election outcome, and

2. to incorporate the principle of maximum vote shift per machine vote count2 that is required for logical consistency when auditing elections

Vote count audit sample sizes must be based on margins between the leading two candidates because the
smaller the margin, the smaller the amount of miscount that could wrongly alter the election outcome,
and the larger the audit sample must be to detect the smaller number of corrupt counts.

In conjunction with this paper, a spreadsheet is available to calculate exact minimum election audit
sample sizes necessary to ensure the integrity of election outcomes. Marian Beddill helped to craft this
new version of an earlier audit calculator spreadsheet created by Dopp.3 This new spreadsheet allows
any person, without a lot of experience, to enter the important factors and obtain a result and see the
efficacy of doing smaller or larger audits. It is available here:
http://ElectionArchive.org/ucvAnalysis/US/paper-audits/HowManyToAudit.xls

Why Assume a Maximum Vote Shift Per Machine Vote Count?
A maximum rate of miscount within any one vote count must be assumed to derive an estimate because
100% of votes cannot be wrongly shifted within each vote count. It would not only be unlikely that
100% of votes are available to target, but it is also unlikely that anyone trying to rig an election would
try to steal 100% of the target votes because it would be immediately noticed.4 However, to avoid
detection, a fraudster would corrupt as few counts as possible. So a maximum rate of vote shift per vote
count is assumed to calculate the amount of corrupt counts that could wrongly alter an election outcome.
The larger the assumed maximum wrongful vote shift rate per machine vote count, the fewer number of
corrupt vote counts could wrongly alter an election outcome; and the larger the audit sample size must
be to detect the corrupt counts.

1 Ron Rivest “How Big should a Statistical Audit Be?”, November, 2006
http://theory.csail.mit.edu/%7Erivest/Rivest-OnEstimatingTheSizeOfAStatisticalAudit.pdf

2 The Brennan Center “The Machinery of Democracy: Protecting Elections in an Electronic World”, June, 2006

3 July 2006 http://electionarchive.org/ucvAnalysis/US/paper-audits/AuditCalculator.xls

4 If vote miscount were made by innocent error, miscount would be more likely to appear in all vote counts and so be
detected with any audit amount. Independent audits should be designed to detect deliberate fraud.

We divide the margin between leading candidates by 2 to obtain the overall rate of votes which could be
shifted to alter an outcome, and then divide by the assumed maximum wrongful vote shift per vote count
to find the minimum percentage of vote counts that must be corrupt to wrongly alter an election
outcome.⁵

Historical Background

In 1975 Roy Saltman first introduced the concept of the necessity to base election audit sample sizes on
the margins between candidates because the closer the margin between candidates, the smaller the
amount of vote fraud or miscount and the fewer the number of corrupt counts which could wrongly alter
the outcome.

To detect small numbers of corrupt vote counts, larger audit samples are necessary. For example, if the
margin between the two leading candidates is 1%, then only approximately 3 corrupt vote counts out of
100 might put the wrong candidate into office. If the margin is 5%, it might take 15 or more corrupt
vote counts out of 100 to wrongly alter the outcome. A larger manual audit sample size is needed to
uncover one of 3 corrupt counts than to uncover one of 15 corrupt counts.

Unfortunately Saltman’s work in 1975 was substantially ignored at the time until the concepts were
rediscovered by Kathy Dopp in July 2006. Dopp furthered Saltman’s work by applying maximum vote
shift per vote count assumptions and using an estimate based on sampling with replacement6 to create a
trial-and-test spreadsheet method to obtain the exact audit sample size.7

Beginning in July 2006, Dopp and Frank Stenger developed a numerical method to exactly calculate
election audit sample sizes, which they released in September 2006, “The Election Integrity Audit”8.

The Dopp/Stenger method included an optional method for adjusting audit sample sizes for precinct size
variation in case miscounts are targeted to the largest precincts. However, the Dopp/Stenger numerical
method has not caught on yet, perhaps due to the complexity of using a computer program at a time
when the public is demanding transparent, easily-understand verification of election results.

Ronald Rivest of MIT derived a formula that more accurately estimates vote count audit sample sizes9
than the one based on sampling with replacement suggested in the Brennan Center report because it
gives a smaller over-estimate of the exact minimum audit required to ensure the integrity of election
outcomes. For more detailed history and derivation of the formula, see Rivest’s paper.

This paper more simply describes the derivation of the Rivest estimate and shows more explicitly how to
use Rivest’s formula to estimate audit sample sizes for specific margins and assumed maximum vote
shift per vote count.

The minimum audit sample size necessary to ensure the integrity of election outcomes to any desired
level of certainty can be determined by using this small easy-to-use spreadsheet:
http://electionarchive.org/ucvAnalysis/US/paper-audits/HowManyToAudit.xl...

5 Vote counts with more than the assumed maximum vote shift relative to prior elections or partisan active voter registration
records in voter history files, must also be included in manual audits as well as randomly selected counts.

6 A sampling with replacement estimate was suggested in the appendices on parallel election day machine testing in the Brennan Center’s June 2006 report “The Machinery of Democracy…”

7 The Brennan Center introduced the idea of a maximum wrongful vote shift per machine in its appendix on sampling voting machines for Election Day random testing of paperless voting machines.
8 http://electionarchive.org/ucvAnalysis/US/paper-audits/ElectionIntegrity...
9 Ibid 1.