Let $U$ and $V$ be two random variables on $(\Omega, \mathcal{A}, P)$ possessing a second moment and such that $V$ is not almost surely zero. Show that $E\left(U^{2}\right) E\left(V^{2}\right) - E(UV)^{2} \geqslant 0$ and that $E\left(U^{2}\right) E\left(V^{2}\right) - E(UV)^{2} = 0$ if and only if there exists $\lambda \in \mathbb{R}$ such that $\lambda V + U$ is almost surely zero.

We assume that $f \in \mathcal { C } ( [ 0,1 ] , \mathbb { R } )$ satisfies: $$\exists \alpha \in ]0,1] , \exists K \geq 0 , \forall ( y , z ) \in [ 0,1 ] ^ { 2 } , | f ( y ) - f ( z ) | \leq K | y - z | ^ { \alpha }$$ and that $c(x) = 0$ for all $x \in [0,1]$. For all $n \in \mathbb{N}^*$, we define: $$B _ { n } f ( X ) = \sum _ { k = 0 } ^ { n } f \left( \frac { k } { n } \right) \binom { n } { k } X ^ { k } ( 1 - X ) ^ { n - k }$$
Let $x \in ]0,1[$ and $n \in \mathbb { N } ^ { * }$. We consider $X _ { 1 } , \ldots , X _ { n }$ mutually independent random variables all following the same Bernoulli distribution with parameter $x$. We set
$$S _ { n } = \frac { X _ { 1 } + \cdots + X _ { n } } { n }$$
(a) Express $\mathbb { E } \left( S _ { n } \right) , \mathbb { V } \left( S _ { n } \right)$ and $\mathbb { E } \left( f \left( S _ { n } \right) \right)$ in terms of $x , n$ and the polynomial $B _ { n } f$.
(b) Deduce the inequalities:
$$\sum _ { k = 0 } ^ { n } \left| x - \frac { k } { n } \right| \binom { n } { k } x ^ { k } ( 1 - x ) ^ { n - k } \leq \mathbb { V } \left( S _ { n } \right) ^ { \frac { 1 } { 2 } } \leq \frac { 1 } { 2 \sqrt { n } }$$

We assume that $f \in \mathcal { C } ( [ 0,1 ] , \mathbb { R } )$ satisfies: $$\exists \alpha \in ]0,1] , \exists K \geq 0 , \forall ( y , z ) \in [ 0,1 ] ^ { 2 } , | f ( y ) - f ( z ) | \leq K | y - z | ^ { \alpha }$$ For all $n \in \mathbb{N}^*$, define $B _ { n } f ( X ) = \sum _ { k = 0 } ^ { n } f \left( \frac { k } { n } \right) \binom { n } { k } X ^ { k } ( 1 - X ) ^ { n - k }$.
Let $n \in \mathbb { N } ^ { * }$. Show that
$$\left\| f - B _ { n } f \right\| _ { \infty } \leq \frac { 3 K } { 2 } \frac { 1 } { n ^ { \alpha / 2 } }$$
Hint: One may first express $f ( x ) - B _ { n } f ( x )$ in terms of $\mathbb { E } ( f ( x ) - f \left( S _ { n } \right) )$.

Let $p$ and $q$ be two strictly positive reals such that $\frac{1}{p} + \frac{1}{q} = 1$. Deduce that if $X$ and $Y$ are two real-valued random variables on the finite probability space $(\Omega, \mathcal{A}, \mathbb{P})$ then
$$\mathbb{E}(|XY|) \leqslant \mathbb{E}(|X|^{p})^{1/p} \mathbb{E}(|Y|^{q})^{1/q}$$
You may first show this result when $\mathbb{E}(|X|^{p}) = \mathbb{E}(|Y|^{q}) = 1$.

We consider $g(X)$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable with independent Rademacher coefficients and $g(M) = \|M \cdot u\|$ for a fixed unit vector $u$, and $m$ is a median of $g(X)$. Deduce that $\mathbb{E}\left((g(X) - m)^{2}\right) \leqslant 32$.

