A Bernoulli mean estimate with known relative error distribution

Suppose that are independent identically distributed Bernoulli random variables with mean p , so and . Any estimate of p has relative error . This paper builds a new estimate of p with the remarkable property that the relative error of the estimate does not depend in any way on the value of p . This allows the easy construction of exact confidence intervals for p of any desired level without needing any sort of limit or approximation. In addition, is unbiased. For ? and δ in (0, 1), to obtain an estimate where , the new algorithm takes on average at most samples. It is also shown that any such algorithm that applies whenever requires at least samples on average. The same algorithm can also be applied to estimate the mean of any random variable that falls in . The used here employs randomness external to the sample, and has a small (but nonzero) chance of being above 1. It is shown that any nontrivial where the relative error is independent of p must also have these properties. Applications of this methodology include finding exact p‐values and randomized approximation algorithms for # P complete problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 173–182, 2017