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.

  • The details are taking more time than I have right now, but you should be able to get good answers for some ranges of the parameters by looking at random sets and using concentration of measure. – Ben Barber Jun 18 '14 at 11:21
  • Note that the number of sets $B$ intersecting $A$ in exactly $j$ elements is $\binom{p_n}{j}\binom{n-p_n}{p_n-j}$. From this one can calculate what you want. The number of elements in the intersection is approximately distributed like a Poisson random variable with parameter $p_n^2/n$. – Lucia Jun 18 '14 at 15:35
  • Thank you for your comment! I don't think that there is an easy (without hypergeometric functions) expression for $\sum_{j=q_n}^{p_n}\binom{p_n}{j}\binom{n-p_n}{p_n-j}$?! How do I get an approximation for this quantity? Could you elaborate on how the Poisson distribution comes up? – whz Jun 18 '14 at 16:41
up vote 4 down vote accepted

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

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.