---
abstract: |
    We propose a simple risk-limiting audit for elections, [<span style="font-variant:small-caps;">ClipAudit</span>]{}. To determine whether candidate A (the reported winner) actually beat candidate B in a plurality election, [<span style="font-variant:small-caps;">ClipAudit</span>]{} draws ballots at random, without replacement, until either all cast ballots have been drawn, or until $$a - b \ge \beta \sqrt{a+b}$$ where $a$ is the number of ballots in the sample for the reported winner A, and $b$ is the number of ballots in the sample for opponent B, and where $\beta$ is a constant determined a priori as a function of the number $n$ of ballots cast and the risk-limit $\alpha$.

    [<span style="font-variant:small-caps;">ClipAudit</span>]{} doesn’t depend on the unofficial margin (as does Bravo).

    We show how to extend [<span style="font-variant:small-caps;">ClipAudit</span>]{} to contests with multiple winners or losers, or to multiple contests.
author:
- |
    Ronald L. Rivest\
    MIT CSAIL\
    [[rivest@mit.edu](rivest@mit.edu)]{}
bibliography:
- 'clip.bib'
title: '[<span style="font-variant:small-caps;">ClipAudit</span>]{}: A Simple Risk-Limiting Post-Election Audit'
---

[**Keywords:**]{} elections, auditing, post-election audits, risk-limiting audit.

