# Tools for Ballot-Polling Risk-Limiting Election Audits

This page implements some tools to conduct "ballot-polling" risk-limiting audits as described in A Gentle Introduction to Risk-Limiting Audits (AGI), by Lindeman and Stark, and BRAVO: Ballot-polling Risk-limiting Audits to Verify Outcomes, by Lindeman, Stark, and Yates. For an implementation of tools for "comparison" risk-limiting audits as described in AGI, see http://statistics.berkeley.edu/~stark/Vote/auditTools.htm.

To hide or show everything but the tools, click this link.

A risk-limiting audit is a procedure that is guaranteed to have a large chance of progressing to a full hand count of the votes if the electoral outcome is wrong. The outcome according to the hand count then replaces the outcome being audited. The risk limit is the maximum chance that the audit will not progress to a full hand count if the electoral outcome is incorrect, no matter why it is incorrect—whether because of voter error, bugs, pollworker error, or deliberate fraud—provided the audit trail is complete and accurate.

There are many methods for conducting risk-limiting audits. This page performs calculations for a particularly simple method described in AGI, a ballot-polling audit.

The expected sample size calculations for this method depend on the risk limit and the reported margins; the expected sample size calculation assumes that the reported margins are correct.

Efficient risk-limiting audits generally count votes by hand until there is convincing evidence that the outcome according to a full hand count would agree with the outcome under audit. If convincing evidence is not forthcoming, the audit progresses to a full hand count, which is used to correct the outcome under audit if the two disagree.

• Choose a number of ballots to audit initially, on the assumption that the contest outcome is correct.
• Select a random sample of ballots
• Find those ballots using a ballot manifest
• Determine whether the audit can stop, given the votes on the ballots in the sample. If the audit cannot stop yet, estimate how many additional ballots will need to be audited

## Initial sample size

The initial sample size tool lets you enter the particulars of the contest(s) to be audited as a group: the total ballots cast across all the contests combined, and the vote totals for each candidate in each contest. The form helps you anticipate the number of randomly selected ballots that might need to be inspected to attain a given limit on the risk, under the assumption that the reported percentages for each candidate are correct. It is completely legitimate to sample one at a time and check whether enough have been sampled using the "stopping sample size tool," (later in this page) but this form can help auditors anticipate how many ballots the audit is likely to require and to retrieve ballots more efficiently, by reducing the number of times a given batch of ballots is opened.

Enter the total number of ballots cast in all contests to be audited. Add candidates and contests as necessary until the results from all contests have been entered. Enter the desired risk limit. Finally, click "calculate" to find the starting sample size.

Initial sample size
Contest information    Smallest margin (votes): undefined. Diluted margin: undefined.

Audit parameters Expected sample size: undefined.

Taking a larger initial sample can avoid needing to expand the sample later, depending on the rate of ballots for each candidate in the sample. Avoiding "escalation" can make the audit less complicated.

### Considerations for deciding which contests to audit together

The number of ballots the audit must examine before stopping depends on the smallest diluted margin among the contests to be audited together (as well as the risk limit, the errors the audit finds, and so on). All else equal, the larger the diluted margin is, the smaller the sample size needs to be.

Because the diluted margin is the smallest margin in votes divided by the total number of ballots cast in all the contests under audit, auditing small contests together with large contests can be inefficient: Dividing the vote margin in small contests by the number of ballots cast in large contests can make the diluted margin very small, which makes the required sample very large.

Generally, if two contests overlap substantially—for instance, if both are jurisdiction-wide contests—it is more economical to audit them together: Fewer ballots will need to be inspected in all. Conversely, if two contests do not overlap at all, it is more efficient to audit them separately.

Auditing small contests together with (overlapping) large contests generally is not efficient unless the vote margin in the small contests is a substantial fraction of the vote margin in the large contests. That is, auditing small contests that have large percentage margins together with large contests that have small percentage margins can be efficient, but auditing small contests together with large contests that have comparable vote margins generally is not efficient, because it makes the diluted margin of the combination much smaller.

