k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots

k-Cut: A Simple Approximately-Uniform

Method for Sampling Ballots in Post-Election

Audits

Mayuri Sridhar and Ronald L. Rivest

Massachusetts Institute of Technology, Cambridge MA 02139, USA

[email protected]

Abstract. We present an approximate sampling framework and discuss

how risk-limiting audits can compensate for these approximations, while

maintaining their “risk-limiting” properties. Our framework is general

and can compensate for counting mistakes made during audits.

Moreover, we present and analyze a simple approximate sampling method,

“k-cut”, for picking a ballot randomly from a stack, without counting.

Our method involves doing k “cuts,” each involving moving a random

portion of ballots from the top to the bottom of the stack, and then pick-

ing the ballot on top. Unlike conventional methods of picking a ballot at

random, k-cut does not require identiﬁcation numbers on the ballots or

counting many ballots per draw. We analyze how close the distribution of

chosen ballots is to the uniform distribution, and design mitigation pro-

cedures. We show that k = 6 cuts is enough for a risk-limiting election

audit, based on empirical data, which provides a signiﬁcant increase in

sampling eﬃciency. This method has been used in pilot RLAs in Indiana

and is scheduled to be used in Michigan pilot audits in December 2018.

Keywords: sampling · elections · auditing · post-election audits · risk-

limiting audit · Bayesian audit.

1 Introduction

The goal of post-election tabulation audits is to provide assurance that the re-

ported results of the contest are correct; that is, they agree with the results that

a full hand-count would reveal. To do this, the auditor draws ballots uniformly

at random one at a time from the set of all cast paper ballots, until the sample

of ballots provides enough assurance that the reported outcomes are correct.

The most popular post-election audit method is known as a “risk-limiting

audit” (or RLA), invented by Stark (see his web page [13]). See also [3, 5–7, 11,

12] for explanations, details, and related papers. An RLA takes as input a “risk-

limit” α (like 0.05), and ensures that if a reported contest outcome is incorrect,

then this error will be detected and corrected with probability at least 1 − α.

Supported by Center for Science of Information (CSoI), an NSF Science and Tech-

nology Center, under grant agreement CCF-0939370.

2 M. Sridhar and R.Rivest

This paper provides a novel method for drawing a random sample of the

cast paper ballots. The new method may often be more eﬃcient than stan-

dard methods. However, it has a cost: ballots are drawn in a way that is only

“approximately uniform”. This paper provides ways of compensating for such

non-uniformity.

There are two standard approaches for drawing a random sample of cast

paper ballots:

1. [ID-based sampling] Print on each scanned cast paper ballot a unique

identifying number (ballot ID numbers). Draw a random sample of ballot ID

numbers, and retrieve the corresponding ballots.

2. [Position-based sampling] Give each ballot an implicit ballot ID equal to

its position, then proceed as with method (1).

These methods work well, and are guaranteed to produce random samples.

In practice, auditors use software, like [14], which takes in a ballot manifest as

input and produces the random sample of ballot ID numbers. In this software,

it is typically assumed that sampling is done without replacement.

However, ﬁnding even a single ballot using these sampling methods can be

tedious and awkward in practice. For example, given a random sample of ID

numbers, one may need to count or search through a stack of ballots to ﬁnd

the desired ballot with the right ID or at the right position. Moreover, typical

auditing procedures assume that there are no mistakes when ﬁnding the ballots

for the sample. Yet, this seems to be an unreasonable assumption - a study by

Goggin et al. shows that when counting 120 ballots, human teams miscount the

number of votes for a given candidate at an average rate of 1.4% [4]. In the

literature about RLAs, there is no way to correct for these mistakes.

Our goal is to simplify the sampling process.

In particular, we deﬁne a general framework for compensating for “approxi-

mate sampling” in RLAs. Our framework of approximate sampling can be used

to measure and compensate for human error rate while using the counting meth-

ods outlined above. Moreover, we also deﬁne a simpler approach for drawing a

random sample of ballots, which does not rely on counting at all. Our technique

is simple and easy to iterate on and may be of particular interest when the stack

of ballots to be drawn from is large. We deﬁne mitigation procedures to account

for the fact that the sampling technique is no longer uniformly random.

Overview of this paper. Section 2 introduces the relevant notation that we use

throughout the paper.

Section 3 presents our proposed sampling method, called “k-cut.”

