Suppose we have a set A and a subset B. If we know |A|, then we can calculate |B| by finding the probability p that an element chosen uniformly at random from A belongs to B. Specifically |A|p=|B|.

Suppose we generate n elements of A uniformly at random and use this data to estimate p (number of elements in B divided by n) and hence estimate |B|.

How reliable is this estimate? I.e. how can we compute the error?

As a side question, is there a name for this technique? (it seems to be a mathematical version of the mark-and-recapture technique)

  • 1
    $\begingroup$ It's binomial estimation. (There is no marking or recapturing at all. which leads to hypergeometric estimation.) $\endgroup$ – whuber Sep 28 '10 at 15:11

You are estimating proportions. For concreteness, imagine that A is the population of voters and B is the set of voters who vote for a particular candidate. Thus, p would be the percentage of voters who would vote for that candidate. Let:

$\pi$ be the true percentage of people who would vote for the candidate

In other words:

$\pi = \frac{|B|}{|A|}$

Then each one of your samples is a bernoulli trial with probability $\pi$ or equivalently you can imagine that each one of your samples is a poll of potential voters asking them whether they would vote for the candidate. Thus, the MLE of $\pi$ is given by:

$p = \frac{n_B}{n}$


$n_B$ is the number of people who said they would vote for candidate or the number of elements which belong to the set B in your sample of size $n$.

The standard error for your estimate is:

$\sqrt{\frac{\pi (1-\pi)}{n}}$

The above can be approximated by using the MLE for $\pi$ i.e., by:

$\sqrt{\frac{p (1-p)}{n}}$


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.