Deduce Carleman's inequality:
$$\sum _ { n = 1 } ^ { + \infty } \left( \prod _ { k = 1 } ^ { n } a _ { k } \right) ^ { 1 / n } \leqslant \mathrm { e } \sum _ { n = 1 } ^ { + \infty } a _ { n }$$
for any sequence $\left( a _ { k } \right) _ { k \in \mathbb { N } ^ { * } }$ of strictly positive real numbers such that $\sum a _ { n }$ converges.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. We now assume that $\lim _ { n \rightarrow + \infty } \left( n ^ { \omega _ { 0 } } p _ { n } \right) = + \infty$. For $k \in \llbracket 0 , s _ { 0 } \rrbracket$, we denote: $$\Sigma _ { k } = \sum _ { \substack { \left( H , H ^ { \prime } \right) \in C _ { 0 } ^ { 2 } \\ s _ { H \cap H ^ { \prime } } = k } } \mathbf { P } \left( H \cup H ^ { \prime } \subset G \right)$$ Let $k \in \llbracket 1 , s _ { 0 } \rrbracket$; show that : $$\Sigma _ { k } \leq \sum _ { H \in \mathcal { C } _ { 0 } } \binom { s _ { 0 } } { k } \binom { n - s _ { 0 } } { s _ { 0 } - k } c _ { 0 } p _ { n } ^ { 2 a _ { 0 } } p _ { n } ^ { - \frac { k } { \omega _ { 0 } } }$$

