1
$\begingroup$

I got stuck solving exercise 11.3 from the book Concentration of Measure for the Analysis of Randomized Algorithms. The setting is:

Consider again the situation of Section $7.2,$ the number of non-empty bins when $m$ balls are thrown independently and uniformly at random into $n$ bins.

It is shown that $\operatorname{Pr}[|f-\mathrm{M}[f]|>t] \leq 2 e^{-t^{2} / n}$.

Then I want to show

Exercise $11.3 .$ Check that in this case, concentration around $\mathrm{M}[f]$ can be used to deduce similar concentration around $\mathrm{E}[f]$

$M[X]$ is the median of $X$. How do I do this? I do not know how to start.

$\endgroup$
1
$\begingroup$

The tail bound shows that $f-M[f]$ is subgaussian with subgaussian norm $O(\sqrt{n})$. Centering a subgaussian random variable loses the subgaussian norm by a factor of $2$. The centered version of $f-M[f]$ is $$ (f - M[f]) - \mathbb{E}(f-M[f]) = f - \mathbb{E}f $$ hence $f-\mathbb{E}f$ is subgaussian with subgaussian norm $O(\sqrt{n})$ and thus $$ \Pr\{ |f-\mathbb{E} f| > t\} \leq 2e^{-ct^2/n} $$ for some absolute constant $c$.

Alternatively, you can just plainly integrate the tail bound to show that $|\mathbb{E}f - M[f]| = O(\sqrt n)$, this gives you a similar concentration around $\mathbb{E}f$, too.

| cite | improve this answer | |
$\endgroup$

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.