Section 4 studies the distribution of single cut sizes, and provides experimen-

tal data. We then show how iterating a single cut provides improved uniformity

for ballot selection.

Section 5 discusses the major questions that are brought up when using

“approximate” sampling in a post-election audit.

k-Cut: Simple Approximate Sampling 3

Section 6 proves a very general result: that any general statistical auditing

procedure for an arbitrary election can be adapted to work with approximate

sampling, with simple mitigation procedures.

Section 7 discusses how to adapt the k-cut method for sampling when the

ballots are organized into multiple stacks or boxes.

Section 8 provides some guidance for using k-cut in practice.

Section 9 gives some further discussion, lists some open problems, and makes

some suggestions for further research.

Section 10 summarizes our contributions.

2 Notation and Election Terminology

Notation. We let [n] denote the set {0, 1, . . . , n − 1}, and we let [a, b] denote the

set {a, a + 1, . . . , b − 1}.

We let U[n] denote the uniform distribution over the set [n]. In U[n], the

“[n]” may be omitted when it is understood to be [n], where n is the number of

ballots in the stack. We let U[a, b] denote the uniform distribution over the set

[a, b].

We let V D(p, q) denote the variation distance between probability distribu-

tions p and q; this is the maximum, over all events E, of

P r

[E] − P r

[E].

Election Terminology. The term “ballot” here means to a single piece of paper

on which the voter has recorded a choice for each contest for which the voter is

eligible to vote. One may refer to a ballot as a “card.” Multi-card ballots are not

discussed in this paper.

Audit types. There are two kinds of post-election audits: ballot-polling audits,

and ballot-comparison audits, as described in [7]. For our purposes, these types

of audits are equivalent, since they both need to sample paper ballots at random,

and can make use of the k-cut method proposed here. However, if one wishes

to use k-cut sampling in a comparison audit, one would need to ensure that

each paper ballot contains a printed ID number that could be used to locate the

associated electronic CVR.

3 The k-Cut Method

The problem to be solved is:

How can one select a single ballot (approximately) at random from a

given stack of n ballots?

This section presents the “k-cut” sampling procedure for doing such sam-

pling. The k-cut procedure does not need to know the size n of the stack, nor

does it need any auxiliary random number generators or technology.

4 M. Sridhar and R.Rivest

We assume that the collection of ballots to be sampled from is in the form of a

stack. These may be ballots stored in a single box or envelope after scanning. One

may think of the stack of ballots as being similar to a deck of cards. When the

ballots are organized into multiple stacks, sampling is slightly more complex—see

Section 7.

The basic operation for drawing a single ballot is called “k-cut and pick,” or

just “k-cut.” This method does k cuts then draws the ballot at the top of the

stack.

To make a single cut of a given stack of n paper ballots:

– Cut the stack into two parts: a “top” part and a “bottom” part.

– Switch the order of the parts, so what was the bottom part now sits above

the top part. The relative order of the ballots within each part is preserved.

We let t denote the size of the top part. The size t of the top part should be

chosen “fairly randomly” from the set [n] = {0, 1, 2, . . . , n − 1}

. In practice, cut

sizes are probably not chosen so uniformly; so in this paper we study ways to

compensate for non-uniformity. We can also view the cut operation as one that

“rotates” the stack of ballots by t positions.

An example of a single cut. As a simple example, if the given stack has n = 5

ballots:

A B C D E ,

where ballot A is on top and ballot E is at the bottom, then a cut of size t = 2

separates the stack into a top part of size 2 and a bottom part of size 3:

A B C D E

whose order is then switched:

C D E A B .

Finally, the two parts are then placed together to form the ﬁnal stack:

C D E A B .

having ballot C on top.

Iteration for k cuts. The k-cut procedure makes k successive cuts then picks the

ballot at the top of the stack.

If we let t

denote the size of the i-th cut, then the net rotation amount after

k cuts is

= t

+ t

+ · · · + t

(mod n) . (1)

The ballot originally in position r

(where the top ballot position is position 0)

is now at the top of the stack. We show that even for small values of k (like

k = 6) the distribution of r

is close to U.

A cut of size n is excluded, as it is equivalent to a cut of size 0.

k-Cut: Simple Approximate Sampling 5

Drawing a sample of multiple ballots. To draw a sample of s ballots, our k-cut