The tool above can be used to explore whether it makes sense to audit a collection of contests together by checking whether the expected sample size when they are audited together is greater than the sum of the expected sample sizes when they are audited separately. (If you experiment with different groupings of contests, be sure to change the entry for "Ballots cast in all contests" to reflect only the contests that are to be audited together.)

Show technical notes.

The initial sample size form implements this formula, adapted from BRAVO to account for ballots that do not show a vote for either candidate in a pair:

$$\mbox{ASN}_{w,\ell} \approx \frac{N}{N_{w\ell}}\frac{\ln(1/\alpha) + \ln(2s_w)/2}{ p_w \ln(2s_w) + p_\ell \ln(2 - 2s_w)},$$

where $$w$$ is a candidate reported to have won; $$\ell$$ is a candidate reported to have lost; $$N$$ is the total number of ballots cast, including votes for all candidates, undervotes, and overvotes; $$N_{w\ell}$$ is the total number of ballots with a vote for either $$w$$ or $$\ell$$ but not both; $$p_c$$ is the fraction of votes for candidate $$c$$ among ballots that show a vote for either $$w$$ or $$\ell$$ but not both; and

$$s_c \equiv \frac{p_c}{\sum_j p_j}.$$

The overall average sample number is the maximum of $$\mbox{ASN}_{w,\ell}$$ over all (winner, loser) pairs $$(w, \ell)$$.

## Random sampling

The next tool helps generate a pseudo-random sample of ballots. To start, input a random seed with at least 20 digits (generated by rolling a 10-sided die, for instance), the number of ballots from which you want a sample, and the number of ballots you want in the sample. Further below, there is a form to help find the individual, randomly selected ballots among the batches in which ballots are stored.

Pseudo-Random Sample of Ballots

The "seed," concatenated with a comma and the "Sample number," is passed through the SHA-256 hash function. The result is displayed as "Hashed value (for testing)". The hashed value, interpreted as a hexadecimal number, is divided by "Number of objects from which to sample." One is added to the remainder of that division to get "Randomly selected item," which will be a number between 1 and "Number of objects from which to sample," inclusive. Clicking "draw sample" successively adds one to "Sample number" and recomputes "Hashed value" and "Randomly selected item" "Draw this many objects" times. Selected items accumulate in "Ballots selected" (and "Ballots selected, sorted"), which reset if the seed or the number of objects changes. The same ballot might be selected more than once. Duplicates are removed in "Ballots selected, duplicates removed." Ballots selected more than once, and the frequencies of those ballots, are in "Repeated ballots." Clicking the "reset" button clears the history but leaves the seed.

I learned about this method of generating pseudo-random numbers from Ronald L. Rivest; it is related to a method described in http://tools.ietf.org/html/rfc3797. The SHA-256 hash algorithm produces hash values that are hard to predict from the input. They are also roughly equidistributed as the input varies. The advantages of this approach for election auditing and some other applications include the following:

• The SH-256 algorithm is public and many implementations are available in many languages. (The Javascript implementation used by this page was written by Brian Turek; The JavaScript routines for arithmetic long integers—the SHA-256 hashed values—were written by Leemon Baird).
• Given the seed, anyone can verify that the sequence of numbers generated was correct—that it indeed comes from applying SHA-256.
• Unless the seed is known, the sequence of values generated is unpredictable (so the result is hard to "game"). It is very hard to distinguish the output from independent, uniformly distributed samples.

For comparison, a reference implementation of this approach in Python written by Ronald L. Rivest is available at http://people.csail.mit.edu/rivest/sampler.py.

For more detail, see http://statistics.berkeley.edu/~stark/Java/Html/sha256Rand.htm.

## Find ballots using a ballot manifest

Generally, ballots will be stored in batches, for instance, separated by precinct and mode of voting. To make it easier to find individual ballots, it helps to have a ballot manifest that describes how the ballots are stored. For instance, we might have 1,000 ballots stored as follows:

Batch labelballots
Polling place precinct 1 130
Vote by mail precinct 1 172
Polling place precinct 2 112
Vote by mail precinct 2 201
Polling place precinct 3 197
Vote by mail precinct 3 188

