3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ You need an anti-concentration result such as Paley-Zygmund. $\endgroup$ Jul 1, 2019 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, 2019 at 16:39
  • $\begingroup$ It's your exercise. You should give it a shot. $\endgroup$ Jul 1, 2019 at 16:41

1 Answer 1

1
$\begingroup$

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

$\endgroup$
10
  • $\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, 2019 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, 2019 at 14:22
  • $\begingroup$ I'll let you work that out. It's part of understanding the solution. $\endgroup$ Jul 2, 2019 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, 2019 at 14:45
  • $\begingroup$ I suggest you spend a few hours thinking it through. $\endgroup$ Jul 2, 2019 at 14:46

Your Answer

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

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