procedure repeats s times the operation of drawing without replacement a single

ballot “at random.” The s ballots so drawn form the desired sample.

Eﬃciency. Suppose a person can make six (“fairly random”) cuts in approx-

imately 15 seconds, and can count 2.5 ballots per second

. Then k-cut (with

k = 6) is more eﬃcient when the number of ballots that needs to be counted is

37.5 or more. Since batch sizes in audits are often large, k-cut has the potential

to increase sampling speed.

For instance, assume that ballots are organized into boxes, each of which

contains at least 500 ballots. Then, when the counting method is used, 85% of

the time a ballot between ballot #38 and ballot #462 will be chosen. In such

cases, one must count at least 38 ballots from the bottom or from the top to

retrieve a single ballot. This implies that k-cut is more eﬃcient 85% of the time.

As the number of ballots per box increases, the expected time taken by

standard methods to retrieve a single ballot increases. With k-cut, the time it

takes to select a ballot is constant, independent of the number of ballots in the

box, assuming that each cut takes constant time.

Security We assume that the value of k is ﬁxed in advance; you can not allow

the cutter to stop cutting once a “ballot they like” is sitting on top.

4 (Non)-Uniformity of Single Ballot Selection

We begin by observing that if an auditor could perform “perfect” cuts, we would

be done. That is, if the auditor could pick the size t of a cut in a perfectly uni-

form manner from [n], then one cut would suﬃce to provide a perfectly uniform

distribution of the ballot selected from the stack of size n. However, there is no

a priori reason to believe that, even with sincere eﬀort, an auditor could pick t

in a perfectly uniform manner.

So, we start by studying the properties of the k-cut procedure for single-

ballot selection, beginning with a study of the non-uniformity of selection for

the case k = 1 and extending our analysis to multiple cuts.

4.1 Empirical Data for Single Cuts

This section presents our experimental data on single-cut sizes. We ﬁnd that in

practice, single cut sizes (that is, for k = 1) are “somewhat uniform.” We then

show that the approximation to uniformity improves dramatically as k increases.

We had two subjects, the authors. Each author had a stack of 150 sequentially

numbered ballots to cut, provided by Marion County, Indiana. The authors made

1680 cuts in total. Figure 1 shows the observed cut size frequency distribution.

The complete data tables are provided in the longer version of this paper

These assumptions are based on observations during the Indiana pilot audits.

The longer version is available at https://arxiv.org/abs/1811.08811

6 M. Sridhar and R.Rivest

Fig. 1. Probability Density of empirical distribution of sizes of single cuts, using com-

bined data from both authors, with 1680 cuts total. The model that best ﬁt the empir-

ical data was an exponential model, shown in blue. The extended paper provides more

details about this and other models for our data.

If the cuts were truly random, we would expect a uniform distribution of the

number of cuts observed as a function of cut size. In practice, the frequency of

cuts was not evenly distributed; there were few or no very large or very small

cuts, and smaller cuts were more common than larger cuts.

4.2 Making k successive cuts to select a single ballot

As noted, the distribution of cut sizes for a single cut is noticeably non-uniform.

Our proposed k-cut procedure addresses this by iterating the single-cut operation

k times, for some small ﬁxed integer k.

We assume for now that cut sizes are distributed as in our experiments, as

described in Figure 1, and that successive cuts are independent. Moreover, we

assume that sampling is done with replacement, for simplicity.

We give computational results showing that as the number of cuts increases,

the k-cut procedure selects ballots with a distribution that approaches the uni-

form distribution. We compare by computing the variation distance of the k-cut

distribution from U for various k. We also computed , the maximum ratio of

the probability of drawing any particular ballot under the empirical distribution,

to the probability of drawing that ballot under the uniform distribution, minus

one

. Our results are summarized in Table 1.

We can see that, after six cuts, we get a variation distance of about 7.19 ×

−4

, for the empirical distribution, which is often small enough to justify our

recommendation that six cuts being “close enough” in practice, for any RLA.

In Section 6.4, we discuss why this value of  is relevant

k-Cut: Simple Approximate Sampling 7

k Variation Distance Max Ratio minus one

1 0.247 1.5

2 0.0669 0.206

3 0.0215 0.0687

4 0.0069 0.0224

5 0.00223 0.00699

6 0.000719 0.00225

7 0.000232 0.000729

