grandes-ecoles 2018 QII.3

grandes-ecoles · France · x-ens-maths__pc Continuous Probability Distributions and Random Variables Probability Inequality and Tail Bound Proof

Let $k$ be a strictly positive integer and $U_{1}, \ldots, U_{k}$ a sequence of $k$ random variables taking values in $\{-1,1\}$, independent and uniformly distributed. We also denote $$S_{k} = \sum_{i=1}^{k} U_{i}$$
Deduce Hoeffding's inequality for $S_{k}$: for all $t > 0$, we have $$\mathbb{P}\left(S_{k} \geqslant t\right) \leqslant \exp\left(-\frac{t^{2}}{2k}\right).$$

Let $k$ be a strictly positive integer and $U_{1}, \ldots, U_{k}$ a sequence of $k$ random variables taking values in $\{-1,1\}$, independent and uniformly distributed. We also denote
$$S_{k} = \sum_{i=1}^{k} U_{i}$$

Deduce Hoeffding's inequality for $S_{k}$: for all $t > 0$, we have
$$\mathbb{P}\left(S_{k} \geqslant t\right) \leqslant \exp\left(-\frac{t^{2}}{2k}\right).$$

Paper Questions

QI.1 QI.2 QI.3 QI.4 QI.5 QI.6 QII.1 QII.2 QII.3 QII.4 QII.5 QII.6 QIII.1 QIII.2 QIII.3 QIII.4 QIV.1 QIV.2 QIV.3 QIV.4 QV.1 QV.2