Let $\varphi$ be the function defined by
$$\forall t \in ] - 1,1 \left[ \backslash \{ 0 \} , \quad \varphi ( t ) = ( 1 - t ) ^ { 1 - 1 / t } \right.$$
Justify that $\varphi$ is extendable by continuity at 0 and specify the value of its extension at 0. We will still denote this extension by $\varphi$.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. We now assume that $\lim _ { n \rightarrow + \infty } \left( n ^ { \omega _ { 0 } } p _ { n } \right) = + \infty$. Justify that for all natural integers $q$ and $r$ satisfying $1 \leq q \leq r$, we have : $$\binom { r } { q } r ^ { - q } \geq \frac { 1 } { q ! } \left( 1 - \frac { q - 1 } { q } \right) ^ { q }$$ and deduce that for $k \in \llbracket 1 , s _ { 0 } \rrbracket$, we have $\Sigma _ { k } = \mathrm { o} \left( \left( \mathbf { E } \left( X _ { n } ^ { 0 } \right) \right)^{ 2 } \right)$ when $n$ tends to $+ \infty$.

We define the sequence $\left( b _ { n } \right) _ { n \in \mathbb { N } }$ by
$$\left\{ \begin{array} { l } b _ { 0 } = - 1 \\ \forall n \in \mathbb { N } ^ { * } , \quad b _ { n } = - \frac { 1 } { n } \sum _ { k = 1 } ^ { n } \frac { 1 } { k + 1 } b _ { n - k } \end{array} \right.$$
Prove that, for all $n$ in $\mathbb { N } ^ { * } , \left| b _ { n } \right| \leqslant 1$. Deduce an inequality on the radius of convergence of the power series $\sum _ { k \geqslant 0 } b _ { k } t ^ { k }$.

We consider $R \in \mathrm{O}_{d}(\mathbb{R})$ with $\operatorname{det}(R) = -1$, and the notation from question 23. We set $S_{0} = (S_{ij})_{1 \leqslant i,j \leqslant d-1} \in \mathscr{M}_{d-1}(\mathbb{R})$.

• [(a)] Show that $\langle D, R \rangle = \operatorname{tr}(S_{0} R_{0}) - S_{dd}$.
• [(b)] Show that $\operatorname{tr}(S_{0} R_{0}) \leqslant \operatorname{tr}(S_{0})$.
• [(c)] Show that $\operatorname{tr}(S_{0}) + S_{dd} = \operatorname{tr}(D)$ and deduce that $\langle D, R \rangle \leqslant \operatorname{tr}(D) - 2S_{dd}$.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. We now assume that $\lim _ { n \rightarrow + \infty } \left( n ^ { \omega _ { 0 } } p _ { n } \right) = + \infty$. Show that $\lim _ { n \rightarrow + \infty } \frac { \mathbf { V } \left( X _ { n } ^ { 0 } \right) } { \left( \mathbf { E } \left( X _ { n } ^ { 0 } \right) \right) ^ { 2 } } = 0$ where $\mathbf { V } \left( X _ { n } ^ { 0 } \right)$ denotes the variance of $X _ { n } ^ { 0 }$.

Let $\varphi$ be the function defined by
$$\forall t \in ] - 1,1 \left[ \backslash \{ 0 \} , \quad \varphi ( t ) = ( 1 - t ) ^ { 1 - 1 / t } \right.$$
We define the sequence $\left( b _ { n } \right) _ { n \in \mathbb { N } }$ by
$$\left\{ \begin{array} { l } b _ { 0 } = - 1 \\ \forall n \in \mathbb { N } ^ { * } , \quad b _ { n } = - \frac { 1 } { n } \sum _ { k = 1 } ^ { n } \frac { 1 } { k + 1 } b _ { n - k } \end{array} \right.$$
Prove that, for all $t$ in $] - 1,1 \left[ , \varphi ^ { \prime } ( t ) = \varphi ( t ) \psi ( t ) \right.$, where
$$\forall t \in ] - 1,1 \left[ , \quad \psi ( t ) = - \sum _ { n = 0 } ^ { + \infty } \frac { 1 } { n + 2 } t ^ { n } \right.$$
then that, for all $n$ in $\mathbb { N } ^ { * }$,
$$\varphi ^ { ( n ) } ( 0 ) = - \sum _ { k = 0 } ^ { n - 1 } \frac { k ! } { k + 2 } \binom { n - 1 } { k } \varphi ^ { ( n - k - 1 ) } ( 0 )$$

We consider $R \in \mathrm{O}_{d}(\mathbb{R})$ with $\operatorname{det}(R) = -1$, $D = \operatorname{Diag}(\alpha_{1}, \ldots, \alpha_{d})$ with $\alpha_{i} \geqslant 0$ in decreasing order, $U = (U_{ij})_{1 \leqslant i,j \leqslant d}$, and $S_{dd}$ as defined in question 24.

• [(a)] Show that $S_{dd} = \sum_{j=1}^{d} \alpha_{j} U_{jd}^{2}$ where $U = (U_{ij})_{1 \leqslant i,j \leqslant d}$.
• [(b)] Deduce that $\langle D, R \rangle \leqslant \left(\sum_{i=1}^{d-1} \alpha_{i}\right) - \alpha_{d}$.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$, and let $$\omega _ { 0 } = \min _ { \substack { H \subset G _ { 0 } \\ a _ { H } \geq 1 } } \frac { s _ { H } } { a _ { H } }$$ Show that the sequence $\left( k ^ { - \omega _ { 0 } } \right) _ { k \geq 2 }$ is a threshold function for the property $\mathcal { P } _ { n }$ : ``contain a copy of $G_0$''.

In this part, we assume that $n \geqslant 4$. Let $u = (u_k)_{k \geqslant 0}$ be a sequence of $\mathbb{C}$ satisfying the condition $(C^\star)$: $R_u > 1$.
Suppose that for all $k \in \mathbb{N}$, $u_k = \mathbb{P}(X = k)$ where $X$ is a random variable taking values in $\mathbb{N}$.
(a) Suppose that $X$ follows a binomial distribution with parameters $(N, p)$. Verify that $u$ satisfies condition $(C^\star)$ and find a simple expression for $u(A)$ for all $A \in \mathbb{M}_n(u)$.
(b) Suppose that $X$ follows a geometric distribution with parameter $p \in ]0,1[$. Verify that $u$ satisfies condition $(C^\star)$ and show that $$u(A) = p\left(I_n - (1-p)A\right)^{-1} A$$ for every diagonalizable matrix $A \in \mathbb{M}_n(u)$.

Give the value of $\delta(\boldsymbol{x}, \boldsymbol{y})$ as a function of $V_{n}(\boldsymbol{x})$, $V_{n}(\boldsymbol{y})$ and the singular values of $Z(\boldsymbol{x}, \boldsymbol{y})$ in the case where $\operatorname{det}(Z(\boldsymbol{x}, \boldsymbol{y})) < 0$.

Recover the result of question 16 and determine a threshold function for the property ``containing a copy of the star with $d$ branches'' with $d$ a fixed integer greater than 1.

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients and we identify $\mathbb { C } ^ { d }$ with the space of column vectors of size $d$.
For a vector $x = \left( x _ { 1 } , \ldots , x _ { d } \right) \in \mathbb { C } ^ { d }$, we define $\| x \| _ { \infty } = \max _ { 1 \leqslant i \leqslant d } \left| x _ { i } \right|$ and $\| x \| _ { 1 } = \sum _ { i = 1 } ^ { d } \left| x _ { i } \right|$.
Let $A \in \mathrm { M } _ { d } ( \mathbb { C } )$. Determine a necessary and sufficient condition on $A$ for the map $x \mapsto \| A x \| _ { \infty }$ to define a norm on $\mathbb { C } ^ { d }$.

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients and we identify $\mathbb { C } ^ { d }$ with the space of column vectors of size $d$.
For a vector $x = \left( x _ { 1 } , \ldots , x _ { d } \right) \in \mathbb { C } ^ { d }$, we define $\| x \| _ { \infty } = \max _ { 1 \leqslant i \leqslant d } \left| x _ { i } \right|$ and $\| x \| _ { 1 } = \sum _ { i = 1 } ^ { d } \left| x _ { i } \right|$.
Given a matrix $A \in \mathrm { M } _ { d } ( \mathbb { C } )$ we define $$\| A \| = \sup _ { \| x \| _ { \infty } \leqslant 1 } \| A x \| _ { \infty } .$$
a. Show that this defines a norm on $\mathrm { M } _ { d } ( \mathbb { C } )$ and that there exists $x _ { 0 } \in \mathbb { C } ^ { d }$ such that $\left\| x _ { 0 } \right\| _ { \infty } = 1$ and $\left\| A x _ { 0 } \right\| _ { \infty } = \| A \|$. b. Show that for all $( A , B ) \in \mathrm { M } _ { d } ( \mathbb { C } )$ we have $\| A B \| \leqslant \| A \| \cdot \| B \|$.

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients and we identify $\mathbb { C } ^ { d }$ with the space of column vectors of size $d$.
For a vector $x = \left( x _ { 1 } , \ldots , x _ { d } \right) \in \mathbb { C } ^ { d }$, we define $\| x \| _ { \infty } = \max _ { 1 \leqslant i \leqslant d } \left| x _ { i } \right|$ and $\| x \| _ { 1 } = \sum _ { i = 1 } ^ { d } \left| x _ { i } \right|$.
Given a matrix $A \in \mathrm { M } _ { d } ( \mathbb { C } )$ we define $\| A \| = \sup _ { \| x \| _ { \infty } \leqslant 1 } \| A x \| _ { \infty }$. For $1 \leqslant i \leqslant d$ we define $L _ { i } = \left( a _ { i , j } \right) _ { 1 \leqslant j \leqslant d }$ as the $i ^ { \mathrm { th } }$ row vector of $A$. Show that $$\| A \| = \max _ { 1 \leqslant i \leqslant d } \left\| L _ { i } \right\| _ { 1 } .$$

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients.
a. Let $u \in \mathcal { L } \left( \mathbb { C } ^ { d } \right)$ be an endomorphism of $\mathbb { C } ^ { d }$ and $M = \left( m _ { i , j } \right) _ { 1 \leqslant i , j \leqslant d }$ the matrix of $u$ in a basis $\mathcal { B } = \left( e _ { 1 } , \ldots , e _ { d } \right)$. Express the matrix $M ^ { \prime } = \left( m _ { i , j } ^ { \prime } \right) _ { 1 \leqslant i , j \leqslant d }$ of $u$ in the basis $\mathcal { B } ^ { \prime } = \left( \alpha _ { 1 } e _ { 1 } , \ldots , \alpha _ { d } e _ { d } \right)$, where the $\alpha _ { i }$ are complex numbers. b. Suppose that $M$ is upper triangular. Show that for all $\varepsilon > 0$ we can choose the $\alpha _ { i }$ such that for $j > i$ we have $\left| m _ { i , j } ^ { \prime } \right| < \varepsilon$.

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients and we identify $\mathbb { C } ^ { d }$ with the space of column vectors of size $d$. For a vector $x = \left( x _ { 1 } , \ldots , x _ { d } \right) \in \mathbb { C } ^ { d }$, we define $\| x \| _ { \infty } = \max _ { 1 \leqslant i \leqslant d } \left| x _ { i } \right|$. If $A$ is a matrix in $\mathrm { M } _ { d } ( \mathbb { C } )$ we denote by $\operatorname { Sp } ( A )$ the spectrum of $A$ and we define the spectral radius $\sigma ( A ) = \max \{ | \lambda | , \lambda \in \operatorname { Sp } ( A ) \}$.
Let $T = \left( t _ { i , j } \right) _ { 1 \leqslant i , j \leqslant d }$ be an upper triangular matrix. Show that for all $\varepsilon > 0$, there exists a norm $\| \cdot \| ^ { \prime }$ on $\mathbb { C } ^ { d }$ such that for all $x \in \mathbb { C } ^ { d }$ we have $$\| T x \| ^ { \prime } \leqslant ( \sigma ( T ) + \varepsilon ) \| x \| ^ { \prime }$$ (one may choose $\| \cdot \| ^ { \prime }$ in the form $\| x \| ^ { \prime } = \| P x \| _ { \infty }$ for a suitably chosen matrix $P$).

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients. If $A$ is a matrix in $\mathrm { M } _ { d } ( \mathbb { C } )$ we denote by $\operatorname { Sp } ( A )$ the spectrum of $A$ and we define the spectral radius $\sigma ( A ) = \max \{ | \lambda | , \lambda \in \operatorname { Sp } ( A ) \}$. We define $\| A \| = \sup _ { \| x \| _ { \infty } \leqslant 1 } \| A x \| _ { \infty }$.
Application: norm and spectral radius. a. Let $T \in \mathrm { M } _ { d } ( \mathbb { C } )$ be an upper triangular matrix. Show that for all $\varepsilon > 0$, there exists a constant $C$ such that for all $n$ we have $\left\| T ^ { n } \right\| \leqslant C ( \sigma ( T ) + \varepsilon ) ^ { n }$. b. Show that $\lim _ { n \rightarrow \infty } \left\| T ^ { n } \right\| ^ { 1 / n } = \sigma ( T )$. c. Let now $A \in \mathrm { M } _ { d } ( \mathbb { C } )$ be an arbitrary matrix. Show that $\lim _ { n \rightarrow \infty } \left\| A ^ { n } \right\| ^ { 1 / n } = \sigma ( A )$. d. Show the equivalence $$A ^ { n } \underset { n \rightarrow \infty } { \longrightarrow } 0 \Leftrightarrow \sigma ( A ) < 1 .$$

Let $\gamma$ be a positive numerical constant. We assume the following property is satisfied: for every convex set $A \subset Q^N$, $$\mathbb{P}(X \in A) \mathbb{E}\left[\exp\left(\gamma \frac{d(X,A)^2}{4K^2}\right)\right] \leq 1.$$ We are given a 1-Lipschitz and convex function $F : \mathbb{R}^N \rightarrow \mathbb{R}$. The purpose of this question is to prove that (37) is then verified: $$\mathbb{P}(F(X) \geq m) \geq \frac{1}{2} \Longrightarrow \mathbb{P}(F(X) \leq m - t) \leq \beta e^{-\alpha t^2/K^2}$$
II.1.a) Let $s, \sigma \in \mathbb{R}$ with $s < \sigma$. By considering the set $$A_s = \left\{x \in Q^N; F(x) \leq s\right\}$$ show that $$\mathbb{P}(F(X) \leq s)\mathbb{P}(F(X) \geq \sigma) \leq \exp\left(-\gamma \frac{(\sigma - s)^2}{4K^2}\right)$$
II.1.b) Prove that (37) is verified.

Let $x$ be an arbitrary point of $Q^N$. Let $P^N$ be the set of vertices of the hypercube $[0,1]^N$, that is the set of linear combinations of the $e_i$ for $i \in \{1, \ldots, N\}$ with coefficients 0 or 1. If $A$ is a non-empty subset of $Q^N$, we define the subsets $P_A(x)$ and $R_A(x)$ of $P^N$ as follows: let $H_i$ be the hyperplane orthogonal to $e_i$, generated by the $e_j$ for $j \neq i$. Then $z \in P_A(x)$ if there exists $a \in A$ such that $$\forall i \in \{1, \ldots, N\}, z \in H_i \Longrightarrow a - x \in H_i$$ while $z \in R_A(x)$ if there exists $a \in A$ such that $$\forall i \in \{1, \ldots, N\}, z \in H_i \Longleftrightarrow a - x \in H_i.$$
Given $A \subset Q^N$ non-empty and $x \in Q^N$, we also define the quantity $$q(x, A) := \inf\left\{|z|; z \in \Gamma(P_A(x))\right\}.$$ We moreover adopt the following convention: if $A$ is the empty set, we set $q(x, A) = 2N$.
II.2.a) If $z, z' \in P^N$, we denote by $z \leq z'$ when $\langle z, e_i \rangle \leq \langle z', e_i \rangle$ for all $i \in \{1, \ldots, N\}$. Prove that $$P_A(x) = \left\{z' \in P^N; \exists z \in R_A(x), z \leq z'\right\}$$
II.2.b) Let $x \in \mathbb{R}^N$. Justify the equivalences $$x \in A \Longleftrightarrow 0 \in P_A(x) \Longleftrightarrow P_A(x) = P^N$$
II.2.c) In dimension $N = 3$, give an example of a set $A$ for which $e_3 \notin P_A(0)$ and describe precisely the sets $R_A(0)$ and $P_A(0)$ corresponding.
II.2.d) Let $B$ be a non-empty subset of $\mathbb{R}^N$. We denote by $\Gamma_0(B)$ the set of convex combinations of at most $N+1$ elements of $B$: $$\Gamma_0(B) := \left\{\sum_{j=1}^{N+1} \theta_j z_j; \theta_j \in [0,1], z_j \in B, \sum_{j=1}^{N+1} \theta_j = 1\right\}.$$ Prove that $\Gamma(B) = \Gamma_0(B)$.
Hint: you may prove that any convex combination of $m+1$ elements of $B$ with $m > N$ can be rewritten as a convex combination of at most $m$ elements of $B$.
II.2.e) Let $B$ be a non-empty subset of $\mathbb{R}^N$. Prove that $\Gamma(B)$ is a convex set, and that it is compact if $B$ is.
II.2.f) Draw and name (as a geometric object) the convex hull $\Gamma(B)$ in dimension $N = 3$, in the three following cases: $$B = \{e_1, e_2, e_1 + e_2\}, \quad B = \{e_1, e_2, e_1 + e_2, e_2 + e_3\}, \quad B = P^3.$$ For each of these examples, say whether $B$ can correspond to a set $P_A(x)$.
II.2.g) Let $A \subset Q^N$ non-empty and $x \in Q^N$. Justify that the infimum in (48) is attained.
II.2.h) Let $A \subset Q^N$ non-empty and $x \in Q^N$. Justify that $q(x, A) \leq \sqrt{N}$. Under what condition do we have $q(x, A) = 0$?
II.2.i) Let $x \in Q^N$ and $A \subset Q^N$ non-empty. Justify that $$q(x, A) = \inf\left\{|z|; z \in \Gamma(R_A(x))\right\}$$
II.2.j) Let $x \in Q^N$ and $A \subset Q^N$ with $A$ convex. Prove that $$d(x, A) \leq 2K\, q(x, A).$$
II.2.k) Let $\gamma \geq 0$ be a numerical constant. Prove that the property: ``for every convex set $A \subset Q^N$, we have $\mathbb{P}(X \in A)\mathbb{E}\left[\exp\left(\gamma\, q(X,A)^2\right)\right] \leq 1$'' implies $$\mathbb{P}(X \in A)\mathbb{E}\left[\exp\left(\gamma \frac{d(X,A)^2}{4K^2}\right)\right] \leq 1.$$

