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



Cardinality of intersection of a random subset with a fixed subset
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.


