Estimation of the number of solutions by Counting

Question

This is a question from a quantum computation textbook.

Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times from the Search Space of size $N$ for solutions using an Oracle that outputs 1 or 0, and let $X_1,X_2,X_3,...X_k$ be the results of the Oracle calls. So $X_j=1$ if the $jth$ Oracle call found a solution and $X_j=0$ otherwise. This algorithm estimates the number of solutions $S$:

$$S=N * \sum_{j}\frac{X_j}{k}$$

Assuming the number of solutions is $M$ and this is not known in advance. The Standard Deviation of $S$ is stated and found to be:

$$\Delta S=\sqrt{\frac{M(N-M)}{k}}$$

The question is:
Prove that to obtain a probability at least $\frac{3}{4}$ of estimating $M$ correctly to within an accuracy $\sqrt{M}$ for all values of $M$, we must have $k=\Omega(N)$.

I know how to get the 2nd equation from the 1st, which is by moving $N$ and $k$ to the left, thus treating $kS/N$ as a Binomial Distribution $B(k,\frac{M}{N})$. Then finding the variance of the Binomial Distribution and some algebraic manipulation will lead to the 2nd equation. I'm clueless in proving of $k=\Omega(N)$. Only thing I tried writing is:

$$P\Big(\sqrt{\frac{M(N-M)}{k}}\leq \sqrt{M}\Big)\geq \frac{3}{4}$$

Can someone help me with this?

Answer 1

Consider a binomial random variable $X \sim \mathrm{bin}(n,p)$, and let $Y = (X - pn)^2$. A straightforward but long calculation shows that $$ \frac{\mathbb{E}[Y]^2}{\mathbb{E}[Y^2]} = \frac{np(1-p)}{p^3 + (1-p)^3 + 3(n-1)p(1-p)} = \frac{1}{3} + o(1). $$ (This is to be expected, since a binomial random variable has roughly Gaussian distribution, and for Gaussian distributions the ratio is exactly $1/3$.)

Now let $Z = (S - M)^2$. It is still the case that $$ \frac{\mathbb{E}[Z]^2}{\mathbb{E}[Z^2]} = \frac{1}{3} + o(1), $$ since $Z$ is just a scalar multiple of $Y$ above, for an appropriate choice of parameters.

In view of applying the Paley–Zygmund inequality, let us estimate $$ \theta = \frac{M}{\mathbb{E}[Z]} = \frac{M}{M(N-M)/k} = \frac{k}{N-M}. $$ It follows that $$ \Pr[|S-M| > \sqrt{M}] = \Pr[Z > M] \geq (1-\theta)^2 \left(\frac{1}{3} + o(1)\right). $$ If we want the right-hand side to be bounded by some constant (in your case, $1/4$) then we need $\theta$ to be bounded from below by some constant $c$ (in your case, roughly $1-\sqrt{3/4}$). In other words, we need $$ k = \theta (N-M) = \Omega(N-M). $$ As long as $M$ is not very close to $N$, this is $\Omega(N)$.

(When $M$ is very close to $N$, less samples are needed. For example, only one sample is needed when $M = N$.)