Let $m$ be a measure. We assume that there exists a constant $C > 0$ such that inequality (3) $$\int e ^ { \lambda f ( x ) } m ( x ) d x \leqslant \exp \left( \lambda \int f ( x ) m ( x ) d x + \frac { C \lambda ^ { 2 } } { 4 } \right)$$ applies to all $f \in \mathscr{C}_b^1$ with $|f'(x)| \leq 1$. Show that inequality (3) applies to the function defined by $f ( x ) = x$. You may use the sequence of functions defined by $f _ { n } ( x ) = n \arctan \left( \frac { x } { n } \right)$.

Let $m$ be a measure. We assume that there exists a constant $C > 0$ such that for $\lambda \geq 0$, $$\int e ^ { \lambda f ( x ) } m ( x ) d x \leqslant \exp \left( \lambda \int f ( x ) m ( x ) d x + \frac { C \lambda ^ { 2 } } { 4 } \right) \tag{3}$$ applies (in particular to $f(x) = x$).
13a. Let $M = \int x m ( x ) d x$ and $a \geqslant M$. Show that $$\int _ { a } ^ { + \infty } m ( x ) d x \leqslant \exp \left( - \frac { ( a - M ) ^ { 2 } } { C } \right)$$
13b. Conclude that for all $\alpha < \frac { 1 } { C }$, the function $x \mapsto e ^ { \alpha x ^ { 2 } } m ( x )$ is integrable on $\mathbb { R }$.

We recall that $\mu ( x ) = \frac { 1 } { \sqrt { \pi } } e ^ { - x ^ { 2 } }$ is a measure, and that for $A \in \operatorname{Int}$, $\mu(A) = \int \mathbb{1}_A(x) \mu(x) dx$. We denote $d(x, A) = \inf\{|x - y| : y \in A\}$. Let $A \subset \mathbb { R }$.
15a. Show that for all $x , y \in \mathbb { R }$, we have $$\exp \left( \frac { 1 } { 2 } d ( x , A ) ^ { 2 } - x ^ { 2 } \right) \mathbb { 1 } _ { A } ( y ) \exp \left( - y ^ { 2 } \right) \leqslant \exp \left( - \frac { ( x + y ) ^ { 2 } } { 2 } \right)$$
15b. We assume that $A \in \operatorname { Int }$ and that $\mu ( A ) > 0$. Deduce that $$\int \exp \left( \frac { 1 } { 2 } d ( x , A ) ^ { 2 } \right) \mu ( x ) d x \leqslant \frac { 1 } { \mu ( A ) }$$

We recall that $\mu ( x ) = \frac { 1 } { \sqrt { \pi } } e ^ { - x ^ { 2 } }$ is a measure, and that for $A \in \operatorname{Int}$, $\mu(A) = \int \mathbb{1}_A(x) \mu(x) dx$. Let $A \in \operatorname{Int}$. For $t \geqslant 0$, we define the set $A _ { t } = \{ x \in \mathbb { R } : d ( x , A ) \leqslant t \}$.
16a. Show that $A _ { t } \in \operatorname { Int }$ for all $t \geqslant 0$.
16b. We further assume that $\mu ( A ) > 0$. Show that for all $t \geqslant 0$, we have $$1 - \mu \left( A _ { t } \right) \leqslant \frac { e ^ { - t ^ { 2 } / 2 } } { \mu ( A ) }$$

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}$$ Let $\varphi(\lambda) = \ln\left(\mathbb{E}\left[e^{\lambda U_{1}}\right]\right)$.
Let $t \in \mathbb{R}$. Show that for all $\lambda > 0$, we have the inequality $$\mathbb{P}\left(S_{k} \geqslant t\right) \leqslant \exp(k\varphi(\lambda) - \lambda t).$$

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).$$

