# Estimation of the number of solutions by Counting

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?

• You need an anti-concentration result such as Paley-Zygmund. Jul 1, 2019 at 15:12
• @YuvalFilmus That looks complicated. Are you able to show me how to apply it in this context?
– C.C.
Jul 1, 2019 at 16:39
• It's your exercise. You should give it a shot. Jul 1, 2019 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$$.)

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