Let $$\gamma_0 = \frac{1}{4}$$ The purpose of the end of this part II is the proof by induction on the dimension $N$ of the property: for every convex set $A \subset Q^N$, $$\mathbb{P}(X \in A)\mathbb{E}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq 1,$$ for $\gamma = \gamma_0$. For $N$ a positive integer, we introduce the following induction hypothesis $H_N$: ``Let $(\Omega, \mathcal{A}, \mathbb{P})$ be a probability space. Let $N$ random variables $X_1, \ldots, X_N$ taking values in a finite set, independent and identically distributed, satisfying $\mathbb{P}(|X_n| \leq K) = 1$, and let $X = (X_i)_{1 \leq i \leq N}$ be the random vector with components $X_1, \ldots, X_N$. Then (53) is verified for $\gamma = \gamma_0 = \frac{1}{4}$''.
II.3.a) We consider the case $N = 1$. Prove that (53) is satisfied when $\gamma \leq \ln(2)$, and thus for $\gamma = \gamma_0$.
We now assume $N > 1$, and we fix $A \subset Q^N$ convex. We adopt the following notations: we decompose $$x = (\bar{x}, x_N) \quad \text{with} \quad \bar{x} = (x_i)_{1 \leq i \leq N-1} \in \mathbb{R}^{N-1}.$$ If $A \subset \mathbb{R}^N$ and $\theta \in \mathbb{R}$, we denote $$A_\theta := \left\{b \in \mathbb{R}^{N-1}; (b, \theta) \in A\right\}$$ the section of $A$ at level $\theta$. We also denote $$\bar{A} := \left\{\bar{a} \in \mathbb{R}^{N-1}; \exists \theta \in \mathbb{R}, (\bar{a}, \theta) \in A\right\}$$ the projection of $A$ onto $\mathbb{R}^{N-1}$.
II.3.b) Let $x \in Q^N$. Let $A \subset Q^N$ such that $A_{x_N}$ is non-empty. Let $\bar{z} \in P^{N-1}$. Prove that $$\bar{z} \in P_{A_{x_N}}(\bar{x}) \Longrightarrow (\bar{z}, 0) \in P_A(x)$$ and $$\bar{z} \in P_{\bar{A}}(\bar{x}) \Longrightarrow (\bar{z}, 1) \in P_A(x)$$
II.3.c) Prove that, for all $\lambda \in [0,1]$, we have $$q(x, A)^2 \leq (1-\lambda)^2 + \lambda\, q(\bar{x}, A_{x_N})^2 + (1-\lambda)\, q(\bar{x}, \bar{A})^2.$$
We fix $x_N \in \mathbb{R}$ such that $\mathbb{P}(X_N = x_N) > 0$ and we consider the probability $$\overline{\mathbb{P}}(B) := \mathbb{P}(B \mid X_N = x_N) = \frac{\mathbb{P}(B \cap \{X_N = x_N\})}{\mathbb{P}(X_N = x_N)} \quad \text{for } B \in \mathcal{A},$$ as well as the associated expectation $$\overline{\mathbb{E}}[Z] := \frac{1}{\mathbb{P}(X_N = x_N)} \mathbb{E}\left[Z\, \mathbf{1}_{\{X_N = x_N\}}\right]$$ for any random variable $Z$.
II.3.d) Assuming the induction hypothesis $H_{N-1}$, prove $$\overline{\mathbb{P}}(\bar{X} \in \bar{A})\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq e^{\gamma_0}$$ and justify that, for all $\lambda \in [0,1]$, we have $$\overline{\mathbb{P}}(\bar{X} \in A_{x_N})^\lambda\, \overline{\mathbb{P}}(\bar{X} \in \bar{A})^{1-\lambda}\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq e^{\gamma_0(1-\lambda)^2}.$$
Hint: you may assume H\"older's inequality: $$\overline{\mathbb{E}}\left[e^{\lambda Y} e^{(1-\lambda)Z}\right] \leq \left\{\overline{\mathbb{E}}\left[e^Y\right]\right\}^\lambda \left\{\overline{\mathbb{E}}\left[e^Z\right]\right\}^{(1-\lambda)}$$ for $\lambda \in [0,1]$ and $Y, Z$ random variables.
II.3.e) We assume $$\overline{\mathbb{P}}(\bar{X} \in \bar{A}) > 0,$$ and we define $$r = \frac{\overline{\mathbb{P}}(\bar{X} \in A_{x_N})}{\overline{\mathbb{P}}(\bar{X} \in \bar{A})}$$ Prove that $$r^\lambda e^{-\gamma_0(1-\lambda)^2}\, \overline{\mathbb{P}}(\bar{X} \in \bar{A})\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq 1.$$
II.3.f) We provisionally admit the following inequality: for all $\gamma \in [0, \gamma_0]$, for all $r \in ]0,1]$, $$\frac{1}{2-r} \leq \sup_{\lambda \in [0,1]} r^\lambda e^{-\gamma(1-\lambda)^2}$$ Justify that $$\overline{\mathbb{P}}(\bar{X} \in \bar{A})\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq (2 - r).$$ We shall distinguish the cases $\overline{\mathbb{P}}(\bar{X} \in A_{x_N}) > 0$ and $\overline{\mathbb{P}}(\bar{X} \in A_{x_N}) = 0$.
II.3.g) Prove that $$\mathbb{P}(X \in A)\, \mathbb{E}\left[\exp\left(\gamma_0\, q(X,A)^2\right) \mathbf{1}_{\{X_N = x_N\}}\right] \leq R(2-r)\, \mathbb{P}(X_N = x_N),$$ where $$R = \frac{\mathbb{P}(X \in A)}{\mathbb{P}(\bar{X} \in \bar{A})}$$
II.3.h) Prove that $$\mathbb{P}(X \in A)\, \mathbb{E}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq R(2-R),$$ where $R$ is defined in (72), then prove (53) and conclude the induction $H_{N-1} \Rightarrow H_N$. You should take care to account for the case where (66) is not verified.
II.3.i) Justify (69): for all $\gamma \in [0, \gamma_0]$, for all $r \in ]0,1]$, $$\frac{1}{2-r} \leq \sup_{\lambda \in [0,1]} r^\lambda e^{-\gamma(1-\lambda)^2}$$