We introduce a uniformly distributed random variable $C : \Omega \rightarrow \mathcal{M}_{n}(\{-1,1\})$. For $\omega \in \Omega$, we denote by $C_{i,j}(\omega)$ the coefficients of the matrix $C(\omega)$.
Show that for all $t \geqslant 0$, we have $$\mathbb{P}\left(M(C) \geqslant t n^{3/2}\right) \leqslant \exp\left(-\left(\frac{t^{2}}{2} - 2\ln 2\right)n\right).$$

We recall the notation $\underline{M}(n) = \min\left\{M(A) \mid A \in \mathcal{M}_{n}(\{-1,1\})\right\}$. Show that for all $n \geqslant 1$, we have $$\underline{M}(n) \leqslant 2\sqrt{\ln 2}\, n^{3/2}.$$
Hint: one may begin by showing that for all $\varepsilon > 0$, there exists a matrix $A$ in $\mathcal{M}_{n}(\{-1,1\})$ such that $$M(A) \leqslant (2\sqrt{\ln 2} + \varepsilon)\, n^{3/2}.$$

We fix $A \in \mathcal{M}_{n}(\{-1,1\})$ and denote $$m(A) := \min(S(A) \cap \mathbb{N}).$$
By drawing inspiration from the previous question and the methods developed in Parts II and III, show that we also have $$m(A) \leqslant \sqrt{2n \ln(2n)}.$$

Let $X : \Omega \rightarrow \mathbb{R}$ be a real-valued random variable. We assume that there exist two strictly positive reals $a$ and $b$ such that, for all non-negative reals $t$,
$$\mathbb{P}(|X| \geqslant t) \leqslant a \exp(-bt^{2})$$
Let $\delta$ be a real such that $0 \leqslant |\delta| \leqslant \sqrt{\frac{a}{b}}$. Justify that, for all reals $t$,
$$\mathbb{P}(|X + \delta| \geqslant t) \leqslant \mathbb{P}(|X| \geqslant t - |\delta|)$$

Let $X : \Omega \rightarrow \mathbb{R}$ be a real-valued random variable. We assume that there exist two strictly positive reals $a$ and $b$ such that, for all non-negative reals $t$,
$$\mathbb{P}(|X| \geqslant t) \leqslant a \exp(-bt^{2})$$
Let $\delta$ be a real such that $0 \leqslant |\delta| \leqslant \sqrt{\frac{a}{b}}$. Deduce that for all reals $t$ such that $t \geqslant |\delta|$, we have
$$\mathbb{P}(|X + \delta| \geqslant t) \leqslant a \exp(a) \exp\left(-\frac{1}{2}bt^{2}\right)$$

Let $X : \Omega \rightarrow \mathbb{R}$ be a real-valued random variable. We assume that there exist two strictly positive reals $a$ and $b$ such that, for all non-negative reals $t$,
$$\mathbb{P}(|X| \geqslant t) \leqslant a \exp(-bt^{2})$$
Let $\delta$ be a real such that $0 \leqslant |\delta| \leqslant \sqrt{\frac{a}{b}}$. Justify that the inequality
$$\mathbb{P}(|X + \delta| \geqslant t) \leqslant a \exp(a) \exp\left(-\frac{1}{2}bt^{2}\right)$$
remains valid if $0 \leqslant t < |\delta|$.

Let $E$ be a Euclidean space of dimension $n \geqslant 1$ equipped with an orthonormal basis $(e_{1}, \ldots, e_{n})$. Let $\varepsilon_{1}, \ldots, \varepsilon_{n} : \Omega \rightarrow \{-1, 1\}$ be Rademacher random variables that are independent of each other. We set $X = \sum_{i=1}^{n} \varepsilon_{i} e_{i}$. The objective of this part is to show, for any non-empty closed convex set $C$ of $E$,
$$\mathbb{P}(X \in C) \cdot \mathbb{E}\left(\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right) \leqslant 1 \tag{II.1}$$
Handle the case where $C$ is a closed convex set of $E$ that does not meet $X(\Omega)$.

