# Nielsen & Chuang Exercise 6.13: Standard deviation of classical counting algorithm

$$\newcommand{\expectation}{\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:

1. $$i=j \implies \expectation{X_i X_i}=P(X_i=1)=M/N \tag4\label4$$
2. $$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?

Since the classical algorithm samples "uniformly and independently $$𝑘$$ times from the search space", equation $$(5)$$ should be, $$P(X_i=1, X_j=1)= P(X_i=1)P(X_j=1)=\frac{M^2}{N^2}$$ instead. If you substitute $$(5)$$ with this, you would arrive at the book's standard deviation.