# Prove that classical counting requires $k=\Omega(N)$ oracle calls

Consider a classical algorithm for the counting problem which samples uniformly and independently $$k$$ times from the search space, and let $$X_1, ... ,X_k$$ be the results of the oracle calls, that is, $$X_j=1$$ if the $$j$$ th oracle call revealed a solution to the problem, and $$X_j=0$$ if the $$j^{th}$$ oracle call did not reveal a solution to the problem. This algorithm returns the estimate $$S≡N\times\sum_j X_j/k$$ for the number of solutions to the search problem. Show that the standard deviation in $$S$$ is $$\Delta S=\sqrt{M (N − M )/k}$$. Prove that to obtain a probability at least $$3/4$$ of estimating $$M$$ correctly to within an accuracy $$\sqrt{M}$$ for all values of $$M$$ we must have $$k=\Omega(N)$$.

First part of this problem is attempted to prove in a similar post, named Nielsen & Chuang Exercise 6.13: Standard deviation of classical counting algorithm, as

$$E[S]=E\Big(N\times\sum_j X_j/k\Big)=\frac{N}{k}\times E\Big( \sum_jX_j \Big)=\frac{N}{k}\times \sum_j E(X_j)\\$$ where we have $$E(X_j)=1\times P(X_j=1)+0\times P(X_j=0)=P(X_j=1)=M/N$$, therefore $$E[S]=\frac{N}{k}\times \sum_j \frac{M}{N}=\frac{N}{k}\times\frac{k\times M}{N}=M$$ Similarly, $$(E[S^2])=E[(N\times\sum_j X_j/k)^2]=\frac{N^2}{k^2}(\sum_j X_j)^2=\frac{N^2}{k^2}\sum_{i=1}^{k}\sum_{j=1}^{k} X_iX_j$$ Case 1 : $$i=j$$ $$E(X_iX_j)=E(X_i^2)=P(X_i=1)=M/N$$ Case 2 : $$i\neq j$$ $$E(X_iX_j)=P(X_i=1,X_j=1)=P(X_i=1)P(X_j=1)=M^2/N^2$$ Note that case 1 happens $$k$$ times, therefore case 2 happens $$k^2-k$$ times. $$\therefore\\ E(S^2)=\frac{N^2}{k^2}\sum_{i=1}^{k}\sum_{j=1}^{k} X_iX_j=\frac{N^2}{k^2}\bigg[k\frac{M}{N}+(k^2-k)\frac{M^2}{N^2}\bigg]=\frac{MN}{k}+M^2-\frac{M^2}{k}$$ and therefore, $$Var(S)=E[S^2]-(E[S])^2=\frac{MN}{k}+M^2-\frac{M^2}{k}-M^2=\frac{M(N-M)}{k}\\ \implies \Delta(S)=\sqrt{M(N-M)/k}$$

The remaining part is,

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

How do I make sense of the remaining part of the problem ?

I solved this problem using Chebyshev's inequality, $$p(|S-E(S)|\geq\lambda\Delta(S))\leq1/\lambda^2$$. To obtain a probability at least 3/4, let $$\lambda=2$$. We know that $$p\left(|S-E(S)|\leq2\Delta S\right)\geq\frac{3}{4}$$ i.e., $$p\left(|S-M|\leq2\sqrt{\frac{M(N-M)}{k}}\right)\geq\frac{3}{4}$$ To make $$2\sqrt{\frac{M(N-M)}{k}}$$ be $$O(\sqrt{M})$$, $$k$$ has to be $$\Omega(N-M)=\Omega(N)$$.