Concentration inequalities for sampling without replacement, with applications to post-election audits
Many practical tasks involve sampling sequentially without replacement from a finite population in order to estimate some parameter, like a mean. We discuss how to derive powerful (new) concentration inequalities for this setting using martingale techniques, and apply it to auditing elections (see below).
This is joint work with my PhD student, Ian Waudby-Smith, who was an undergrad at UWaterloo. An early preprint is available here.
More details: When determining the outcome of an election, electronic voting machines are often employed for their tabulation speed and cost-effectiveness. Unlike paper ballots, these machines are vulnerable to software bugs and fraudulent tampering. Post-election audits provide assurance that announced electoral outcomes are consistent with paper ballots or voter-verifiable records. We propose an approach to election auditing based on confidence sequences (VACSINE)—these are visualizable sequences of confidence sets for the total number of votes cast for each candidate that adaptively shrink to zero width. These confidence sequences have uniform coverage from the beginning of an audit to the point of an exhaustive recount, but their main advantage is that their error guarantee is immune to continuous monitoring and early stopping, providing valid inference at any auditor-chosen, data-dependent stopping time. We develop VACSINEs for various types of elections including plurality, approval, ranked-choice, and score voting protocols.
Please Note: This talk will be given through Zoom. To join, please follow this link: Department Seminar by Aaditya Ramdas.