k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-Election Audits
k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-Election Audits
复制标题
k-Cut：选举后审计中选票抽样的简单近似统一方法
DOI：
10.1007/978-3-030-43725-1_17
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Rivest
中科院分区：
文献类型：
--
作者：
Mayuri Sridhar;R. Rivest
我们提出了一个近似的抽样框架，并讨论如何风险限制审计可以弥补这些近似值，同时保持其“风险限制”的属性。我们的框架是通用的，可以弥补审计过程中的计数错误。
此外，我们提出并分析了一个简单的近似抽样方法，“$k$-cut”，从堆栈中随机挑选一张选票，不计数。我们的方法涉及到做$k$“切割”，每次都涉及到将选票的随机部分从堆栈的顶部移动到底部，然后选择顶部的选票。与传统的随机抽取选票的方法不同，$k$-cut不需要选票上的识别号码，也不需要每次抽取计算许多选票。我们分析了选择选票的分布与均匀分布的接近程度，并设计了不同的缓解程序。我们表明，$k=6$削减是足够的风险限制选举审计，根据经验数据，这将提供一个显着的效率提高。
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 different mitigation procedures. We show that $k=6$ cuts is enough for an risk-limiting election audit, based on empirical data, which would provide a significant increase in efficiency.