$N$ being a non-zero natural integer, $\left( X _ { j } ^ { i } \right) _ { 1 \leqslant i \leqslant N , 1 \leqslant j \leqslant n }$ is a family of $n \times N$ mutually independent real random variables with the same distribution $\mathcal { R }$. For every $i \in \llbracket 1 , N \rrbracket$, we set $X ^ { i } = \frac { 1 } { \sqrt { n } } \left( X _ { 1 } ^ { i } , \ldots , X _ { n } ^ { i } \right) ^ { \top }$.
Deduce that, for every natural integer $N$ less than or equal to $\exp \left( \frac { \varepsilon ^ { 2 } n } { 4 } \right)$, there exists a family of $N$ unit vectors of $\mathbb { R } ^ { n }$ whose coherence parameter is bounded by $\varepsilon$.

Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of mutually independent random variables satisfying $\mathbb{P}(X_n = -1) = \mathbb{P}(X_n = 1) = \frac{1}{2}$ for all $n \in \mathbb{N}$, and let $(a_n)_{n \in \mathbb{N}}$ be a real sequence such that $\sum a_n^2$ converges. Let $S_N = \sum_{n=0}^N X_n a_n$ and let $A_j = \{|S_{\phi(j+1)} - S_{\phi(j)}| > 2^{-j}\}$. Using the sequence $(\phi(j))_{j \in \mathbb{N}}$ satisfying $\sum_{n > \phi(j)}^{+\infty} a_n^2 \leqslant \frac{1}{8^j}$, deduce the bound $\mathbb{P}(A_j) \leqslant 2^{-j}$.

Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of mutually independent random variables satisfying $\mathbb{P}(X_n = -1) = \mathbb{P}(X_n = 1) = \frac{1}{2}$ for all $n \in \mathbb{N}$, and let $(a_n)_{n \in \mathbb{N}}$ be a real sequence such that the series $\sum a_n^2$ converges. For all $N \in \mathbb{N}$, denote $S_N = \sum_{n=0}^N X_n a_n$. Let $(\phi(j))_{j \in \mathbb{N}}$ be a strictly increasing sequence of natural integers satisfying $\sum_{n > \phi(j)}^{+\infty} a_n^2 \leqslant \frac{1}{8^j}$ for all $j \in \mathbb{N}$, and let $A_j = \left\{\left|S_{\phi(j+1)} - S_{\phi(j)}\right| > 2^{-j}\right\}$. Deduce from the two previous questions the bound $\mathbb{P}(A_j) \leqslant 2^{-j}$.

Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of mutually independent random variables satisfying $\mathbb{P}(X_n = -1) = \mathbb{P}(X_n = 1) = \frac{1}{2}$ for all $n \in \mathbb{N}$, and let $(a_n)_{n \in \mathbb{N}}$ be a real sequence such that the series $\sum a_n^2$ converges. For all $N \in \mathbb{N}$, denote $S_N = \sum_{n=0}^N X_n a_n$. Let $(\phi(j))_{j \in \mathbb{N}}$ be a strictly increasing sequence of natural integers. Define $$A_j = \left\{\left|S_{\phi(j+1)} - S_{\phi(j)}\right| > 2^{-j}\right\}, \quad B_j = \left\{\max_{\phi(j)+1 \leqslant n \leqslant \phi(j+1)} \left|S_n - S_{\phi(j)}\right| > 2^{-j}\right\}.$$ Deduce that $\mathbb{P}(B_j) \leqslant 2\mathbb{P}(A_j)$.

Let $E$ be a countably infinite subset of $\mathbb{R}$. Let $(\Omega, \mathscr{A}, P)$ be a probability space. Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of random variables defined on $(\Omega, \mathscr{A}, P)$, taking values in $E$. We assume that for all $\omega \in \Omega$, the sequence $(X_n(\omega))_{n \in \mathbb{N}}$ is stationary and converges to $X(\omega)$. Let $L$ be the random variable defined as in 15a.
Show that $P(X_n \neq X) \leqslant P(L \geqslant n)$ for all integer $n$ in $\mathbb{N}$.

