A Bernoulli mean estimate with known relative error distribution

Abstract Suppose thatX 1 , X 2 , … are independent identically distributed Bernoulli random variables with mean p , so ℙ ( X i = 1 ) = p and ℙ ( X i = 0 ) = 1 − p . Any estimate p ^ of p has relative errorp ^ / p − 1 . This paper builds a new estimate p ^ 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, p ^ is unbiased. For ∊ and δ in (0, 1), to obtain an estimate where ℙ ( | p ^ / p − 1 | > ϵ ) ≤ δ , the new algorithm takes on average at most 2 ϵ − 2p − 1 ln ( 2 δ − 1 ) ( 1 − ( 4 / 3 ) ϵ ) − 1samples. It is also shown that any such algorithm that applies whenever p ≤ 1 / 2 requires at least ( 1 / 5 ) ϵ − 2 ( 1 + 2 ϵ ) ( 1 − δ ) ln ( ( 2 − δ ) δ − 1 ) p − 1samples on average. The same algorithm can also be applied to estimate the mean of any random variable that falls in [ 0 , 1 ] . The p ^ 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 p ^ 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