k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits
© 2020, International Financial Cryptography Association. 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 m...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137350 |
| _version_ | 1826198483333283840 |
|---|---|
| author | Sridhar, M Rivest, RL |
| author_facet | Sridhar, M Rivest, RL |
| author_sort | Sridhar, M |
| collection | MIT |
| description | © 2020, International Financial Cryptography Association. 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 picking the ballot on top. Unlike conventional methods of picking a ballot at random, k-cut does not require identification 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 procedures. We show that k=6 cuts is enough for a risk-limiting election audit, based on empirical data, which provides a significant increase in sampling efficiency. This method has been used in pilot RLAs in Indiana and is scheduled to be used in Michigan pilot audits in December 2018. |
| first_indexed | 2024-09-23T11:05:39Z |
| format | Article |
| id | mit-1721.1/137350 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:05:39Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1373502021-11-05T03:27:18Z k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits Sridhar, M Rivest, RL © 2020, International Financial Cryptography Association. 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 picking the ballot on top. Unlike conventional methods of picking a ballot at random, k-cut does not require identification 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 procedures. We show that k=6 cuts is enough for a risk-limiting election audit, based on empirical data, which provides a significant increase in sampling efficiency. This method has been used in pilot RLAs in Indiana and is scheduled to be used in Michigan pilot audits in December 2018. 2021-11-04T15:42:46Z 2021-11-04T15:42:46Z 2018-11 2021-02-04T17:05:34Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137350 Sridhar, M and Rivest, RL. 2018. "k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11599 LNCS. en 10.1007/978-3-030-43725-1_17 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing MIT web domain |
| spellingShingle | Sridhar, M Rivest, RL k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits |
| title | k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits |
| title_full | k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits |
| title_fullStr | k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits |
| title_full_unstemmed | k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits |
| title_short | k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits |
| title_sort | k cut a simple approximately uniform method for sampling ballots in post election audits |
| url | https://hdl.handle.net/1721.1/137350 |
| work_keys_str_mv | AT sridharm kcutasimpleapproximatelyuniformmethodforsamplingballotsinpostelectionaudits AT rivestrl kcutasimpleapproximatelyuniformmethodforsamplingballotsinpostelectionaudits |