1
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

1
$\begingroup$

I solved this problem using Chebyshev's inequality, $p(|S-E(S)|\geq\lambda\Delta(S))\leq1/\lambda^2$. To obtain a probability at least 3/4, let $\lambda=2$. We know that $$p\left(|S-E(S)|\leq2\Delta S\right)\geq\frac{3}{4}$$ i.e., $$p\left(|S-M|\leq2\sqrt{\frac{M(N-M)}{k}}\right)\geq\frac{3}{4}$$ To make $2\sqrt{\frac{M(N-M)}{k}}$ be $O(\sqrt{M})$, $k$ has to be $\Omega(N-M)=\Omega(N)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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