Introduction and Motivation {#sec:introduction}
===========================

The paper is organized as follows: Section \[sec:preliminaries\] provides some terminology, notation, and orientation. Then Section \[sec:clipaudit\] provides an overview of the [<span style="font-variant:small-caps;">ClipAudit</span>]{} audit method. Section \[sec:computing-betas\] discusses the computation of the key constant $\beta$. Section \[sec:expected-final-sample-size\] analyzes the final expected audit sample size. Some [<span style="font-variant:small-caps;">ClipAudit</span>]{} variants are presented in Section \[sec:variants\]. Section \[sec:discussion\] provides more discussion of [<span style="font-variant:small-caps;">ClipAudit</span>]{}. Finally, related work is described in Section \[sec:related-work\].

Preliminaries {#sec:preliminaries}
=============

#### Outcomes, Ballots, Profiles.

We assume an election designed to produce an **outcome** from a set $\mathcal{C}$ of $C$ alternatives (or candidates).

Each of $n$ voters casts a single ballot. A ballot specifies a single candidate, chosen by the voter.

We denote the **profile** of cast ballots as $$P = \{v_1, v_2, \ldots, v_n\}\ ,$$ where each $v_i \in \mathcal{C}$. (One may wish to allow a cast vote $v_i$ to represent an “overvote” or an “undervote” as well, although the election outcome will never be “overvote” or “undervote.”) The profile may be viewed as a sequence or as a multiset, since profiles may contain repeated items (identical ballots).

#### Plurality Election.

We assume a *plurality election*: the candidate with the most votes is the winner. (There may be ties, which can be resolved according to relevant election law.)

#### Post-election audits.

We assume here that voters have cast votes on **paper ballots** on which their choices were recorded and verified by the voter. These paper ballots were scanned, and the electronic versions of the ballots aggregated to provide the initial or **reported outcome** for the election.

Confidence in the reported election outcome can be derived from a **post-election audit**.

The paper ballots are the “ground truth” for the election; a full and correct count of the paper ballots should give (essentially by definition) the **actual (or true) outcome** for the election.

A “compliance audit” can provide assurance that the paper trail has the necessary integrity. For details, see Benaloh et al. [@Benaloh-2011-SOBA], Lindeman and Stark [@Lindeman-2012-gentle], and Stark and Wagner [@Stark-2012-evidence-based].

#### Statistical post-election audits

Instead of using a recount, it is usually more efficient to audit using a statistical method based on hand examination of a **sample** of the paper ballots, a method first proposed by Johnson [@Johnson-2004-election-certification]. Such a **statistical (post-election) audit** typically provides statistical assurance that the reported outcome is indeed equal to the actual outcome, while examining only a relatively small sample of the paper ballots. In the presence of errors or fraud sufficient to make the reported outcome incorrect, the audit may need to examine many ballots, or even all ballots, before concluding that the reported outcome was incorrect.

#### Risk-limiting audits.

Stark [@Stark-2008-conservative] has provided a refined notion of a statistical audit—that of a **risk-limiting (post-election) audit** (or **RLA**). If the reported outcome is incorrect, the RLA is guaranteed to have a large, pre-specified chance $(1-\alpha)$ of examining all cast ballots and thereby correcting the reported outcome. In other words, if the reported outcome is incorrect, the audit will accept the reported outcome as correct with probability at most $\alpha$.

Here $\alpha$ is an audit parameter (for example, $\alpha=0.05$).

Lindeman and Stark have provided a “gentle introduction” to RLAs [@Lindeman-2012-gentle]. General overviews of post-election audits are available from Lindeman et al. [@Lindeman-2008-principles], Norden et al. [@Norden-2007-post-election-audits], and the Risk-Limiting Audit Working Group [@Bretschneider-2012-risk]. Stark and Wagner [@Stark-2012-evidence-based] promulgate the notion of an “evidence-based election,” which includes not only a risk-limiting audit but also the larger goals of ensuring that the evidence trail has integrity.

A variety of statistical methods for providing RLAs have been developed [@Stark-2008-sharper; @Hall-09-implementing-rlas; @Stark-2009-cast; @Stark-2009-efficient; @Stark-2009-risk-limiting; @Stark-2010-rla-cluster-size; @Stark-2010-super-simple; @Checkoway-2010-single-ballot; @CaliforniaSOS-2011-post-election-rla; @Lindeman-2012-bravo; @Sarwate-2013-risk-limiting; @Stark-2014-verifiable-elections]. We also note the availability of online tools for risk-limiting audits [@Stark-2015-tools]. We compare our [<span style="font-variant:small-caps;">ClipAudit</span>]{} proposal with Bravo [@Lindeman-2012-bravo], one of the best and best-known RLA methods.

[<span style="font-variant:small-caps;">ClipAudit</span>]{} overview {#sec:clipaudit}
====================================================================

[<span style="font-variant:small-caps;">ClipAudit</span>]{} is, like most statistical post-election audits, structured as a sequential decision-making procedure.

Randomly chosen ballots are examined one at a time, until a *stopping rule* says that the audit should stop (accepting the reported outcome as correct), or until all $n$ ballots in the profile have been examined (thereby revealing the true outcome, which may or may not be equal to the reported outcome).

[<span style="font-variant:small-caps;">ClipAudit</span>]{} is a *ballot-polling audit*: it looks only at the paper ballots, and does not consider the electronic version of the ballot data (cast vote record, or CVR) produced by the initial machine-scan of the paper ballots. (A *comparison audit* would do that, but [<span style="font-variant:small-caps;">ClipAudit</span>]{} is not a comparison audit. Comparison audits are generally more efficient than ballot-polling audits, and are thus to be preferred to ballot-polling audits when CVRs are available.)

With [<span style="font-variant:small-caps;">ClipAudit</span>]{}, ballots are sampled **without replacement**. (A variant of [<span style="font-variant:small-caps;">ClipAudit</span>]{} can easily be defined that use sampling with replacement, but such an approach is somewhat less efficient.)

Let $\alpha$ be the desired risk-limit.

[<span style="font-variant:small-caps;">ClipAudit</span>]{} should accept an incorrect reported outcome as correct with probability at most $\alpha$.

If the reported outcome is incorrect, [<span style="font-variant:small-caps;">ClipAudit</span>]{} will, with probability at least $1-\alpha$, proceed to determine the correct outcome by examining *all* of the paper ballots, in accordance with the definition of a risk-limiting audit.

We first describe [<span style="font-variant:small-caps;">ClipAudit</span>]{} for the simple case that there are only two candidates. Its extension to handle multiple candidates is described in Section \[sec:multiple-candidates\].

Let the two candidates be $A$ and $B$. In the ballots sampled by the audit so far, let $a$ denote the number of votes seen for $A$ and let $b$ denote the number of votes seen for $B$.

Let $\beta = \beta(n, \alpha)$ be a constant depending on the number $n$ of cast ballots and the desired risk limit $\alpha$. To get started, the reader may imagine that $\beta=3$ (which is about right for many typical values of $n$ and $\alpha=0.05$); more accurate values can be obtained from Figure \[fig:beta-chart\].

[<span style="font-variant:small-caps;">ClipAudit</span>]{} has a very simple structure:

Computing $\beta$ {#sec:computing-betas}
=================

   $n\backslash \alpha$   0.010   0.020   0.050   0.100   0.200   0.500
  ---------------------- ------- ------- ------- ------- ------- -------
           100            2.683   2.500   2.236   2.000   1.732   1.155
           300            2.887   2.694   2.425   2.145   1.877   1.343
           1000           3.054   2.864   2.546   2.294   2.000   1.414
           3000           3.184   3.000   2.670   2.401   2.095   1.511
          10000           3.290   3.077   2.770   2.496   2.183   1.633
          30000           3.357   3.144   2.828   2.556   2.240   1.715
          100000          3.411   3.206   2.889   2.638   2.324   1.747
          300000          3.487   3.273   2.958   2.684   2.375   1.817
         1000000          3.530   3.309   3.000   2.734   2.438   1.890
         3000000          3.560   3.352   3.040   2.782   2.474   1.937

The [<span style="font-variant:small-caps;">ClipAudit</span>]{} procedure depends on a well-defined value $\beta=\beta(n,\alpha)$, which depends upon the number $n$ of cast votes and upon the risk limit $\alpha$.

When using [<span style="font-variant:small-caps;">ClipAudit</span>]{} to audit a particular election, one can determine an appropriate value of $\beta$ use by consulting Figure \[fig:beta-chart\]. If the exact values of $n$ and $\alpha$ for the election audit are not available in the table, one can round $n$ up and round $\alpha$ down as needed.

In this section we describe how to compute $\beta(n,\alpha)$.

Computation of $\beta$ using simulation
---------------------------------------

Let $n$ be an even integer.

Let $$X \in \{-1, 1\}^n$$ be a randomly chosen vector **with zero sum**, and let $$S_t = X_1 + X_2 + \cdots + X_t
\label{eqn:random-walk}$$ for $1\le t \le n$ be the associated random walk. $S_t$ corresponds to the margin of candidate A over B within a sample of size $t$, as the sample size $t$ increases, when A and B are in fact *tied* in the overall profile of size $n$.

Note that sampling is done from the profile “without replacement,” so that at most $n$ ballots can be drawn for the sample, and when all $n$ are drawn, the two candidates are tied (since $S_n=0$).

Let $S'_t$ be the observed margin in the actual audit for the sample of size $t$. Assume that A is the announced winner, and that $S'_t$ is the margin of A over B in the sample.

The stopping condition for [<span style="font-variant:small-caps;">ClipAudit</span>]{} is $$S'_t > \beta \sqrt{t}
\label{eqn:stopping}$$ where $\beta$ is chosen so that a random walk $$S = (S_1, S_2, ..., S_n)$$ for a tied race has chance exactly $\alpha$ of stopping (i.e. satisfying (\[eqn:stopping\]) for some $t$, $1\le t \le n$).

[<span style="font-variant:small-caps;">ClipAudit</span>]{} is thus a risk-limiting audit (RLA) since if Bob really won, the chance that the audit stops and accepts Alice is not greater than the chance that the audit stops and accepts Alice if there is actually a tie.

Computing $\beta$ can be done in a couple of ways: simulations or approximate computations via dynamic programming. (“Approximate” because this method assume that the sampling is with replacement, rather than without replacement.) An analytic approach might also work, but I haven’t seen how to do that yet.

In any case, the simulation method is the fastest.

Computations yield, e.g. $$\beta(n=10000, \alpha=0.05) \approx 2.77\ .$$ Thus, for a 10000-vote election with announced winner Alice with $\alpha=0.05$ the audit would stop when the margin $a-b$ for Alice over Bob exceeds $$2.77 \sqrt{a+b}$$ when the sample shows $a$ votes for Alice and $b$ votes for Bob.

#### Simulation method

We now describe the computation of $\beta(n,\alpha)$ by the simulation method in more detail. Let $T$ denote the desired number of trials (simulation runs). We use $T=10^6$ in our computations.

For each trial $i$, $1\le i\le T$:

1.  Generate a random vector $X$ of length $n$ having zero sum. Each entry in $X$ is $+1$ or $-1$. (If $n$ is odd, then let $X$ have sum $+1$.)

2.  Compute the associated random walk via equation (\[eqn:random-walk\]).

3.  Compute $$\beta_i = \max_{1\le t\le n} \frac{S_t}{\sqrt{t}}\ .$$

4.  Return $\beta(n, \alpha)$ as that $k$th smallest value $\beta_i$, where $k={\lfloor (1-\alpha)T \rfloor}$. Here “$k$th smallest” means the value that is larger than or equal to $k$ values in the set—that is, the $k$th element if the values in the set are sorted into increasing order.

#### Formula for estimating $\beta(n,\alpha)$

We worked to fit a formula to the entries in Figure \[fig:beta-chart\]. Our best fit was to the formula: $$\beta(n,\alpha) \approx 0.075 \ln(n) + 0.700\, \textrm{isf}(\alpha) + 0.860\ ;
\label{eqn:best-fit-for-beta}$$ where $\textrm{isf}(\alpha)$ is the inverse survival function for the standard normal distribution—the value $x$ such that $\Phi(x) = 1 - \alpha$, and $\Phi$ is the cdf for the standard normal distribution. Over the values shown in the table the approximation was always within 0.16, and typically less than 0.05.

To get a formula that is a good fit but always an upper bound on the desired $\beta$ value, it suffices to raise the constant in the formula to 1.00: $$\beta(n,\alpha) \le 0.075 \ln(n) + 0.700\, \textrm{isf}(\alpha) + 1.000\ ;
\label{eqn:best-fit-for-beta-upper-bound}$$

The [<span style="font-variant:small-caps;">ClipAudit</span>]{} user may find it convenient to derive $\beta(n,\alpha)$ using formula (\[eqn:best-fit-for-beta\]) or formula (\[eqn:best-fit-for-beta-upper-bound\]) rather than using the table.

Expected Final Sample Size {#sec:expected-final-sample-size}
==========================

Let $m$ denote the actual fractional margin in favor of $A$—the fraction of votes for $A$ minus the fraction of votes for $B$. If the actual fractional margin in favor of $A$ is $m$, then the expected value of $S_t$ is $mt$.

Thus, $S_t\ge \beta \sqrt{t}$ is expected to occur when $$t \ge \frac{\beta^2}{m^2}\ .
\label{eqn:clipaudit-sample-size}$$

Compare with Bravo result: equation (7) in [@Lindeman-2012-bravo] says that Bravo should terminate once $$t \ge \frac{2 \ln(1/\alpha)}{m^2}\ .
\label{eqn:bravo-sample-size}$$

Comparing [<span style="font-variant:small-caps;">ClipAudit</span>]{}’s $\beta^2$ with Bravo’s $2\ln(1/\alpha)\approx 6$, (for $\alpha=0.05$), we see that Bravo has an advantange for $\beta > \sqrt{6} = 2.449$, *assuming that the reported margin is correct*.

#### Example

Consider auditing an election with $n=50000$ cast ballots, of which 60% are reported for candidate A and 40% are reported for candidate B, with a risk limit of $\alpha=0.10$.

For Bravo, formula (\[eqn:bravo-sample-size\]) gives an estimated sample size of 115; experimental results (shown in Table 1 of Lindeman et al. [@Lindeman-2012-bravo]) show an average sample size (ASN) of 119, assuming that the reported fraction of votes for each candidate is correct.

For [<span style="font-variant:small-caps;">ClipAudit</span>]{}, we use the value $\beta=2.568$ from formula (\[eqn:best-fit-for-beta\]); then formula (\[eqn:clipaudit-sample-size\]) gives an estimated sample size of 165; experimental results show an average sample size of 143.

We see that (at least for this example), using [<span style="font-variant:small-caps;">ClipAudit</span>]{} rather than Bravo incurs a performance penalty (in terms of number of ballots examined) on the order of 20%.

However, one advantage of [<span style="font-variant:small-caps;">ClipAudit</span>]{} is that its performance is *insensitive* to the reported vote fractions. If the reported vote fractions had been 70% for candidate A and 30% for candidate B (while the true fractions remained at 60% and 40%), Bravo would have performed a *full recount* with high probability, examining all 50000 ballots, whereas the expected workload by [<span style="font-variant:small-caps;">ClipAudit</span>]{} would be unchanged. Intuitively, Bravo is trying to see if the true vote fractions are “closer” to the reported vote fractions or to vote fractions representing a tied outcome; if the true vote fractions are “closer” to a tie (even if they support the reported outcome), then the Bravo audit will typically be forced into a doing a full recount.

Thus, one might adopt [<span style="font-variant:small-caps;">ClipAudit</span>]{} in situations where the reported vote fractions are a bit suspect, and/or where there is a desire to avoid the possibility of a full recount being caused by incorrect reported vote fractions.

Variants {#sec:variants}
========

\[sec:multiple-candidates\]

#### Multiple candidates.

The [<span style="font-variant:small-caps;">ClipAudit</span>]{} method can be easily extended to handle more than two candidates, possibly with multiple winners. Suppose the election has $C$ candidates, and that the top $W$ vote-getters will be declared the *winners*, and that the remaining $L=C-W$ will be declared *losers*. Here either $W$ or $L$ or both may be larger than $1$.

Let $A_1, \ldots, A_W$ denote the $W$ reported winners, and let $B_1, \ldots, B_L$ denote the $L$ reported losers.

We simply modify [<span style="font-variant:small-caps;">ClipAudit</span>]{} to concurrently audit that each $A_i$ defeats $B_j$, for $1\le i\le W$ and $1\le j\le L$. Each subaudit uses the same sequence of audited ballots, paying attention only to those ballots relevant to its task. Each audit uses the same overall risk limit $\alpha$. The overall audit stops and accepts the reported outcomes if and only if all of the subaudits have stopped and accepted that their $A_i$ defeats their $B_j$.

(The overall audit is an RLA with risk limit $\alpha$ because the chance that the overall audit accepts an incorrect outcome is at most the chance that a particular one of the subaudits with an incorrect hypothesis to check accepts it as correct.[^1])

#### Multiple contests

Multiple contests can be audited concurrently in a similar way. Each contest is audited using the overall risk limit $\alpha$ as its individual risk limit. Ballots are sampled uniformly from the set of all ballots having relevant (still-being-audited) contests on them. When a ballot is examined, choices for all relevant (still-being-audited) contests are determined by hand, and the audits for the relevant contests make progress (and possibly terminated). When all audits have terminated, or all ballots examined for all audits still being audit, the audit stops.

Each individual contest is audited in a risk-limiting manner. The fact that the different audits are using the same ballot samples doesn’t affect this argument (although it may mean that the different audit results are correlated, which shouldn’t be a problem).

Discussion {#sec:discussion}
==========

[<span style="font-variant:small-caps;">ClipAudit</span>]{} may be easier to explain or understand than Bravo, and doesn’t have any dependence on the unofficial margin.

It would be nice to prove a simple formula for $\beta(n,\alpha)$. Nonetheless, $\beta(n,\alpha)$ can be adequately estimated for practical use of [<span style="font-variant:small-caps;">ClipAudit</span>]{}.

Related Work {#sec:related-work}
============

DiffSum[@Rivest-2015-diffsum] has an identical structure, but the constant corresponding $\beta$ there has no formal definition, and the method is not provably risk-limiting.

We note for the record that there are statistical post-election audits that don’t seem to quite fit the “risk-limiting audit” definition, but which nonetheless have sound probabilistic foundations. In particular, the “Bayesian audit” of Rivest and Shen [@Rivest-2012-bayesian] is of this character. We refer the reader to that paper for details and discussion.

Acknowledgments {#sec:acknoledgments .unnumbered}
===============

Ronald L. Rivest gratefully acknowledges support for his work on this project received from the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-0939370, and from the Department of Statistics, University of California, Berkeley, which hosted his sabbatical visit when this work began. Thanks in particular to Philip Stark for helpful feedback and suggestions.

[^1]: Thanks for Philip B. Stark for providing this argument.