Let $p$ and $q$ be two strictly positive reals such that $\frac{1}{p} + \frac{1}{q} = 1$. Deduce that if $X$ and $Y$ are two real-valued random variables on the finite probability space $(\Omega, \mathcal{A}, \mathbb{P})$, then
$$\mathbb{E}(|XY|) \leqslant \mathbb{E}(|X|^{p})^{1/p} \mathbb{E}(|Y|^{q})^{1/q}$$
You may first prove this result when $\mathbb{E}(|X|^{p}) = \mathbb{E}(|Y|^{q}) = 1$.

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$. Deduce the expectation of $\exp\left(\frac{1}{8} d(X, u)^{2}\right)$ and show that it is less than or equal to $2^{n}$.

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_{-}$. We have shown the inequality
$$d(X, C)^{2} \leqslant 4\lambda^{2} + (1 - \lambda) d(X', C_{\varepsilon_{n}})^{2} + \lambda d(X', C_{-\varepsilon_{n}})^{2}$$
Show that for all $\lambda$ in $[0, 1]$
$$\mathbb{E}\left(\left.\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right\rvert \, \varepsilon_{n} = -1\right) \leqslant \exp\left(\frac{\lambda^{2}}{2}\right) \mathbb{E}\left(\left(\exp\left(\frac{1}{8} d(X', C_{-1})^{2}\right)\right)^{1-\lambda} \cdot \left(\exp\left(\frac{1}{8} d(X', C_{+1})^{2}\right)\right)^{\lambda}\right)$$

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_{-}$.
Deduce that
$$\mathbb{E}\left(\left.\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right\rvert \, \varepsilon_{n} = -1\right) \leqslant \exp\left(\frac{\lambda^{2}}{2}\right) \left(\mathbb{E}\left(\exp\left(\frac{1}{8} d(X', C_{-1})^{2}\right)\right)\right)^{1-\lambda} \cdot \left(\mathbb{E}\left(\exp\left(\frac{1}{8} d(X', C_{+1})^{2}\right)\right)\right)^{\lambda}$$

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_{-}$.
Deduce from the above that for all $\lambda$ in $[0, 1]$
$$\mathbb{E}\left(\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right) \leqslant \frac{1}{2}\left(\frac{1}{p_{+}} + \exp\left(\frac{\lambda^{2}}{2}\right) \frac{1}{(p_{-})^{1-\lambda}} \cdot \frac{1}{(p_{+})^{\lambda}}\right)$$

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_{-}$. We set $\lambda = 1 - \frac{p_{-}}{p_{+}}$. Show that
$$\mathbb{E}\left(\exp\left(\frac{1}{8} d(X, C)^{2}\right)\right) \leqslant \frac{1}{2p_{+}}\left(1 + \exp\left(\frac{\lambda^{2}}{2}\right) (1 - \lambda)^{\lambda - 1}\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. Let $m$ be a median of $g(X)$. Deduce that $\mathbb{E}\left((g(X) - m)^{2}\right) \leqslant 32$.

In the general model of a Pólya urn ($b = c = 0$, $a = d$), using the results of questions 16 and 19, determine the expectation of $X_{n}$.

For $i \in \mathbb{N}^{*}$, let $Y _ { i }$ be the Bernoulli random variable indicating the event $$Y _ { i } = \mathbf{1} \left( S _ { i } \notin \left\{ S _ { k } , 0 \leq k \leq i - 1 \right\} \right) .$$ Show that, for $i \in \mathbb{N}^{*}$: $$P \left( Y _ { i } = 1 \right) = P ( R > i )$$ Deduce that, for $n \in \mathbb{N}^{*}$: $$E \left( N _ { n } \right) = 1 + \sum _ { i = 1 } ^ { n } P ( R > i )$$

Let $n \geqslant 1$ be a natural integer, and let $(X_1, \ldots, X_n)$ be discrete real random variables that are mutually independent such that, for all $k \in \{1, \ldots, n\}$, $$P[X_k = 1] = P[X_k = -1] = \frac{1}{2}$$ We define $$S_n = \frac{1}{n} \sum_{k=1}^{n} X_k$$ as well as, for all $\lambda \in \mathbb{R}$, $$\psi(\lambda) = \log\left(\frac{1}{2}e^{\lambda} + \frac{1}{2}e^{-\lambda}\right)$$ For each $\lambda \geqslant 0$, we set $$m(\lambda) = \frac{E[X_1 \exp(\lambda X_1)]}{E[\exp(\lambda X_1)]}$$ as well as $$D_n(\lambda) = \exp(\lambda n S_n - n \psi(\lambda))$$
(a) For $n \geqslant 2$ and $\lambda \geqslant 0$, show that $$E[(X_1 - m(\lambda))(X_2 - m(\lambda)) D_n(\lambda)] = 0$$
(b) Deduce that, for $n \geqslant 1$ and $\lambda \geqslant 0$, $$E[(S_n - m(\lambda))^2 D_n(\lambda)] \leqslant \frac{4}{n}.$$

Let $n \geqslant 1$ be a natural integer, and let $\left( X _ { 1 } , \ldots , X _ { n } \right)$ be mutually independent discrete real random variables such that, for all $k \in \{ 1 , \ldots , n \}$, $$P \left[ X _ { k } = 1 \right] = P \left[ X _ { k } = - 1 \right] = \frac { 1 } { 2 }$$ We define $$S _ { n } = \frac { 1 } { n } \sum _ { k = 1 } ^ { n } X _ { k }$$ as well as, for all $\lambda \in \mathbb { R }$, $$\psi ( \lambda ) = \log \left( \frac { 1 } { 2 } e ^ { \lambda } + \frac { 1 } { 2 } e ^ { - \lambda } \right)$$ For each $\lambda \geqslant 0$, we set $$m ( \lambda ) = \frac { E \left[ X _ { 1 } \exp \left( \lambda X _ { 1 } \right) \right] } { E \left[ \exp \left( \lambda X _ { 1 } \right) \right] }$$ as well as $$D _ { n } ( \lambda ) = \exp \left( \lambda n S _ { n } - n \psi ( \lambda ) \right)$$
(a) For $n \geqslant 2$ and $\lambda \geqslant 0$, show that $$E \left[ \left( X _ { 1 } - m ( \lambda ) \right) \left( X _ { 2 } - m ( \lambda ) \right) D _ { n } ( \lambda ) \right] = 0$$
(b) Deduce that, for $n \geqslant 1$ and $\lambda \geqslant 0$, $$E \left[ \left( S _ { n } - m ( \lambda ) \right) ^ { 2 } D _ { n } ( \lambda ) \right] \leqslant \frac { 4 } { n }$$

We fix a real random variable $X : \Omega \rightarrow \mathbb { R }$, whose image $X ( \Omega )$ is a countable set, with $X ( \Omega ) = \left\{ x _ { n } , n \in \mathbb { N } \right\}$ and $a _ { n } = \mathbb { P } \left( X = x _ { n } \right)$. We assume that $\phi _ { X }$ is of class $C ^ { 2 }$ on $\mathbb { R }$. Using the results of Q31 and Q32, deduce that $X$ admits a moment of order 2.

We consider $n$ discrete random variables $Y_1, \ldots, Y_n$ with random vector $Y$ and covariance matrix $\Sigma_Y$. We assume $r < n$ where $r$ is the rank of $\Sigma_Y$. We denote by $d = \dim \ker \Sigma_Y$ and we consider an orthonormal basis $(V_1, \ldots, V_d)$ of $\ker \Sigma_Y$.
Prove that $$\forall j \in \llbracket 1, d \rrbracket, \quad \mathbb{V}\left(V_j^\top(Y - \mathbb{E}(Y))\right) = 0.$$

We assume that $\Sigma_Y$ has $n$ distinct eigenvalues which we order in strictly decreasing order $\lambda_1 > \cdots > \lambda_n$. We equip ourselves with a vector $U_0$ such that $\mathbb{V}\left(U_0^\top Y\right) = \max_{U \in C} \mathbb{V}\left(U^\top Y\right)$, where $C = \left\{ U \in \mathcal{M}_{n,1}(\mathbb{R}) \mid U^\top U = 1 \right\}$. We denote $$C' = \left\{ U \in \mathcal{M}_{n,1}(\mathbb{R}) \mid U^\top U = 1 \text{ and } U_0^\top U = 0 \right\}.$$
Justify that $q_Y$ admits a maximum on $C'$.

We now study the linearization problem in the case $|\lambda| = 1$, with $\lambda$ not a root of unity. We set, for $m \geqslant 1$, $$\alpha_m := \min(1/5, \omega_{m+1}, \omega_{m+2}, \ldots, \omega_{2m}), \quad \gamma_m := \alpha_m^{2/m},$$ where $\omega_k := |\lambda^k - \lambda|, k \geqslant 2$, and $G$ as defined in question (26).
Show that $$\hat{G}(r) \leqslant \left(\alpha_m + (1 + \alpha_m)\alpha_m^2 + \frac{\alpha_m(1 + \alpha_m)(1 + \alpha_m^2)}{1 - \alpha_m}\right) r \leqslant r$$ for all $r$ such that $$0 \leqslant r \leqslant \frac{1 - \alpha_m}{(1 + \alpha_m)(1 + \alpha_m^2)} \gamma_m r_0$$

We fix two functions $f$ and $g$ in $E$. For $x > 0$, we set $F ( x ) = - U ( f ) ^ { \prime } ( x ) \mathrm { e } ^ { - x }$. It has been shown that $| U ( g ) ( x ) | \leqslant 4 \| g \| \frac { \sqrt { x } \mathrm { e } ^ { x / 2 } } { 1 + x }$ and $\left| U ( f ) ^ { \prime } ( x ) \right| \leqslant \| f \| \frac { \mathrm { e } ^ { x / 2 } } { \sqrt { x } }$. Show that for all $x > 0 , | F ( x ) U ( g ) ( x ) | \leqslant \frac { 4 \| f \| \| g \| } { 1 + x }$.

We fix two functions $f$ and $g$ in $E$. For $x > 0$, we set $F ( x ) = - U ( f ) ^ { \prime } ( x ) \mathrm { e } ^ { - x }$ where $U(f)^\prime(x) = \mathrm { e } ^ { x } \int _ { x } ^ { + \infty } f ( t ) \frac { \mathrm { e } ^ { - t } } { t } \mathrm {~d} t$. Show that for all $x \in ] 0,1] , | F ( x ) | \leqslant \| f \| \left( \mathrm { e } ^ { - 1 } - \ln ( x ) \right) ^ { 1 / 2 }$. One may use Question 19.

Let $\mathcal{C}^{1}$ be the space of functions of class $C^{1}$ from $[-\pi, \pi]$ to $\mathbf{C}$. For $f \in \mathcal{C}^{1}$, we set $$\|f\|_{\infty} = \max\{|f(t)|; t \in [-\pi, \pi]\} \quad \text{and} \quad V(f) = \int_{-\pi}^{\pi} |f^{\prime}|.$$
By considering a well-chosen sequence of functions, show that there does not exist an element $C$ of $\mathbf{R}^{+*}$ such that $$\forall f \in \mathcal{C}^{1}, \quad V(f) \leq C\|f\|_{\infty}$$

Let $E = \{x_1, x_2, \ldots, x_n, \ldots\}$ be an infinite countable set. We denote $\mathscr{M}(E)$ the set of probability measures on $E$. We fix a sequence $(\mu_n)_{n \in \mathbb{N}}$ of elements of $\mathscr{M}(E)$ and $\mu \in \mathscr{M}(E)$ satisfying $$\forall x \in E, \quad \lim_{n \rightarrow +\infty} \mu_n(x) = \mu(x) \tag{1}$$ We also fix a real number $\varepsilon > 0$. Show that there exists a finite subset $F_\varepsilon$ of $E$ and an integer $N_\varepsilon \geqslant 0$ such that $\mu(F_\varepsilon) > 1 - \varepsilon$ and for all integer $n \geqslant N_\varepsilon$ $$\sum_{x \in F_\varepsilon} |\mu_n(x) - \mu(x)| < \varepsilon$$

Let $E = \{x_1, x_2, \ldots, x_n, \ldots\}$ be an infinite countable set. We denote $\mathscr{M}(E)$ the set of probability measures on $E$. We fix a sequence $(\mu_n)_{n \in \mathbb{N}}$ of elements of $\mathscr{M}(E)$ and $\mu \in \mathscr{M}(E)$ satisfying condition (1): $\forall x \in E, \lim_{n \to +\infty} \mu_n(x) = \mu(x)$. We fix $\varepsilon > 0$ and a finite subset $F_\varepsilon$ of $E$ and integer $N_\varepsilon$ as in 10a. Show that for every subset $A$ of $E$: $$\left|\mu_n(A) - \mu(A)\right| \leqslant \left|\mu_n(A \cap F_\varepsilon) - \mu(A \cap F_\varepsilon)\right| + \mu(E \backslash F_\varepsilon) + \mu_n(E \backslash F_\varepsilon)$$ and deduce that if $n \geqslant N_\varepsilon$, then $\left|\mu_n(A) - \mu(A)\right| < 4\varepsilon$.