$\newcommand{\expectation}[1]{\mathop{\mathbb{E}} \left[ #1 \right] } \newcommand{\Var}{\mathrm{Var}}$ From Nielsen & Chuang 10th edition page 261:
Consider a classical algorithm for the counting problem which samples uniformly and independently $k$ times from the search space, and let $X1, \dots, 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 \equiv N \times \sum_j X_j/k$ for the number of solutions to the search problem. Show that the standard deviation in $S$ is $\bigtriangleup S = \sqrt{ M(N − M)/k }$.
The question goes on but I'm already stuck here. To get to the standard deviation first I'm trying to calculate the variance via:
$$ \Var(S) = \expectation{S^2} - \expectation{S}^2 \tag1\label1 $$ $$ \expectation{S} = N \times \sum_j \expectation{X_j}/k = \frac{N}{k} \sum_{j=1}^k \frac{M}{N} = M \tag2\label2 $$
Therefore $S$ is an unbiased estimator of M.
Now:
$$ \expectation{S}^2 = \expectation{\left( N \times \sum_j X_j/k \right)^2} = \frac{N^2}{k^2} \expectation{\left( \sum_j X_j \right)^2} = \frac{N^2}{k^2} \sum_{i=1}^k \sum_{j=1}^k \expectation{X_i X_j} \tag3\label3 $$
To calculate $\expectation{X_i X_j}$ we need to consider 2 cases:
- $i=j \implies \expectation{X_i X_i}=P(X_i=1)=M/N \tag4\label4$
- $i \neq j \implies \expectation{X_i X_j}=P(X_i=1, X_j=1)=\frac{M}{N} \frac{M-1}{N-1} \tag5\label5$
Case 1 happens $k$ times, therefore case 2 must happen $k^2-k$ times. So we have:
$$ \expectation{S}^2 = \frac{N^2}{k^2} \left( k \frac{M}{N} + (k^2 - k) \frac{M}{N} \frac{M-1}{N-1} \right) \tag6\label6 $$
Putting \eqref{2} and \eqref{6} together, after some tedious algebra I got:
$$ \Var(S) = \frac{M}{k} \frac{(N-M)(N-k)}{N-1} \tag7\label7 $$
If $k \ll N$, then \eqref{7} is close to what is stated in the original question but is not exactly it. Can anyone spot where I made the blunder?
