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

  • $\begingroup$ Where does this question come from? $\endgroup$ – Igor Rivin Nov 13 '13 at 1:42
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Thanks for posting this, it's quicker and tidier than the explicit calculations I wrote down in my answer $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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