This is a question from a quantum computation textbook.

Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times from the Search Space of size $N$ for solutions using an Oracle that outputs 1 or 0, and let $X_1,X_2,X_3,...X_k$ be the results of the Oracle calls. So $X_j=1$ if the $jth$ Oracle call found a solution and $X_j=0$ otherwise. This algorithm estimates the number of solutions $S$:

$$S=N * \sum_{j}\frac{X_j}{k}$$

Assuming the number of solutions is $M$ and this is not known in advance. The Standard Deviation of $S$ is stated and found to be:

$$\Delta S=\sqrt{\frac{M(N-M)}{k}}$$

The question is:
Prove that to obtain a probability at least $\frac{3}{4}$ of estimating $M$ correctly to within an accuracy $\sqrt{M}$ for all values of $M$, we must have $k=\Omega(N)$.

I know how to get the 2nd equation from the 1st, which is by moving $N$ and $k$ to the left, thus treating $kS/N$ as a Binomial Distribution $B(k,\frac{M}{N})$. Then finding the variance of the Binomial Distribution and some algebraic manipulation will lead to the 2nd equation. I'm clueless in proving of $k=\Omega(N)$. Only thing I tried writing is:

$$P\Big(\sqrt{\frac{M(N-M)}{k}}\leq \sqrt{M}\Big)\geq \frac{3}{4}$$

Can someone help me with this?

  • $\begingroup$ You need an anti-concentration result such as Paley-Zygmund. $\endgroup$ – Yuval Filmus Jul 1 '19 at 15:12
  • $\begingroup$ @YuvalFilmus That looks complicated. Are you able to show me how to apply it in this context? $\endgroup$ – C.C. Jul 1 '19 at 16:39
  • $\begingroup$ It's your exercise. You should give it a shot. $\endgroup$ – Yuval Filmus Jul 1 '19 at 16:41

Consider a binomial random variable $X \sim \mathrm{bin}(n,p)$, and let $Y = (X - pn)^2$. A straightforward but long calculation shows that $$ \frac{\mathbb{E}[Y]^2}{\mathbb{E}[Y^2]} = \frac{np(1-p)}{p^3 + (1-p)^3 + 3(n-1)p(1-p)} = \frac{1}{3} + o(1). $$ (This is to be expected, since a binomial random variable has roughly Gaussian distribution, and for Gaussian distributions the ratio is exactly $1/3$.)

Now let $Z = (S - M)^2$. It is still the case that $$ \frac{\mathbb{E}[Z]^2}{\mathbb{E}[Z^2]} = \frac{1}{3} + o(1), $$ since $Z$ is just a scalar multiple of $Y$ above, for an appropriate choice of parameters.

In view of applying the Paley–Zygmund inequality, let us estimate $$ \theta = \frac{M}{\mathbb{E}[Z]} = \frac{M}{M(N-M)/k} = \frac{k}{N-M}. $$ It follows that $$ \Pr[|S-M| > \sqrt{M}] = \Pr[Z > M] \geq (1-\theta)^2 \left(\frac{1}{3} + o(1)\right). $$ If we want the right-hand side to be bounded by some constant (in your case, $1/4$) then we need $\theta$ to be bounded from below by some constant $c$ (in your case, roughly $1-\sqrt{3/4}$). In other words, we need $$ k = \theta (N-M) = \Omega(N-M). $$ As long as $M$ is not very close to $N$, this is $\Omega(N)$.

(When $M$ is very close to $N$, less samples are needed. For example, only one sample is needed when $M = N$.)

  • $\begingroup$ Wow.. Thank you for sharing the solution in this clear manner. My aptitude in math is not yet mature to this level. Haha I don't think I would have figure out these steps myself. $\endgroup$ – C.C. Jul 2 '19 at 14:01
  • $\begingroup$ Just one more clarification. Shouldn't it be $P(|S-M|\leq\sqrt{M})$ since the estimate $S$ must be within $\pm\sqrt{M}$ of $M$? $\endgroup$ – C.C. Jul 2 '19 at 14:22
  • $\begingroup$ I'll let you work that out. It's part of understanding the solution. $\endgroup$ – Yuval Filmus Jul 2 '19 at 14:23
  • $\begingroup$ If we were to stick with $Pr(|S-M| > \sqrt{M})$ and we let the right side be bounded by the constant $1/4$, then shouldn't the inequality between $Pr()$ and $1/4$ be $<$? How are we going to apply the Paley-Zygmund Theorem? $\endgroup$ – C.C. Jul 2 '19 at 14:45
  • $\begingroup$ I suggest you spend a few hours thinking it through. $\endgroup$ – Yuval Filmus Jul 2 '19 at 14:46

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.