# Cardinality of intersection of a random subset with a fixed subset

How can I simply prove the following fact:

Let $A := \{1, \dots n \}$ and $B := \{1, \dots, \lfloor \frac{n}{4} \rfloor \}$. Let $d \in (0,1)$ and let $R$ be a randomly choosen (with uniform distribution) subset of cardinality $\lfloor n^{d} \rfloor$ from all subsets of that cardinality. Then for any $d' < d$:

$$\mathbb{P}(|B \cap R| > n^{d'}) \rightarrow 1,$$

when $n \rightarrow \infty.$?

• Where does this question come from? – Igor Rivin Nov 13 '13 at 1:42
• This question naturally appeared during my research about random groups. I have proved couple facts in the model where I draw only positive words. This lemma helps to generalize my results to the standard random group model. – Tomek Odrzygozdz Nov 13 '13 at 9:45

I think a reasonably quick way to do it is something like this:

Write $C = A \setminus B$. If we can show that \begin{equation} \tag{*} \Pr[|C \cap R| \geq .8 \lfloor n^d \rfloor] = o_n(1) \end{equation} then we're done because $.2 \lfloor n^d \rfloor > n^{d'}$ for sufficiently large $n$.

For each $1 \leq i \leq \lfloor n^d \rfloor$, the probability that the $i$th element of $R$ falls into $C$ is at most $.76$ (for sufficiently large $n$). If the events were independent then we'd easily have $(*)$, by Chernoff bound. But in fact, the events are negatively associated, so the Chernoff bound still holds; see:

Alternatively, I believe Hoeffding's original paper on Hoeffding(/Chernoff) bounds treated sampling without replacement.

• Thanks for posting this, it's quicker and tidier than the explicit calculations I wrote down in my answer – Michal Kotowski Nov 13 '13 at 4:49

I think it can be done by standard but very tedious calculations, at least if you do it by brute force (if anyone knows a more clever approach, I'd be happy to hear about it). I don't know if that counts as simple. It's of course possible I messed things up somewhere.

Let $m = n^{d}$, $m' = n^{d'}$, $|B| = cn$. We want to show that: $$\mathbb{P}(|B \cap R| \leq m') \to 0$$

First we do the union bound: $$\mathbb{P}(|B \cap R| \leq m') = \sum\limits_{k=0}^{m'} \mathbb{P}(|B \cap R| = k)$$ so it's enough to show that each term in the sum goes to $0$ faster than polynomially.

Fix $k$ between $0$ and $m'$. To get a random $R$, we first choose exactly $k$ elements from $B$ and then the remaining $|R|-k = m-k$ elements from the complement of $B$, which has size $(1-c)n$. So: $$\mathbb{P}(|B \cap R| = k) = \frac{1}{\binom{n}{m}}\binom{cn}{k}\binom{(1-c)n}{m-k}$$

Now you have to use Stirling approximation for each term and carefully collect exponents together. I did the calculation and it seemed to work, but I'll spare you the details unless you insist. A possibly easier way to proceed (I haven't checked it very carefully though) is to use the asymptotic formula: $$\log \binom{n}{k} \approx nH\left(\frac{k}{n}\right)$$ where $H$ is the binary entropy (valid for $n,k \gg 1$)

Taking the log of our probability gives: $$-\log \binom{n}{m} + \log\binom{cn}{k} + \log \binom{(1-c)n}{m-k} \approx -nH\left(\frac{m}{n}\right) + cnH\left(\frac{k}{cn}\right) + (1-c)n H\left(\frac{m-k}{(1-c)n}\right)$$

So if for large $n$ we have: $$-H\left(\frac{m}{n}\right) + cH\left(\frac{k}{cn}\right) + (1-c) H\left(\frac{m-k}{(1-c)n}\right) < 0$$ then our probability will go to $0$ superpolynomially quickly and we are done.

For $k \ll m$ it should be provable by checking that it holds at $k=0$, $k=m'$ and calculating the derivative - then by monotonicity we have our bound everywhere. Rough calculations show this should hold, but you need to check it yourself.