3
$\begingroup$

$\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:

  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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.