Let $E$ be an infinite countable subset of $\mathbb{R}$. Let $(\Omega, \mathscr{A}, P)$ be a probability space. Let $(X_n)_{n \in \mathbb{N}}$ be a sequence of random variables defined on $(\Omega, \mathscr{A}, P)$, taking values in $E$, such that for all $\omega \in \Omega$, the sequence $(X_n(\omega))_{n \in \mathbb{N}}$ is stationary and converges to $X(\omega)$. Let $L$ be the random variable defined in 15a. Show that $\mathbf{P}(X_n \neq X) \leqslant \mathbf{P}(L \geqslant n)$ for all integer $n$ in $\mathbb{N}$.

Let $x > 0$. By writing that $\varphi ( t ) \leqslant \frac { t } { x } \varphi ( t )$ for all $t \geqslant x$, show that $$\int _ { x } ^ { + \infty } \varphi ( t ) \mathrm { d } t \leqslant \frac { \varphi ( x ) } { x }$$ where $\varphi ( x ) = \frac { 1 } { \sqrt { 2 \pi } } \mathrm { e } ^ { - x ^ { 2 } / 2 }$.

Let $x > 0$. Using the study of a well-chosen function, show that $$\frac { x } { x ^ { 2 } + 1 } \varphi ( x ) \leqslant \int _ { x } ^ { + \infty } \varphi ( t ) \mathrm { d } t$$ where $\varphi ( x ) = \frac { 1 } { \sqrt { 2 \pi } } \mathrm { e } ^ { - x ^ { 2 } / 2 }$.

In this subsection, $n$ is a non-zero natural number and $Z _ { 1 } , \ldots , Z _ { n }$ are discrete random variables independent on a probability space $(\Omega , \mathcal { A } , \mathbb { P })$. For all $p \in \llbracket 1 , n \rrbracket$, we denote $R _ { p } = \sum _ { i = 1 } ^ { p } Z _ { i }$. Let $A$ denote the event $\left\{ \max _ { 1 \leqslant p \leqslant n } \left| R _ { p } \right| \geqslant 3 x \right\}$.
Deduce that $$\mathbb { P } ( A ) \leqslant \mathbb { P } \left( \left\{ \left| R _ { n } \right| \geqslant x \right\} \right) + \max _ { 1 \leqslant p \leqslant n } \mathbb { P } \left( \left\{ \left| R _ { n } - R _ { p } \right| > 2 x \right\} \right) .$$

In this subsection, $n$ is a non-zero natural number and $Z _ { 1 } , \ldots , Z _ { n }$ are discrete random variables independent on a probability space $(\Omega , \mathcal { A } , \mathbb { P })$. For all $p \in \llbracket 1 , n \rrbracket$, we denote $R _ { p } = \sum _ { i = 1 } ^ { p } Z _ { i }$.
Conclude that $$\forall x > 0 , \quad \mathbb { P } \left( \left\{ \max _ { 1 \leqslant p \leqslant n } \left| R _ { p } \right| \geqslant 3 x \right\} \right) \leqslant 3 \max _ { 1 \leqslant p \leqslant n } \mathbb { P } \left( \left\{ \left| R _ { p } \right| \geqslant x \right\} \right) .$$

Let $\left( X _ { i } \right) _ { i \in [ 1 , n ] }$ be a sequence of independent random variables all following a Rademacher distribution. Deduce that: for all $t \geq 0$, for all $x \geq 0$ and for all $\left( c _ { 1 } , \ldots , c _ { n } \right) \in \mathbf { R } ^ { n }$, $$\mathbf { P } \left( \exp \left( x \left| \sum _ { i = 1 } ^ { n } c _ { i } X _ { i } \right| \right) > \mathrm { e } ^ { t x } \right) \leq 2 \mathrm { e } ^ { - t x } \exp \left( \frac { x ^ { 2 } \sum _ { i = 1 } ^ { n } c _ { i } ^ { 2 } } { 2 } \right) .$$ You may use Markov's inequality.

Let $\left( X _ { i } \right) _ { i \in [ 1 , n ] }$ be a sequence of independent random variables all following a Rademacher distribution. Show that: for all $t \geq 0$ and for all non-zero $\left( c _ { 1 } , \ldots , c _ { n } \right) \in \mathbf { R } ^ { n }$, $$\mathbf { P } \left( \left| \sum _ { i = 1 } ^ { n } c _ { i } X _ { i } \right| > t \right) \leq 2 \exp \left( - \frac { t ^ { 2 } } { 2 \sum _ { i = 1 } ^ { n } c _ { i } ^ { 2 } } \right) .$$