# Can we estimate the size of a subset X of a set A, by randomly sampling subsets of A?

Let $A$ be a finite set and suppose we want to compute the size of some subset $X$.

Motivation: If we can generate elements $x$ of $A$ uniformly at random, then we can estimate the size of $A$ by random sampling. That is, we take $n$ random samples from $A$, if $m$ of them belong to $X$, then $|X|/|A| \approx m/n$. Unfortunately, for what I do, usually $|A|$ is massive and $|X|$ (while massive) is quite small with respect to $|A|$. So if I attempt to perform the above estimation, I'm likely to get $m=0$, which, while not useless, is not really all that satisfying.

So, I have an idea that I'm hoping will speed up this process. Instead of throwing darts at a massive dart board, why don't I throw balls? That is, instead of sampling elements $x \in A$, we sample subsets of $A$. Surely I should be able to infer something about the density of $X$ in $A$ from this experiment.

Suppose $A$ is equipped with a metric $d(x,y)$ (I have in mind the Hamming distance). For any $y \in A$ let $Y(y)=\{x \in A:d(x,y) \leq k\}$ be the closed ball of radius $k$ in $A$ centered at $t$. Since we can sample elements $x \in A$ uniformly at random, we can sample $k$-balls $Y_k(t)$ uniformly at random.

Suppose (a) every $x \in A$ belong to exactly the same number of $k$-balls and (b) every $k$-ball has the same size $r$.

Now suppose I generate $k$-balls $Y_1,Y_2,\ldots,Y_n$ uniformly at random and suppose $m=\sum_{i=1}^n |Y_i \cap X|$. It seems we can estimate $|A|$ in a similar way, that is $|X|/|A| \approx \frac{m}{rn}$.

So my questions are:

Am I correct in that we can approximate $|X|$ this way? If so, I doubt I'm the first to think of this, so is there a name for this method?

I did actually test this on some sets, and it seems to match what I claim.

Are there any drawbacks to this approach? (e.g. is it less accurate? do I need more samples?)

• I think you made a slight mistake in the second paragraph: $|X|/|A| \approx m/n$. Otherwise, what you are doing is basically reinventing Monte Carlo integration, well, the subset version I have not encountered yet, but I'd not be surprised if it's done already. – Raskolnikov Dec 1 '10 at 12:12
• Thanks, yes that was a mistake (in fact, there was a similar one later on also). – Douglas S. Stones Dec 1 '10 at 12:26

OK, try reading the wikipedia page for Monte Carlo integration. You'll see they mention a stratified version. Stratification is the technical term in statistics for what you attempt: subdividing in subsets (subsamples). I guess the references can help you further.

For any subset $Y$ of $A$, let $\pi(Y)$ be the probability you will select it in your sampling. You have described a random variable

$$f(Y) = |Y \cap X|.$$

The total of $f$ in the population of subsets of $A$ is

$$\tau(X) = \sum_{Y \subset A}|Y \cap X| = 2^{|A|-1}|X|.$$

From a sample (with replacement) of subsets of $A$, say $Y_1, Y_2, \ldots, Y_m$, the Hansen-Hurwitz Estimator obtains an unbiased estimate of this total as

$$\hat{f}_\pi = \sum_{i=1}^{m} \frac{|Y_i \cap X|}{\pi(Y_i)} .$$

Dividing this by $2^{|A|-1}|A|$ therefore estimates $|X|/|A|$. The variance of $\hat{f}_\pi$ is

$$\text{Var}(\hat{f}_\pi) = \frac{1}{m} \sum_{Y \subset A} \pi(Y) \left( \frac{|Y \cap X|}{\pi(Y)} - 2^{|A|-1}|X| \right)^2\text{.}$$

Dividing this by $2^{2(|A|-1)}|A|^2$ yields the sampling variance of $|X|/|A|$. Given $A$, $X$, and a proposed sampling procedure (which specifies $\pi(Y)$ for all $Y \subset A$), choose a value of $m$ (the sample size) for which the estimation variance becomes acceptably small.

• great, I guess this is the answer ! I did not know Hansen-Hurwitz... – robin girard Dec 1 '10 at 16:43

I assume your measure is finite. WLOG it can be a probability.

The first procedure you mention is the good old empirical probability estimate:

$\hat{P}(Y\in X)= | \{ x_i \in X\} | /n$

(there montecarlo estimate of an inetgral is a good interpretation also). In high dimension it does not work since $\{x_i\in X\}$ is likely to be empty for typical A. As you have noticed, you need regularization. How sophisticate regularisation you need is related to the dimension of your space.

An idea is to enlarge $X$ or even give a weight to $x_i$ that is not in $X$ according to its distance to $X$, this is what I ould call kernel probability estimate (by analogy with kernel density estimate):

$\hat{P}(Y\in X)= 1/(c(k) n)\sum_{i} K(d(x_i,X)/k)$

where $K$ is a kernel that integrates to $1$ (in your case it can be $K(x)=1\{x\leq 1\}$ but gaussian kernel has good properties) and $c(k)$ a well chosen normalization constant (i.e such that $\hat{P}(Y\in A)=1$).