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