Let $f \in \mathcal{C}(\mathbb{R})$ such that $$\lim_{x \rightarrow -\infty} f(x) = +\infty \quad \text{and} \quad \lim_{x \rightarrow +\infty} f(x) = +\infty$$ a) Show that the set $\{x \in \mathbb{R} \mid f(x) \leq f(0)\}$ is closed and bounded. b) Deduce that there exists $x_* \in \mathbb{R}$ such that $f(x_*) = \min\{f(x) \mid x \in \mathbb{R}\}$.

We suppose in this question that $f \in \mathcal{C}^1(\mathbb{R})$ is convex, and that $f'$ is $L$-Lipschitzian, for some $L > 0$. a) Show that for all $x, y \in \mathbb{R}$ $$\left|f'(x) - f'(y)\right|^2 \leq L(x-y)\left(f'(x) - f'(y)\right)$$ b) Let $x, y \in \mathbb{R}$, and let $\tilde{x} := x - \tau f'(x)$ and $\tilde{y} := y - \tau f'(y)$. Show that $$|\tilde{x} - \tilde{y}|^2 \leq |x-y|^2 - \tau(2 - \tau L)(x-y)\left(f'(x) - f'(y)\right)$$ c) We further suppose that $f$ admits a minimizer $x_*$, and that $0 < \tau \leq 2/L$. Show that the sequence $\left(\left|x_n - x_*\right|\right)_{n \in \mathbb{N}}$ is decreasing. (Recall that $\left(x_n\right)_{n \in \mathbb{N}}$ satisfies the recurrence relation $\forall n \in \mathbb{N},\, x_{n+1} := x_n - \tau f'(x_n)$.)

Deduce that $$\forall x \in \Lambda_n, \quad n\left(-h - \beta\frac{\lambda_{\max}}{2}\right) \leqslant H_n(h,x) \leqslant n\left(h - \beta\frac{\lambda_{\min}}{2}\right).$$