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 ?
