Risk-limiting financial audits via weighted sampling without replacement
Authors: Shubhanshu Shekhar, Ziyu Xu, Zachary Lipton, Pierre Liang, Aaditya Ramdas
Abstract
We introduce the notion of risk-limiting financial audits (RLFA): procedures that manually evaluate a subset of $N$ financial transactions to check the validity of a claimed assertion $\mathcal{A}$ about the transactions. More specifically, RLFA satisfy two properties: (i) if $\mathcal{A}$ is false, they correctly disprove it with probability at least $1-\delta$, and (ii) they validate the correctness of $\mathcal{A}$ with probability $1$, if it is true. We propose a general RLFA strategy, by constructing new confidence sequences (CSs) for the weighted average of $N$ unknown values, based on samples drawn without replacement from a (randomized) weighted sampling scheme. Next, we develop methods to improve the quality of CSs by incorporating side information about the unknown values. We show that when the side information is sufficiently accurate, it can directly drive the sampling. For the case where the accuracy is unknown