A Bernoulli mean estimate with known relative error distribution1. Issue 2 (30th March 2016)

• Record Type: Journal Article
• Authors: Huber, Mark
• Is Part Of: Random structures & algorithms. Volume 50:Issue 2(2017)
• Page Start: 173
• Page End: 182
• Publication Date: 2016-03-30
• Subjects: Bernoulli -- randomized approximation scheme -- exact confidence interval; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20654
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Suppose that X 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 error p ^ / 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 ϵ − 2 p − 1 ln ( 2 δ − 1 ) ( 1 − ( 4 / 3 ) ϵ ) − 1 samples. 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 − 1 samples 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