Tight relative estimation in the mean of Bernoulli random variables
This work provides an incremental improvement for researchers in streaming algorithms and statistical estimation, offering a more efficient solution under specific conditions.
The paper tackles the problem of estimating the mean of Bernoulli random variables with a specified relative error and failure probability, introducing a new method that is faster than the previous best (GBAS) when the mean is bounded away from zero.
Given a stream of Bernoulli random variables, consider the problem of estimating the mean of the random variable within a specified relative error with a specified probability of failure. Until now, the Gamma Bernoulli Approximation Scheme (GBAS) was the method that accomplished this goal using the smallest number of average samples. In this work, a new method is introduced that is faster when the mean is bounded away from zero. The process uses a two-stage process together with some simple inequalities to get rigorous bounds on the error probability.