8 7.49e-05 0.000235

Table 1. Convergence of k-cut to uniform with increasing k. Variation distance from

uniform and -values for k cuts, as a function of k, for n = 150, where  is one less

than the maximum ratio of the probability of selecting a ballot under the assumed

distribution to the probability of selecting that ballot under the uniform distribution.

4.3 Asymptotic Convergence to Uniform with k

As k increases, the distribution of cut sizes provably approaches the uniform

distribution, under mild assumptions about the distribution of cut sizes for a

single cut and the assumption of independence of successive cuts.

This claim is plausible, given the analysis of similar situations for contin-

uous random variables. For example, Miller and Nigrini [9] have analyzed the

summation of independent random variables modulo 1, and given necessary and

suﬃcient conditions for this sum to converge to the uniform distribution.

For the discrete case, one can show that if once k is large enough that every

ballot is selected by k-cut with some positive probability, then as k increases

the distribution of cut sizes for k-cut approaches U. Furthermore, the rate of

convergence is exponential. The proof details are omitted here; however, the

second claim uses Markov-chain arguments, where each rotation amount is a

state, and the fact that the transition matrix is doubly stochastic.

5 Approximate Sampling

We have shown in the previous section that as we iterate our k-cut procedure,

our distribution becomes quite close to the uniform distribution. However, our

sampling still is not exactly uniform.

The literature on post-election audits generally assumes that sampling is

perfect. One exception is the paper by Banuelos and Stark [2], which suggests

dealing conservatively with the situation when one can not ﬁnd a ballot in an

audit, by treating the missing ballot as if it were a vote for the runner-up. Our

proposed mitigation procedures are similar in ﬂavor.

In practice, sampling for election audits is often done using software such

as that by Stark [14] or Rivest [10]. Given a random seed and a number n of

ballots to sample from, they can generate a pseudo-random sequence of integers

from [n], indexing into a list of ballot positions or ballot IDs. It is reasonable to

8 M. Sridhar and R.Rivest

treat such cryptographic sampling methods as “indistinguishable from sampling

uniformly,” given the strength of the underlying cryptographic primitives.

However, in this paper we deal with sampling that is not perfect; the k-cut

method with k = 1 is obviously non-uniform, and even with modest k values, as

one might use in practice, there will be some small deviations from uniformity.

Thus, we address the following question:

How can one eﬀectively use an approximate sampling procedure in a

post-election audit?

We let G denote the actual (“approximate”) probability distribution over [n]

from the sampling method chosen for the audit. Our analyses assume that we

have some bound on how close G is to U, like variation distance. Furthermore,

the quality of the approximation may be controllable, as it is with k-cut: one

can improve the closeness to uniform by increasing k. We let G

denote the

distribution on s-tuples of ballots from [n] chosen with replacement according

to the distribution G for each draw.

6 Auditing Arbitrary Contests

This section proves a general result: for auditing an arbitrary contest, we show

that any risk-limiting audit can be adapted to work with approximate sampling,

if the approximate sampling is close enough to uniform. In particular, any RLA

can work with the k-cut method, if k is large enough.

We show that if k is suﬃciently large, the resulting distribution of k-cut

sizes will be so close to uniform that any statistical procedure cannot eﬃciently

distinguish between the two. That is, we want to choose k to guarantee that U

and G are close enough, so that any statistical procedure behaves similarly on

samples from each.

