Consider a family $F$ of subsets of a probability space $\Omega$. Assume that $F$ has bounded VC dimension and that the measure of each subset in $F$ is at least $\epsilon$.

Drawing $n$ iid points from $\Omega$, can we find a good lower bound on the probability that all subsets in $F$ contain at least a point?

I tried using the uniform CLT (VC inequality), but it seems suboptimal in the regime where the expected number of points in each subset is small.


The worst-case scenario is when elements of $F$ are disjoint. Let $k$ be the number of elements of $F$. Then, using this answer with Stirling numbers, the probability that all those elements are occupied is

$$\sum_i {\binom ni} (k\epsilon)^i (1-k\epsilon)^{n-i} \left\{ \begin{array}& i \\ k \end{array} \right\} k!/k^i$$

$$=k!\sum_i {\binom ni} \left\{ \begin{array}& i \\ k \end{array} \right\} \epsilon^i (1-k\epsilon)^{n-i} $$

If $\epsilon$ is small in the sense that $n\epsilon<k$, then it may be enough to use the lower bound from the $i=k$ term: $$\epsilon^k (1-k\epsilon)^{n-k}n! /(n-k)! $$


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.