TransWikia.com

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

Quantum Computing Asked on February 16, 2021

$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 tag1label1
$$

$$
expectation{S} = N times sum_j expectation{X_j}/k = frac{N}{k} sum_{j=1}^k frac{M}{N} = M tag2label2
$$

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} tag3label3
$$

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 tag4label4$
  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} tag5label5$

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) tag6label6
$$

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} tag7label7
$$

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?

One Answer

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.

Correct answer by Nan on February 16, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP