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.$?
 A: 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:


*

*http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.aos/1176346079

*http://wwwusers.di.uniroma1.it/~ale/Papers/master.pdf
Alternatively, I believe Hoeffding's original paper on Hoeffding(/Chernoff) bounds treated sampling without replacement.
A: 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.
