The Exercise

A search space holds $N$ items, $M$ of them solutions, and an oracle answers whether a given item is a solution. A classical algorithm estimates $M$ by sampling: it draws $k$ items uniformly and independently, asks the oracle about each, and returns the fraction of draws that turned up a solution, multiplied by $N$ . The exercise asks for the standard deviation of this estimate, and then for the number of draws it takes to get $M$ right to within $\sqrt{M}$ with probability at least three quarters, whatever the value of $M$ ; the answer is a number of draws linear in $N$ .

Sampling the Search Space

The success probability $p$ of a draw from $N$ items of which $M$ are solutions is the number $p = \min\Bigl(\frac{M}{N},\, 1\Bigr).$ (1)^✦

A draw has two outcomes, $\mathrm{yes}$ when the oracle finds a solution and $\mathrm{no}$ when it does not. The distribution $\mu_p$ of a single draw is the Bernoulli distribution with parameter $p$ on these two outcomes: $\mu_p(\mathrm{yes}) = p, \qquad \mu_p(\mathrm{no}) = 1 - p.$ (2)^✦

A run of $k$ draws is a sequence $\omega = (\omega_1, \dots, \omega_k)$ of outcomes. The distribution $P_{N,M,k}$ of a run is the product of $k$ copies of $\mu_p$ , one for each draw, so that the draws are independent: $P_{N,M,k}(\omega) = \prod_{i=1}^{k} \mu_p(\omega_i).$ (3)^✦

The indicator $X_i$ of the $i$ th draw is the function on runs that equals one when that draw finds a solution and zero otherwise: $X_i(\omega) = \begin{cases} 1, & \omega_i = \mathrm{yes},\\ 0, & \omega_i = \mathrm{no}. \end{cases}$ (4)^✦ The sampling estimator $S$ is the function on runs that counts the successful draws and scales the count by $N/k$ : $S(\omega) = \frac{N}{k} \sum_{i=1}^{k} X_i(\omega).$ (5)^✦ It does not depend on $M$ ; only the distribution of the runs does.

The standard deviation $\Delta S$ of the estimator is the square root of its variance, where $\mathbb{E}$ denotes the expectation over runs distributed according to $P_{N,M,k}$ : $\Delta S = \sqrt{\mathbb{E}\bigl[(S - \mathbb{E}\,S)^2\bigr]}.$ (6)^✦

The Claim

Theorem 1. For a search space of $N \ge 1$ items with $M \le N$ solutions and a run of $k \ge 1$ draws, the standard deviation of the sampling estimator is $\Delta S = \sqrt{\frac{M(N-M)}{k}}.$ (7)^✦

The number of successes $\sum_i X_i$ is binomial with variance $kp(1-p)$ ; scaling by $N/k$ and putting $p = M/N$ gives (7).

Theorem 2. Let a run have $k \ge 1$ draws from a search space of $N$ items, and suppose that for every number of solutions $M$ with $1 \le M \le N-1$ the sampling estimator satisfies $P_{N,M,k}\bigl(\,\lvert S - M \rvert \le \sqrt{M}\,\bigr) \ge \frac{3}{4}.$ (8)^✦ Then $N < 4k$ .^✦

What Is Checked

Both claims are stated over the distribution $P_{N,M,k}$ of a run of $k$ independent draws, the product (3) of Bernoulli distributions with parameter $p$ , and over the estimator $S$ built from the indicators of the draws; the first claim is also stated over the standard deviation $\Delta S$ . The library proves of these constructions that the success probability (1) is at most one, $p \le 1$ , for every $N$ and $M$ .^✦