Previous work done by Baign`eres in [1] shows that, there is an optimal dis-

tinguisher between two ﬁnite probability distributions, which depends on the

KL-Divergence between the two distributions.

We follow a similar model to this work, however, we develop a bound based

on the variation distance between U and G.

6.1 General Statistical Audit Model

We construct the following model, summarized in Figure 2.

We deﬁne δ to be the variation distance between G and U. We can ﬁnd an

upper bound for δ empirically, as seen in Table 1. If G is the distribution of

k-cut, then by increasing k we can make δ arbitrarily small.

The audit procedure requires a sample of some given size s, from U

or G

We assume that all audits behave deterministically. We do not assume that suc-

cessive draws are independent, although we assume that each cut is independent.

Given the size s sample, the audit procedure can make a decision on whether

to accept the reported contest result, escalate the audit, or declare an upset.

k-Cut: Simple Approximate Sampling 9

Fig. 2. Overview of uniform vs. approximate sampling eﬀects, for any statistical au-

diting procedure. The audit procedure can be viewed as a distinguisher between the

two underlying distributions. If it gives signiﬁcantly diﬀerent results for the two distri-

butions, it can thereby distinguish between them. However, if p and p

are extremely

close, then the audit cannot be used as a distinguisher.

6.2 Mitigation Strategy

When we use approximate sampling, instead of uniform, we need to ensure that

the “risk-limiting” properties of the RLAs are maintained. In particular, as de-

scribed in [7], an RLA with a risk limit of α guarantees that with probability at

least (1−α) the audit will ﬁnd and correct the reported outcome if it is incorrect.

We want to maintain this property, while introducing approximate sampling.

Without loss of generality, we focus on the probability that the audit accepts

the reported result, since it is the case where approximate sampling may aﬀect

the risk-limiting properties. We show that G and U are suﬃciently close when k

is large, that the diﬀerence between p and p

, as seen in Figure 2, is small.

We show a simple mitigation procedure, for RLA plurality elections, to com-

pensate for this non-uniformity, that we denote as risk-limit adjustment. For

RLAs, we can simply decrease the risk limit α by |p

− p| (or an upper bound on

this) to account for the diﬀerence. This decrease in the risk limit can accommo-

date the risk that the audit behaves incorrectly due to approximate sampling.

6.3 How much adjustment is required?

We assume we have an auditing procedure A, which accepts samples and outputs

“accept” or “reject”. We model approximate sampling with providing A samples

from a distribution G. For our analysis, we look at the empirical distribution of

cuts in Table 2. For uniform sampling, we provide A samples from U.

We would like to show that the probability that A accepts an outcome in-

correctly, given samples from G is not much higher than the probability that A

10 M. Sridhar and R.Rivest

accepts an incorrect outcome, given samples from U. We denote B as the set of

ballots that we are sampling from.

Theorem 1. Given a ﬁxed sample size s and the variation distance δ, the max-

imum change in probability that A returns “accept” due to approximate sampling

is at most



+ (1 + nδ)

− 1,

where s

is the maximum number of “successes” seen in s Bernoulli trials, where

each has a success probability of δ, with probability at least 1 − 

Proof. We deﬁne s as the number of ballots that we pull from the set of cast

ballots, before deciding whether or not to accept the outcome of the election.

Given a sample size s, based on our sampling technique, we draw s ballots, one

at a time, from G or from U.

We model drawing a ballot from G as ﬁrst drawing a ballot from U; however,

with probability δ, we replace the ballot we draw from U with a new ballot from

B following a distribution F. We make no further assumptions about the distri-

bution F, which aligns with our deﬁnition of variation distance. When drawing

from G, for any ballot b ∈ B, we have probability at most

+ δ of drawing b.

When we sample sequentially, we get a length-s sequence of ballot IDs, S,

for each of G and U. Throughout this model, we assume that we sample with

replacement, although similar bounds should hold for sampling without replace-

ment, as well. We deﬁne X as the list of indices in the sequence S where both G

and U draw the same ballot, in order. We deﬁne Z as the list of indices where G

has “switched” a ballot after the initial draw. That is, for a ﬁxed draw, U might

produce the sample sequence [1, 5, 29]. Meanwhile, G might produce the sample

sequence sequence [1, 5, 30]. For this example, X = [0, 1] and Z = [2].

We deﬁne the set of possible size-s samples as the set D. We choose s

such

that for any given value 

, the probability that |Z| is larger than s

is at most



. Using this set up, we can calculate an upper bound on the probability that A

returns “accept”. In particular, given the empirical distribution, the probability

that A returns “accept” for a deterministic auditing procedure becomes

Pr[A accepts | G] =

S∈D

Pr[A accepts | S] ∗ Pr[draw S | G] .

Now, we note that we can split up the probability that we can draw a speciﬁc

sample S from the distribution G. We know that with high probability, there are

at most s

ballots being “switched”. Thus,

Pr[A accepts | G]

S∈D

Pr[A accepts | S]∗Pr[draw S | G, S has ≤ s

“switched” ballots]∗Pr[S has ≤ s

“switched” ballots]

S∈D

Pr[A accepts | S]∗Pr[draw S | G, S has > s

“switched” ballots]∗Pr[S has > s

“switched” ballots] .

k-Cut: Simple Approximate Sampling 11

Now, we note that the second term is upper bounded by

Pr[any size-s sample has more than s

switched ballots] .

We deﬁne the probability that any size-s sample contains more than s

switched

ballots as 

We note that, although the draws aren’t independent, from the deﬁnition

of variation distance, this is upper bounded by the probability that a binomial

distribution, with s draws and δ probability of success.

Now, we can focus on bounding the ﬁrst term. We know that

Pr[A accepts | G, any sample has at most s

switched ballots]

S∈D

Pr[A accepts | S] ∗ Pr[draw S | G, S has ≤ s

“switched” ballots]

For the uniform distribution, we know that the probability of accepting becomes

Pr[A accepts | U] =

S∈D

Pr[A accepts | S] ∗ Pr[draw S | U] .

Thus, we know that the change in probability becomes

Pr[A accepts | G] − Pr[A accepts | U]

≤ 

S∈D

Pr[A accepts | S](Pr[draw S | G, S has ≤ s

“switched” ballots]−Pr[draw S | U]) .

However, for any ﬁxed sample S, we know that we can produce S from E in

many possible ways. That is, we know that we have to draw at least s−s

ballots

that are from U. Then, we have to draw the compatible s

ballots from G. In

general, we deﬁne the possible length s − s

compatible shared list of indices as

the set X. That is, by conditioning on X, we are now deﬁning the exact indices in

the sample tally where the uniform and empirical sampling can diﬀer. We note

that |X| =





and each possible set happens with equal probability. Then, for

any speciﬁc x ∈ X, we can deﬁne z as the remaining indices, which are allowed

to diﬀer from uniform and approximate sampling. That is, if there are 3 ballots

in the sample, and x = [0, 1], then z = [2].

We can now calculate the probability that we draw some speciﬁc size-s sample

S, given the empirical distribution, and a ﬁxed value of s

Pr[draw S | G] =

x∈X

Pr[draw x | U]∗Pr[draw z | G]∗Pr[switched ballots are at indices in z]

However, we know that for each ballot b in z, we draw ballot b with probability

at most

+δ. That is, for any ballot in x, we know that we draw it with uniform

probability exactly. However, for a ballot b in z, we know that this a ballot that

may have been “switched”. In particular, with probability

, we draw the correct

12 M. Sridhar and R.Rivest

ballot from U. However, in addition to this, with probability δ, we replace it

with a new ballot - we assume that we replace it with the correct ballot with

probability 1. Thus, with probability at most

+ δ, we draw the correct ballot

for this particular slot. Thus, we get

Pr[draw S | G]

x∈X

Pr[draw x | U] ∗ Pr[draw z | G] ∗ Pr[switched ballots are at indices in z]

≤

x∈X

Pr[draw x | U] ∗ (

1 + nδ

)

∗ Pr[switched ballots are at indices in z]

≤ (1 + nδ)

x∈X

Pr[draw x | U] ∗ Pr[draw z | U] ∗ Pr[switched ballots are at indices in z] .

Now, we note that there are





possible sequences x ∈ X, where the

“switched” ballots could be. Each of these possible sequences occurs with equal

probability, this becomes

Pr[draw S | G]

≤ (1 + nδ)

x∈X

Pr[draw x | U] ∗ Pr[draw z | U] ∗ Pr[switched ballots are at indices in z] .

= (1 + nδ)

x∈X

Pr[draw x | U] ∗ Pr[draw z | U] ∗





= (1 + nδ)

Pr[draw S | U] .

Using this bound we can calculate our total change in acceptance probability

as:

Pr[A accepts | G] − Pr[A accepts | U]

≤ 

S∈D

Pr[A accepts | S](Pr[draw S | G, S has ≤ s

“switched” ballots] − Pr[draw S | U])

≤ 

+ ((1 + nδ)

− 1)

S∈D

Pr[A accepts | S] Pr[draw S | U]

≤ 

+ (1 + nδ)

− 1 ,

which provides us the required bound.

6.4 Empirical Support

Our previous theorem gives us a total bound of our change in risk limit, which

depends on our value of s

and δ. We note that, for each ballot b, we provide

a general bound of a multiplicative factor increase of (1 + nδ), which is based

oﬀ the variation distance of δ. However, we note that in practice, the exact

k-Cut: Simple Approximate Sampling 13

bound we are looking for depends on the multiplicative increase in probability

of a single ballot being chosen. That is, we can calculate the max increase in

multiplicative ratio for a single ballot, compared to the uniform distribution.

Thus, if a ballot is chosen with probability at most

(1+

)

, then our bound on

the change in probability becomes



+ (1 + 

)

− 1.

The values of 

are recorded, for varying number of cuts in Table 1.

We can calculate the maximum change in probability for a varying number of

cuts using this bound. Here, we analyze the case of 6 cuts. To get a bound on s

we can model how often we switch ballots. In particular, this follows a binomial

distribution, with s independent trials, where each trial has a δ

probability of

success. Using the binomial survival function, we see at most 4 “switched ballots”

in 1,000 draws, with probability (1- 8.78 × 10

−4

). From our previous argument,

we know that our change in acceptance probability is at most (1+

)

−1. Using

our value of 

for k = 6, this causes a change in probability of at most 0.0090.

Thus, the maximum possible change in probability of incorrectly accepting

this outcome is 0.0090 + 8.78 × 10

−4

, which is approximately 9.88 × 10

−3

. We

can compensate for this by adjusting our risk limit by less than 1%.

7 Multi-stack Sampling

Our discussion so far presumes that all cast paper ballots constitute a single

“stack,” and suggest using our proposed k-cut procedure is used to sample ballots

from that stack. In practice, however, stacks have limited size, since large stacks

are physically awkward to deal with. The collection of cast paper ballots is

therefore often arranged into multiple stacks of some limited size.

The ballot manifest describes this arrangement of ballots into stacks, giving

the number of such stacks and the number of ballots contained in each one. We

assume that the ballot manifest is accurate. A tool like Stark’s Tools for Risk-

Limiting Audits

takes the ballot manifest (together with a random seed and

the desired sample size) as input and produces a sampling plan.

A sampling plan describes exactly which ballots to pick from which stacks.

That is, the sampling plan consists of a sequence of pairs, each of the form:

(stack-number, ballot-id), where ballot-id may be either an id imprinted on the

ballot or the position of the ballot in the stack (if imprinted was not done).

Modifying the sampling procedure to use k-cut is straightforward. We ignore

the ballot-ids, and note only how many ballots are to be sampled from each

stack. That number of ballots are then selected using k-cut rather than using

the provided ballot-ids. For example, if the sampling plan says that 2 ballots are

to be drawn from stack 5, then we ignore the ballot-ids for those speciﬁc ballots,

and return 2 ballots drawn approximately uniformly at random using k-cut.

Thus, the fact that cast paper ballots may be arranged into multiple stacks

(or boxes) does not aﬀect the usability of k-cut for performing audits.

https://www.stat.berkeley.edu/ stark/Vote/auditTools.htm

14 M. Sridhar and R.Rivest

8 Approximate Sampling in Practice

The major question when using the approximate sampling procedure is how

to choose k. Choosing a small value of k makes the overall auditing procedure

more eﬃcient, since you save more time in each sample you choose. However, it

requires more risk limit adjustment.

The risk limit mitigation procedure requires knowledge of the maximum sam-

ple size, which we denote as s

∗

, beforehand. We assume that the auditors have a

reasonable procedure for estimating s

∗

for a given contest. One procedure to es-

timate s

∗

is to draw an initial sample, s, using uniform random sampling. Then,

we can use a statistical procedure to approximate how many additional ballots

we would need to ﬁnish the audit, assuming the rest of the ballots in the pool

are similar to the sample. Possible statistical procedures include replicating the

votes on the ballots, or using sample size estimates deﬁned in [8].

Let us assume that we use one of these techniques and calculate that the

audit is complete after an extension of size d. To be safe, we can assume that at

most 3d additional samples will be needed. Thus, our ﬁnal bound on s

∗

would

be s + 3d. Given this upper bound, we can perform our mitigation procedures,

assuming that we are drawing a sample of size s

∗

. Ballots after the ﬁrst s

∗

ballots

in our sample should be sampled uniformly at random.

9 Discussion and Open Problems

We would like to do more experimentation on the variation between individuals

on their cut-size distributions. The current empirical results in this paper are

based oﬀ of the cut distributions of just the two authors in the paper. We would

like to test a larger group of people to better understand a variety of empirical

distributions. After investigating this, we would like to develop “best practices”

for using the k-cut procedure. That is, we’d like to develop a set of techniques

that auditors can use to produce nearly-uniform single-cut-size distributions,

which will make k-cut more eﬃcient.

We would also like to run some experiments to test our assumptions for k-

cut, in practice. For instance, we would like to test whether each cut is truly

made independently.

In the longer version of the paper, we provide the full details of our empirical

data, for full reproducibility. We also discuss possible models for our empirical

data and the convergence rates of our models.

10 Conclusions

We have presented an approximate sampling procedure, k-cut, for use in post-

election audits. We expect the use of k-cut will save time since it eliminates the

need to count many ballots in a stack to ﬁnd the desired one.

k-Cut: Simple Approximate Sampling 15

We showed that even for small values of k, our procedure provides a sample

that is close to being chosen uniformly at random. We designed a simple mit-

igation procedure for RLAs that accounts for any remnant non-uniformity, by

adjusting the risk limit. Finally, we provided a recommendation of k = 6 cuts

to use in practice, for sample sizes up to 1,000 ballots, based on our empirical

data, with a 1% risk limit adjustment.

An earlier version of k-cut was used in pilot audits in Marion County, Indiana

to increase audit eﬃciency. This paper provides theoretical justiﬁcation for this

technique, which is also scheduled to be used in Michigan in December 2018.

References

1. Baign`eres, T., Vaudenay, S.: The complexity of distinguishing distributions (2008),

