Convergence in Distribution for Subset Counts Between Random Sets

Abstract

Erdős posed the problem of how many random subsets need to be chosen from a set of $n$ elements, each element appearing in each subset with probability $p=1/2$, in order that at least one subset is contained in another. Rényi answered this question, but could not determine the limiting probability distribution for the number of subset counts because the higher moments diverge to infinity.

The model considered by Rényi with $p$ arbitrary is denoted by ${\cal P}(m,n,p)$, where $m$ is the number of random subsets chosen. We give a necessary and sufficient condition on $p(n)$ and $m(n)$ for subset counts to be asymptotically Poisson and find rates of convergence using Stein's method. We discuss how Poisson limits can be shown for other statistics of ${\cal P}(m,n,p)$.