Manipulating Concentration Inequalities

66 Views Asked by At

I have been studying concentration inequalities for sums of random variables recently, specifically Bernstein's inequality in several forms, and have a question regarding the manipulation of such expressions.

Assume we are given the following form of Bernstein's inequality (see for example Vershynin's "High-Dimensional Probability" Corollary 2.8.3): Let $X_1, \dots, X_N$ be independent, mean zero, sub-exponential random variables. Then, for every $t \geq 0$, we have

$$ \mathbb{P}(|\frac{1}{N} \sum_{i=1}^N X_i | \geq t) \leq 2 \exp{(-c \min \{ \frac{t^2}{K^2}, \frac{t}{K} \} N )} $$

where $ K = \max_i \|X_i\|_{\phi_2}$ and $c > 0$ is an absolute constant.

Now, given this, can we deduce for $t \geq 1$

$$ \mathbb{P}(|\frac{1}{N} \sum_{i=1}^N X_i | \geq tK ) \leq 2 \exp{(-c t N )} ? $$

I don't quite see why one would be able to simply pull the constant $K$ from the right side into the probability...

1

There are 1 best solutions below

0
On BEST ANSWER

Apply the first inequality to $t = uK$, for $u \geq 1$. You get $$\begin{align*} \mathbb{P}\left\{\left|\frac{1}{N} \sum_{i=1}^N X_i \right| \geq uK\right\} &\leq 2 \exp{\left(-c \min \{ \frac{u^2K^2}{K^2}, \frac{uK}{K} \} N \right)}\\ &=2 \exp{\left(-c \min \{ u, 1 \} u N \right)}\\ &=2 \exp{\left(-c u N \right)} \end{align*} $$ the last equality since $u\geq 1$.