Friday, September 22, 2006

Rivest on audit size estimation

Ron Rivest has a draft of an excellent paper on estimating the number of items (e.g. voting machines) that need to be audited to discover whether or not the machines are cheating. The paper assumes that there is a reliable way to manually check whether a machine is cheating. For example, if every machine had a corresponding paper trail that had been verified by voters, then one could count the papers by hand and check them against the machine.

Rivest has once again dazzled us with his creativity. He presents a simple rule of thumb that can be calculated with a calculator or in one's head for determining how many machines to audit, using what he terms the "rule of 3". Appendix A is especially useful for people who do not follow the technical details. It shows the number of machines to audit based on the number of bad ones that exist and based on the confidence level one wants to achieve. So, for example, in appendix A, you can see that if you have 1,000 machines, and there are 50 "bad" ones, then to have 95% confidence that you have discovered at least one of the bad ones, you must audit at least 57 machines. This, as compared to the rule of thumb which produces the number 59. Amazingly, the rule of thumb is so elegant, and yet it always comes close, and always errs on the side of being a little conservative, meaning that it will never recommend auditing too few.

Rivest has not published this draft, and he is still seeking comments, so if you have any suggestions after reading his paper, he would appreciate it if you could send them.

I now quote from the last section of the paper, where I think this work can have tremendous impact:

    "We hope that the rules presented here will provide useful guidance for those designing sampling procedures for would probably be best to merely mandate a sample size sufficient to detect, with a specified level of confidence, any election fraud sufficient to have changed the outcome."

I often meet with legislators at the state and federal level to discuss voting issues, and I will be pointing them to this work from now on. Thank you Ron Rivest for once again contributing something elegant, practical and long needed!