Learning Bernoulli Parameter (problem related to a Quantum Algorithm)

Question

The LGZ algorithm for Topological Data Analysis via computing Betti Numbers is a quantum algorithm that relies on sampling random eigenvalues of an appropriate linear operator. The expected fraction of these eigenvalues that are 0 is equal to the normalised Betti Number.

My question concerns how many samples of random eigenvalues one would need to be confident that the estimator (i.e. the ratio of eigenvalues that are 0 in the sample) is close to its true value (the normalised Betti Number.

Abstracting away all details of quantum algorithms, the problem is effectively the following: Suppose we have a coin with some unknown probability of heads (p).

We make N flips of the coin with the aim of knowing p to within error ±ϵ, and with probability of failure <δ. For a given target of (ϵ,δ), how many flips N do we need to make?

Answer 1

The answer is $$ \Theta\left( \frac{\log(1/\delta)}{\varepsilon^2} \right) $$ for a uniform minimax bound. The upper bound follows from a Hoeffding bound; for the lower bound, you can derive it from the "simpler" testing question, as, e.g., outlined in this Wikipedia article. You can have a local minimax version as well, if that's what you want, with a dependence on the (unknown) parameter $p$ in the bound; see, e.g., this question.