If ballot 500 is selected for audit, which ballot is that? If we take the listing of batches in the order given by the manifest, and we require that within each batch, the ballots are in an order that does not change during the audit, then the 500th ballot is the 86th ballot among the vote by mail ballots for precinct 2: The first three batches have a total of 130+172+112 = 414 ballots. The first ballot in the fourth batch is ballot 415. Ballot 500 is the 86th ballot in the fourth batch.

The ballot look-up tool transforms a list of ballot numbers and a ballot manifest into a list of ballots in each batch. Batch labels should not contain commas. Use a comma to separate each batch label from the number of ballots in that batch (or the range of ballot numbers or the set of ballot identifiers—see below). The manifest should have one line per batch and no empty lines.

For instance, to input the ballot manifest above, you would enter:

Polling place precinct 1, 130
Vote by mail precinct 1, 172
Polling place precinct 2, 112
Vote by mail precinct 2, 201
Polling place precinct 3, 197
Vote by mail precinct 3, 188


Some jurisdictions number the ballots cast in an election. If all the ballots in an election are numbered sequentially, the numbers on the ballots that contain a particular contest might not be sequential. For instance, an election might cover precincts 1, 2, and 3, but only voters in precincts 1 and 3 are eligible to vote in the contests to be audited with the current sample. In the previous example, suppose that the jurisdiction had stamped numbers on all the ballots, sequentially, so that the ballots from the polling place in precinct 1 were numbered 1 to 130, the vote by mail ballots from precinct 1 were numbered 131 to 302, the ballots from the polling place in precinct 2 were numbered 303 to 414, and so on, as summarized in the following table:

Batch labelballot range
Polling place precinct 1 1 to 130
Vote by mail precinct 1 131 to 302
Polling place precinct 2 303 to 414
Vote by mail precinct 2 415 to 615
Polling place precinct 3 616 to 812
Vote by mail precinct 3 813 to 994
Provisional ballots for precinct 1 996, 998, 1000
Provisional ballots for precinct 2 997
Provisional ballots for precinct 3 995, 999

Since the ballots already have numbers on them, it makes sense to look them up using those numbers. If we were auditing a collection of contests that included only precincts 1 and 3, the ballots subject to audit would be the 686 ballots labeled 1 to 130, 131 to 302, 616 to 812, and 813 to 994, and 995, 996, 998, and 1000. In this case, the ballot manifest would include only the six batches that comprise precincts 1 and 3, not all eight batches; there are only 686 ballots in these batches. Each line in the manifest would consist of a batch label and a range of ballot numbers, where the range is denoted by a colon, or of a batch label and a set of ballot identifiers in parentheses, separated by spaces. Ballot ranges cannot have gaps: There can be no missing numbers within the range for any single batch. (If there is in fact a gap, input the numbers as a set of identifiers, rather than as a range.) Again, separate the label from the range or set of ballot numbers by a comma. The label must not contain any commas, and the range of ballot numbers or set of identifiers must not contain commas. In this example, we would enter the ballot manifest as follows:

Polling place precinct 1, 1:130
Vote by mail precinct 1, 131:302
Polling place precinct 3, 616:812
Vote by mail precinct 3, 813:994
Provisional precinct 1, (996 998 1000)
Provisional precinct 3, (995 999)


The total number of ballots in the manifest must equal the number cast in the contests that are to be audited together using the sample (686 in this example).

Ballot look-up tool

## Should more ballots be audited?

The audit looks at every (winner, loser) pair in each contest. Auditing continues until there is strong evidence that every winner in a contest got more votes than every loser in the contest. It does this by considering (winner, loser) pairs, which are represented in the table below. The numbers in the table all start at 1. Votes for a winner will decrease the numbers in that winner's column for that winner's contest. Votes for a loser will increase the numbers in that loser's row for that loser's contest. The audit continues until all the numbers are not larger than the risk limit. E.g., if the risk limit is 10%, the audit stops when the numbers in the table are all less than 0.1.

Audit progress

The stopping rule implements the following formula from AGI: FIX ME!