Asymptotics of the number of elements in the intersection of two growing sets

Question

Let $[n]:=\{1,\dots,n\}$ and $0\leq p_n\leq n$. Fix any subset $A_n$ of $[n]$ with $p_n$ elements. The number of subsets $B$ of $[n]$ with $p_n$ elements that are disjoint from $A$ is $\binom{n-p_n}{p_n}$ and so the number of subsets $B$ with $p_n$ elements that have a non-empty intersection with $A$ is given by $\binom{n}{p_n}-\binom{n-p_n}{p_n}$ which asymptotically behaves like $\binom{n}{p_n}$ if $\sqrt{n}\ll p_n$. Precisely: $$\lim_{n\to\infty}\frac{\binom{n}{p_n}-\binom{n-p_n}{p_n}}{\binom{n}{p_n}}=\begin{cases}1 &\text{if }\sqrt{n}\ll p_n\\ 0&\text{if }p_n\ll\sqrt{n}\\ e^{-a^2}&\text{if }\lim_{n\to\infty}\frac{p_n}{\sqrt{n}}=a\end{cases}$$ To put it differently, any two subsets of $[n]$ with $p_n$ elements typically have non-empty intersection if $p_n$ grows faster than $\sqrt{n}$.

Now, I am interested in the typical number of elements in their intersection if $p_n$ grows faster than $\sqrt{n}$. My feeling would be that this number also grows with $n$. Precisely, I believe (numerics support this) that if $q_n$ grows slower than $p_n/\sqrt{n}$ then eventually all sets $A_n$, $B_n$ with $p_n$ elements each share at least $q_n$ elements. To put it in formulas, if $A_n$ is any set with $p_n$ elements, then $$\lim_{n\to\infty }\frac{\lvert\{B_n\subset[n]~~\lvert~~\lvert B_n\lvert=p_n\text{ and }\lvert A_n\cap B_n\lvert\geq q_n\}\rvert}{\binom{n}{p_n}}=1.$$

Since there is no exact combinatorial count (only in terms of generalised hypergeometric functions) on the number of $B_n$ of a given size that share at least $q_n$ elements with some fixed sets, I would need some good lower bound on it. Has anybody seen those asymptotics worked out? Any references would be welcome.

Answer 1

To avoid subscripts, I'll write simply $p$ instead of $p_n$. We'll assume that $p$ is small compared with $n$; certainly say $3p<n$. Given $A$ of cardinality $p$, the number of sets $B$ of size $p$ intersecting $A$ in exactly $j$ elements is $$ \binom{p}{j} \binom{n-p}{p-j} \le \frac{p^j}{j!} \Big(\frac{p}{n-2p}\Big)^j \binom{n-p}{p} \le \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j \Big(\frac{n-p}{n}\Big)^p \binom{n}{p}. $$ Since $(1-x)\le e^{-x}$, the above is $$ \le \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j e^{-p^2/n} \binom{n}{p}. $$ Thus the probability that $B$ intersects $A$ in exactly $j$ elements is at most $$ \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j e^{-p^2/n}. \tag{1} $$ (In fact, in a wide range this is essentially an asymptotic, and so the number of elements in the intersection is essentially Poisson with parameter $p^2/n$.)

But we can continue with actual inequalities rather than asymptotics. Consider the probability that the size of the intersection is at most $J$ (and assume that $J\le p^2/(n-2p)$). By (1) this probability is $$ \le e^{-p^2/n} \sum_{j=0}^{J} \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j. $$ For any $\alpha >0$ the above is (since $e^{\alpha(J-j)}\ge 1$ for $j\le J$ and non-negative otherwise) $$ \le e^{-p^2/n} \sum_{j=0}^{\infty} e^{\alpha(J-j)} \frac{1}{j!} \Big(\frac{p^2}{n-2p}\Big)^j = e^{-p^2/n} \exp\Big(\alpha J + \frac{p^2}{n-2p} e^{-\alpha}\Big). $$ Choose optimally $\alpha$ such that $J=e^{-\alpha}(p^2/(n-2p))$ and so the above estimate becomes $$ \le e^{-p^2/n} \exp\Big( J \Big( 1+ \log \frac{p^2}{J(n-2p)}\Big)\Big). $$ This is a completely explicit bound, and for example shows that the probability that the intersection is at most $p^2/(e(n-2p))$ is at most $$ \exp\Big(-\frac{p^2}{n} + \frac{2}{e} \frac{p^2}{n-2p} \Big). $$ Clearly this is very small if $p^2/n$ is large, but $p$ is small compared to $n$.

Answer 2

The problem statement exactly corresponds to the definition of the hypergeometric distribution. With this key-phrase in hand, it is easy to locate an extensive literature. Start with wikipedia for basic stuff like the mean, variance, normal approximation, etc.. The book "Univariate Discrete Distributions" by Johnson, Kotz and Kemp contains a lot more. A recent lovely paper of Matthew Skala has a survey of tail inequalities.