Let $E$ be a Euclidean space of dimension $n \geqslant 1$ equipped with an orthonormal basis $(e_{1}, \ldots, e_{n})$. Let $\varepsilon_{1}, \ldots, \varepsilon_{n} : \Omega \rightarrow \{-1, 1\}$ be Rademacher random variables that are independent of each other. We set $X = \sum_{i=1}^{n} \varepsilon_{i} e_{i}$. We assume that $C$ is a closed convex set of $E$ that meets $X(\Omega)$ in a single vector $u$. Justify that $d(X, C) \leqslant d(X, u)$ and deduce inequality
$$\mathbb{P}(X \in C) \cdot \mathbb{E}\left(\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right) \leqslant 1 \tag{II.1}$$
in this case.

Let $E$ be a Euclidean space of dimension $n \geqslant 1$ equipped with an orthonormal basis $(e_{1}, \ldots, e_{n})$. Let $\varepsilon_{1}, \ldots, \varepsilon_{n} : \Omega \rightarrow \{-1, 1\}$ be Rademacher random variables that are independent of each other. We set $X = \sum_{i=1}^{n} \varepsilon_{i} e_{i}$. We assume that $C$ is a closed convex set of $E$ such that $C \cap X(\Omega)$ contains at least two elements. We propose to prove inequality
$$\mathbb{P}(X \in C) \cdot \mathbb{E}\left(\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right) \leqslant 1 \tag{II.1}$$
by induction on the dimension $n$ of $E$. Handle the case $n = 1$.

We denote
$$p_{+} = \mathbb{P}(X' \in C_{+1}) \quad \text{and} \quad p_{-} = \mathbb{P}(X' \in C_{-1})$$
We will assume, without loss of generality, that $p_{+} \geqslant p_{-}$. Using the induction hypothesis, justify that
$$\mathbb{E}\left(\left.\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right\rvert \, \varepsilon_{n} = 1\right) \leqslant \frac{1}{p_{+}}$$

Complete the proof of inequality
$$\mathbb{P}(X \in C) \cdot \mathbb{E}\left(\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right) \leqslant 1 \tag{II.1}$$

Deduce Talagrand's inequality: For every non-empty closed convex set $C$ of $E$ and for every strictly positive real number $t$
$$\mathbb{P}(X \in C) \cdot \mathbb{P}(d(X, C) \geqslant t) \leqslant \exp\left(-\frac{t^{2}}{8}\right)$$

We consider the space $E = \mathcal{M}_{k,d}(\mathbb{R})$ equipped with the inner product defined by
$$\forall (A, B) \in E^{2}, \quad \langle A \mid B \rangle = \operatorname{tr}\left(A^{\top} \cdot B\right)$$
We denote by $\|\cdot\|_{F}$ the associated Euclidean norm. We fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define
$$g : \left\lvert \, \begin{aligned} & \mathcal{M}_{k,d}(\mathbb{R}) \rightarrow \mathbb{R} \\ & M \mapsto \|M \cdot u\| \end{aligned} \right.$$
Let $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ be a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $C = \left\{M \in \mathcal{M}_{k,d}(\mathbb{R}) \mid g(M) \leqslant r\right\}$. Deduce that
$$\mathbb{P}(g(X) \leqslant r) \cdot \mathbb{P}(g(X) \geqslant r + t) \leqslant \exp\left(-\frac{1}{8} t^{2}\right)$$

We consider the space $E = \mathcal{M}_{k,d}(\mathbb{R})$ equipped with the inner product defined by
$$\forall (A, B) \in E^{2}, \quad \langle A \mid B \rangle = \operatorname{tr}\left(A^{\top} \cdot B\right)$$
We fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define $g(M) = \|M \cdot u\|$. Let $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ be a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Deduce from the above that, for every strictly positive real number $t$
$$\mathbb{P}(|g(X) - m| \geqslant t) \leqslant 4 \exp\left(-\frac{1}{8} t^{2}\right)$$
where $m$ is a median of $g(X)$.

