Tight relative estimation in the mean of Bernoulli random variables
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Statistical Mean Estimation with Coded Relayed Observations
We consider a problem of statistical mean estimation in which the samples are not observed directly, but are instead observed by a relay (``teacher'') that transmits information through a memoryless channel to the decode…
DecoderHeavy Hitters and Bernoulli Convolutions
A very simple event frequency approximation algorithm that is sensitive to event timeliness is suggested. The algorithm iteratively updates categorical click-distribution, producing (path of) a random walk on a standard …
Beyond Binomial and Negative Binomial: Adaptation in Bernoulli Parameter Estimation
Estimating the parameter of a Bernoulli process arises in many applications, including photon-efficient active imaging where each illumination period is regarded as a single Bernoulli trial. Motivated by acquisition effi…
parameter estimationGeneralized Gumbel-Softmax Gradient Estimator for Generic Discrete Random Variables
Estimating the gradients of stochastic nodes in stochastic computational graphs is one of the crucial research questions in the deep generative modeling community, which enables the gradient descent optimization on neura…
Topic ModelsAn Efficient Labeled/Unlabeled Random Finite Set Algorithm for Multiobject Tracking
We propose an efficient random finite set (RFS) based algorithm for multiobject tracking in which the object states are modeled by a combination of a labeled multi-Bernoulli (LMB) RFS and a Poisson RFS. The less computat…
Object