Error in estimating the size of a set?

Question

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)

Answer 1

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}$

where

$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}}$