We fix once and for all an integer $n$ which should be considered as being very large. For each pair $(x,y) \in \{0,1\}^n$ such that $x \neq y$, we fix an integer $j_n(x,y)$ whose existence is proved in question 17c. We say that $x$ is better than $y$ given $E^1, E^2, \ldots, E^T$ if $$\left|\frac{1}{T}\sum_{i=1}^T E^i_{j_n(x,y)} - \mathbb{E}\left[O_{j_n(x,y)}(x)\right]\right| < \left|\frac{1}{T}\sum_{i=1}^T E^i_{j_n(x,y)} - \mathbb{E}\left[O_{j_n(x,y)}(y)\right]\right|$$ We set $R_{n,T}(E^1, E^2, \ldots, E^T) = x$ if for all $y \neq x$, $x$ is better than $y$. If we cannot find such an $x$ we set $R_{n,T}(E^1, E^2, \ldots, E^T) = (0,0,\ldots,0)$.
Prove that if $T_n \geq e^{3\ln(n)n^{1/3}}$ then for all $x \in \{0,1\}^n$ and any sequence $$O^1(x), O^2(x), \ldots, O^{T_n}(x)$$ of $T_n$ random variables taking values in $\{0,1\}^n$ mutually independent with the same distribution as $O(x)$, we have $$\max_{x \in \{0,1\}^n} \mathbb{P}\left(R_{n,T_n}\left(O^1(x), O^2(x), \ldots, O^{T_n}(x)\right) \neq x\right) \leq u_n$$ where $(u_n)_{n \geq 1}$ is a sequence tending to 0 as $n$ tends to infinity.
Hint. One may start by writing, justifying it, that $$\mathbb{P}\left(R_{n,T}\left(O^1(x), O^2(x), \ldots, O^T(x)\right) \neq x\right) \leq \sum_{y \in \{0,1\}^n, y \neq x} \mathbb{P}\left(x \text{ is not better than } y \text{ given } O^1(x), O^2(x), \ldots, O^T(x)\right)$$

We define, for all $x \in \mathbb{R}$, $\lambda^*(x) = \sup_{t \geqslant 0}(tx - \lambda(t))$. We admit that the convergence of the sequence of functions $\left(t \mapsto \frac{\ln\left(E\left(\mathrm{e}^{tS_n}\right)\right)}{n}\right)_{n \in \mathbb{N}^*}$ towards $t \mapsto \ln(\gamma(t))$ is uniform on $\mathbb{R}^+$. Let $\varepsilon > 0$. Show that there exists a rank $n_0 \in \mathbb{N}^*$ such that, for all $t \in \mathbb{R}^+$ and for all $n \in \mathbb{N}^*$, $$n \geqslant n_0 \Longrightarrow \ln\left(E\left(\mathrm{e}^{tS_n}\right)\right) \leqslant n(\lambda(t) + \varepsilon).$$

We define, for all $x \in \mathbb{R}$, $\lambda^*(x) = \sup_{t \geqslant 0}(tx - \lambda(t))$. Let $\varepsilon > 0$ and $n_0$ as in Q35. Using Markov's inequality applied to the random variable $e^{tS_n}$, show that for $a > 1$, $n \geqslant n_0$ and $t \geqslant 0$, $$P\left(S_n \geqslant nam\right) \leqslant \mathrm{e}^{-ntam} \mathrm{e}^{n(\lambda(t) + \varepsilon)}.$$

We define, for all $x \in \mathbb{R}$, $\lambda^*(x) = \sup_{t \geqslant 0}(tx - \lambda(t))$. Let $\varepsilon > 0$ and $n_0$ as in Q35. Deduce that for $n \geqslant n_0$, $$P\left(S_n \geqslant nam\right) \leqslant \mathrm{e}^{-n\left(\lambda^*(am) - \varepsilon\right)}.$$

Give a concrete meaning to $m = \lim_{n \rightarrow +\infty} \frac{1}{n} E(S_n)$ in relation to the industrial process studied and interpret the inequality $P\left(S_n \geqslant nam\right) \leqslant \mathrm{e}^{-n(\lambda^*(am) - \varepsilon)}$. One may establish an intuitive link with the law of large numbers.