results also in Baigne`eres’ PhD thesis.

2. Banuelos, J.H., Stark, P.B.: Limiting risk by turning manifest phantoms into evil

zombies. https://arxiv.org/abs/1207.3413 (2012)

3. Bretschneider, J., Flaherty, S., Goodman, S., Halvorson, M., John-

ston, R., Lindeman, M., Rivest, R., Smith, P., Stark, P.: Risk-

limiting post-election audits: Why and how? (Oct 2012), (ver. 1.1)

http://people.csail.mit.edu/rivest/pubs.html#RLAWG12

4. Goggin, S.N., Byrne, M.D., Gilbert, J.E.: Post-election auditing eﬀects of procedure

and ballot type on manual counting accuracy, eﬃciency, and auditor satisfaction

and conﬁdence. Election Law Journal (2012)

5. Johnson, K.: Election veriﬁcation by statistical audit of voter-veriﬁed paper ballots.

http://ssrn.com/abstract=640943 (Oct 31 2004)

6. Lindeman, M., Halvorseon, M., Smith, P., Garland, L., Addona, V.,

McCrea, D.: Principle and best practices for post-election audits.

www.electionaudits.org/ﬁles/best%20practices%20ﬁnal 0.pdf (2008)

7. Lindeman, M., Stark, P.B.: A gentle introduction to risk-limiting audits. IEEE

Security and Privacy 10, 42–49 (2012)

8. Lindeman, M., Stark, P.B., Yates, V.S.: BRAVO: Ballot-polling risk-limiting au-

dits to verify outcomes. In: Halderman, A., Pereira, O. (eds.) Proceedings 2012

EVT/WOTE Conference (2012)

9. Miller, S.J., Nigrini, M.J.: The modulo 1 Central Limit Theorem and Benford’s

law for products. https://arxiv.org/abs/math/0607686 (2007)

10. Rivest, R.L.: Reference implementation code for pseudo-random sampler.

http://people.csail.mit.edu/rivest/sampler.py (2011)

11. Rivest, R.L.: Bayesian tabulation audits: Explained and extended.

https://arxiv.org/abs/1801.00528 (January 1, 2018)

12. Rivest, R.L., Shen, E.: A Bayesian method for auditing elections. In: Halder-

man, J.A., Pereira, O. (eds.) Proceedings 2012 EVT/WOTE Conference (2012),

https://www.usenix.org/system/ﬁles/conference/evtwote12/rivest bayes rev 073112.pdf,

https://www.usenix.org/conference/evtwote12/workshop-

program/presentation/rivest

13. Stark, P.B.: Papers, talks, video, legislation, software, and other documents on vot-

ing and election auditing. https://www.stat.berkeley.edu/ stark/Vote/index.htm

14. Stark, P.B.: Tools for ballot-polling risk-limiting election audits.

https://www.stat.berkeley.edu/ stark/Vote/ballotPollTools.htm (2017)