4 Concentration inequalities
A real valued random variable \(X\) is \(\sigma ^2\)-sub-Gaussian if for any \(\lambda \in \mathbb {R}\),
\begin{align*} \mathbb {E}\left[e^{\lambda X}\right] & \le e^{\frac{\lambda ^2 \sigma ^2}{2}} \: . \end{align*}
If \(X\) is \(\sigma _1^2\)-sub-Gaussian and \(Y\) is \(\sigma _2^2\)-sub-Gaussian, and \(X\) and \(Y\) are independent, then \(X + Y\) is \((\sigma _1^2 + \sigma _2^2)\)-sub-Gaussian.
Proof
For \(X\) a \(\sigma ^2\)-sub-Gaussian random variable, for any \(t \ge 0\),
\begin{align*} \mathbb {P}(X \ge t) & \le \exp \left(- \frac{t^2}{2 \sigma ^2}\right) \: . \end{align*}
Proof
Let \(X_1, \ldots , X_n\) be independent random variables such that \(X_i\) is \(\sigma _i^2\)-sub-Gaussian for \(i \in [n]\). Then for any \(t \ge 0\),
\begin{align*} \mathbb {P}\left(\sum _{i=1}^n X_i \ge t\right) & \le \exp \left(- \frac{t^2}{2 \sum _{i=1}^n \sigma _i^2}\right) \: . \end{align*}
Proof