0
$\begingroup$

Suppose I can make i.i.d. samples from the Bernoulli distribution with bias $p$ and want to find approximation $\hat{p} \in [(1-\epsilon)p,(1+\epsilon)p]$ with constant probability. I suppose that this should be possible to do in $O(\frac{1}{\epsilon^2 p})$ samples. Is this so? If so, are there any papers about this? I have found many papers which looked at maximum likelihood estimates or a Bayesian setting. I am interested in a reference, rather than in a solution as it must exist and I want to reference it in a paper.

$\endgroup$
0
$\begingroup$

I was finally able to find a reference, though it took me way too long. This paper [1] shows an algorithm that does exactly this, see Theorem 5 in that paper. The idea does not come from this paper, see the references they give.

[1] Sequential sampling techniques for algorithmic learning theory, Osamu Watanabe, https://core.ac.uk/download/pdf/82665979.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.