2025-Ens-MpC-Corrigé

Écoles normales supérieures — 2025

Mathématiques C — Filières MP–MPI

Fonctions d’un grand nombre de variables aléatoires

On travaille sur un espace probabilisé {(\Omega,\mathcal A,\mathbb P)}. Les variables sont discrètes, à valeurs dans des sous-ensembles dénombrables de {\mathbb R}.

Pour {X\geq0} prenant les valeurs distinctes {x_n}, {\mathbb E[X]=\sum\limits_{n\geq0}x_n\mathbb P(X=x_n)}, éventuellement infinie. Si {\mathbb E[|X|]\lt \infty}, la même somme définit l’espérance d’une variable réelle quelconque. Si {\mathbb E[X^2]\lt \infty}, alors {(\mathbb E[|X|])^2\leq\mathbb E[X^2]} et {\operatorname{Var}(X)=\mathbb E[(X-\mathbb E[X])^2]=\mathbb E[X^2]-(\mathbb E[X])^2.}On rappelle Markov : {\mathbb P(X\geq t)\leq\mathbb E[X]/t} pour {X\geq0} intégrable et {t>0}.

L’indépendance de {X_1,\ldots,X_N} signifie, pour toutes fonctions bornées {\psi_i}, {\mathbb E\left[\prod_{i=1}^N\psi_i(X_i)\right]=\prod_{i=1}^N\mathbb E[\psi_i(X_i)].}On note {\mathbf1_A} l’indicatrice de {A}. Une constante numérique est indépendante de {K,N} et des variables considérées.

I. Amplitude d’une somme de variables aléatoires

On suppose {N\geq1}, {K\geq1}, et les {X_i} de même loi, avec {\mathbb P(|X_i|\leq K)=1}, {\mathbb E[X_i]=0}, {\operatorname{Var}(X_i)\leq1}. On pose {S_N=X_1+\cdots+X_N}.

I.1 Pour {N=1}, donner sans justification un exemple de loi usuelle satisfaisant la condition de bornitude, et deux exemples ne la satisfaisant pas.
I.2 Donner, pour tout {N}, des variables satisfaisant les hypothèses et telles que {\mathbb P(|S_N|\geq N)\geq1/2}.
I.3 Si les variables sont deux à deux décorrélées, c’est-à-dire {\mathbb E[X_nX_m]=0} pour {n\ne m}, montrer {\mathbb E[|S_N|^2]\leq N}, puis {\mathbb P(|S_N|>t\sqrt N)\leq1/t^2} pour {t>0}.

I.4. Des variables {(Y_n)} sont {k}-indépendantes si toute sous-famille de {k} variables distinctes est indépendante, au sens de la factorisation des espérances de produits de fonctions bornées.

I.4.a Montrer que la {k}-indépendance implique la {j}-indépendance pour {j\leq k}.
I.4.b Qu’est-ce que la {N}-indépendance pour {N} variables {Y_1,\ldots,Y_N} ?
I.4.c Soient {Y_1,Y_2} indépendantes uniformes sur {\{0,1\}}, et {Y_3=Y_1+Y_2\pmod2}.

Montrer que {(Y_1,Y_2,Y_3)} est {2}-indépendante mais non {3}-indépendante.

I.5. On fixe un entier pair {k\in\{2,\ldots,N\}} et l’on suppose les {X_i} {k}-indépendantes. On note {\mathcal T=\{1,\ldots,N\}^k} et {m_T(n)=\#\{i:n_i=n\}} pour {T=(n_1,\ldots,n_k)}.

L’ensemble {\mathcal T_\ell} rassemble les tuples utilisant exactement {\ell} indices distincts, chacun avec multiplicité au moins {2}.

I.5.a Déterminer {|\mathcal T_1|} et {|\mathcal T_\ell|} pour {\ell>k/2}.
I.5.b Justifier {\mathbb E[S_N^k]=\sum_{T\in\mathcal T}\prod_{n=1}^N\mathbb E[X_n^{m_T(n)}],}puis {\mathbb E[S_N^k]=\sum_{\ell=1}^{k/2}\sum_{T\in\mathcal T_\ell}\prod_{n=1}^N\mathbb E[X_n^{m_T(n)}].}
I.5.c Montrer {\mathbb E[S_N^k]\leq\sum\limits_{\ell=1}^{k/2}K^{k-2\ell}|\mathcal T_\ell|}.
I.5.d Justifier {|\mathcal T_\ell|\leq\binom N\ell\ell^k\leq N^\ell\ell^k/\ell!}.
I.5.e Montrer {\ell!\geq\ell^\ell e^{-\ell}}, puis {|\mathcal T_\ell|\leq(Ne)^\ell(k/2)^{k-\ell}}.
I.5.f Montrer {\mathbb E[S_N^k]\leq\left(\frac{Kk}{2}\right)^k\sum_{\ell=1}^{k/2}\left(\frac{2Ne}{kK^2}\right)^\ell.}
I.5.g Sous l’hypothèse {kK^2\leq N}, poser {\theta=2Ne/(kK^2)} et montrer {\mathbb E[S_N^k]\leq\frac\theta{\theta-1}\left(\frac{Nek}{2}\right)^{k/2}\leq2\left(\frac{Nek}{2}\right)^{k/2}.}
I.5.h Toujours sous {kK^2\leq N}, montrer, pour {t>0}, {\mathbb P(|S_N|\geq t\sqrt N)\leq2\left(\frac{\sqrt{ek/2}}t\right)^k.}

I.6. Les {X_i} sont maintenant indépendantes. On veut établir, avec des constantes numériques {\alpha,\beta>0}, {\mathbb P(|S_N|\geq t\sqrt N)\leq\beta\exp(-\alpha t^2/K^2)\quad(t\geq0).}

I.6.a Justifier qu’il suffit de traiter {K=1}.
I.6.b Soit {k} le plus grand entier pair de {\{1,\ldots,N\}} inférieur ou égal à {2t^3/e^2}.

Justifier que {kK^2\leq N} si {e\leq t\leq(e/\sqrt2)\sqrt N}.

I.6.c Sous {e\leq t\leq(e/\sqrt2)\sqrt N}, établir l’inégalité avec {\beta=2e} et {\alpha=e^{-2}}.
I.6.d Conclure pour tout {t\geq0}, avec des constantes numériques {\alpha,\beta>0}.

II. Concentration de combinaisons de variables aléatoires

On munit {\mathbb R^N} de son produit scalaire canonique {\langle\cdot,\cdot\rangle}, de sa norme euclidienne {|\cdot|} et de sa base canonique {(e_i)}. La formule (34) du PDF porte {|x|^2:=\langle x,x\rangle^{1/2}} ; il faut lire {|x|=\langle x,x\rangle^{1/2}}, conformément à (35) : {x=\sum_{i=1}^N\langle x,e_i\rangle e_i,\quad |x|^2=\sum_{i=1}^N|\langle x,e_i\rangle|^2.}Une fonction {F} est {1}-lipschitzienne si {|F(x)-F(y)|\leq|x-y|}.

Théorème à démontrer. Les {X_i}, indépendantes et de même loi, prennent maintenant leurs valeurs dans un ensemble fini et satisfont {|X_i|\leq K} presque sûrement. On pose {X=(X_1,\ldots,X_N)}.

Pour toute fonction convexe {1}-lipschitzienne {F}, tout {m\in\mathbb R} et tout {t\geq0}, on veut montrer {\begin{array}{l}\mathbb P(F(X)\geq m)\geq\frac12\\[8pt]\quad\Longrightarrow\ \mathbb P(F(X)\leq m-t)\leq\beta e^{-\alpha t^2/K^2}\end{array}}On note {Q_N=[-K,K]^N}, de diamètre {2K\sqrt N}. Pour {A\ne\varnothing}, {d(x,A)=\inf_{a\in A}|x-a|}. Par convention, {d(x,\varnothing)=4NK}.

II.1. On suppose qu’une constante {\gamma>0} vérifie, pour tout convexe {A\subset Q_N}, {\mathbb P(X\in A)\mathbb E\!\left[\exp\!\left(\frac{\gamma d(X,A)^2}{4K^2}\right)\right]\leq1.}

II.1.a Pour {s\lt \sigma}, considérer {A_s=\{x\in Q_N:F(x)\leq s\}} et montrer {\mathbb P(F(X)\leq s)\mathbb P(F(X)\geq\sigma)\leq e^{-\gamma(\sigma-s)^2/(4K^2)}.}
II.1.b Démontrer la conclusion du théorème.

II.2. On note {P_N=\{0,1\}^N} et {H_i=\{z:z_i=0\}}. Pour {A\ne\varnothing} et {x\in Q_N}, un sommet {z} appartient à {P_A(x)} s’il existe {a\in A} tel que {z_i=0} implique {a_i=x_i} pour tout {i}. Il appartient à {R_A(x)} si l’on peut remplacer ces implications par des équivalences.

Pour {z,z'\in P_N}, la notation {z\leq z'} signifie {z_i\leq z'_i} pour tout {i}.

II.2.a Montrer {P_A(x)=\{z'\in P_N:\exists z\in R_A(x),\ z\leq z'\}}.
II.2.b Justifier {x\in A\Longleftrightarrow0\in P_A(x)\Longleftrightarrow P_A(x)=P_N}.
II.2.c En dimension {3}, donner un exemple où {e_3\notin P_A(0)} et décrire exactement {R_A(0)} et {P_A(0)}.

Pour {B\ne\varnothing}, on note {\Gamma(B)} l’ensemble de ses combinaisons convexes finies. On pose {q(x,A)=\inf\{|z|:z\in\Gamma(P_A(x))\},}et, pour {A=\varnothing}, {q(x,A)=2N}. On note {\Gamma_0(B)} l’ensemble des combinaisons convexes d’au plus {N+1} points de {B}.

II.2.d Montrer {\Gamma(B)=\Gamma_0(B)}. On pourra réduire le nombre de points d’une combinaison en contenant plus de {N+1}.
II.2.e Montrer que {\Gamma(B)} est convexe, et compact si {B} est compact.
II.2.f En dimension {3}, représenter et nommer {\Gamma(B)} pour {B=\{e_1,e_2,e_1+e_2\}}, puis {B=\{e_1,e_2,e_1+e_2,e_2+e_3\}}, puis {B=P_3}. Dire, dans chaque cas, si {B} peut être un ensemble {P_A(x)}.
II.2.g Justifier que l’infimum définissant {q(x,A)} est atteint lorsque {A\ne\varnothing}.
II.2.h Montrer {q(x,A)\leq\sqrt N}. Quand a-t-on {q(x,A)=0} ?
II.2.i Justifier la formule (51), imprimée {q(x,A)=\inf\{|z|,\;z\in\Gamma(R_A(x))\}}.
II.2.j Pour {A\subset Q_N} convexe, montrer {d(x,A)\leq2Kq(x,A)}.
II.2.k Montrer que, pour {\gamma\geq0}, la propriété {\mathbb P(X\in A)\mathbb E[e^{\gamma q(X,A)^2}]\leq1} pour tout convexe {A\subset Q_N} implique la conclusion (37).

II.3. On pose {\gamma_0=1/4}. L’hypothèse {H_N} affirme que, pour tout vecteur de {N} variables indépendantes, de même loi, à valeurs dans un ensemble fini et bornées par {K}, {\mathbb P(X\in A)\mathbb E[e^{\gamma_0q(X,A)^2}]\leq1}pour tout convexe {A\subset Q_N}.

II.3.a Pour {N=1}, montrer cette propriété dès que {0\leq\gamma\leq\ln2}, donc pour {\gamma_0}.

Pour {N>1}, on écrit {x=(\bar x,x_N)}. Pour {A\subset Q_N}, on note {A_\theta=\{b:(b,\theta)\in A\}} sa section, et {\bar A=\{b:\exists\theta,\ (b,\theta)\in A\}} sa projection sur {\mathbb R^{N-1}}. Ces ensembles sont convexes lorsque {A} l’est.

II.3.b Si {A_{x_N}\ne\varnothing}, montrer {z\in P_{A_{x_N}}(\bar x)\Rightarrow(z,0)\in P_A(x)} et {z\in P_{\bar A}(\bar x)\Rightarrow(z,1)\in P_A(x)}.
II.3.c Montrer, pour {\lambda\in[0,1]}, {q(x,A)^2\!\leq\!(1\!-\!\lambda)^2\!+\!\lambda q(\bar x,A_{x_N})^2\!+\!(1\!-\!\lambda)q(\bar x,\bar A)^2}

On fixe {x_N} tel que {\mathbb P(X_N=x_N)>0}. On note {\mathbb P_*} la probabilité conditionnelle sachant {X_N=x_N}, et {\mathbb E_*} l’espérance associée. On pose {\bar X=(X_1,\ldots,X_{N-1})}.

II.3.d En admettant {H_{N-1}}, montrer {\mathbb P_*(\bar X\in\bar A)\mathbb E_*[e^{\gamma_0q(X,A)^2}]\leq e^{\gamma_0}}puis, pour {\lambda\in[0,1]}, {\begin{array}{l}\mathbb P_*(\bar X\in A_{x_N})^\lambda\mathbb P_*(\bar X\in\bar A)^{1-\lambda}\mathbb E_*[e^{\gamma_0q(X,A)^2}]\\[8pt]\qquad\leq e^{\gamma_0(1-\lambda)^2}\end{array}}On pourra utiliser Hölder sous la forme {\mathbb E[e^{\lambda Y}e^{(1-\lambda)Z}]\leq\mathbb E[e^Y]^\lambda\mathbb E[e^Z]^{1-\lambda}}.
II.3.e Si {\mathbb P_*(\bar X\in\bar A)>0}, poser {r=\mathbb P_*(\bar X\in A_{x_N})/\mathbb P_*(\bar X\in\bar A)} et montrer {r^\lambda e^{-\gamma_0(1-\lambda)^2}\mathbb P_*(\bar X\in\bar A)\mathbb E_*[e^{\gamma_0q(X,A)^2}]\leq1.}

On admet provisoirement, pour {0\leq\gamma\leq\gamma_0} et {0\leq r\leq1}, {\frac1{2-r}\leq\sup_{\lambda\in[0,1]}r^\lambda e^{-\gamma(1-\lambda)^2}.\tag{69}}

II.3.f En déduire {\mathbb P_*(\bar X\in\bar A)\mathbb E_*[e^{\gamma_0q(X,A)^2}]\leq2-r}, en distinguant les cas où la probabilité de la section est positive ou nulle.
II.3.g Montrer {\begin{array}{l}\mathbb P(X\in A)\mathbb E[e^{\gamma_0q(X,A)^2}\mathbf1_{\{X_N=x_N\}}]\\[8pt]\quad\leq R(2-r)\mathbb P(X_N=x_N)\end{array}}où {R=\mathbb P(X\in A)/\mathbb P(\bar X\in\bar A)}.
II.3.h Montrer {\mathbb P(X\in A)\mathbb E[e^{\gamma_0q(X,A)^2}]\leq R(2-R)}, puis conclure {H_{N-1}\Rightarrow H_N}, en traitant aussi le cas où la projection a une probabilité nulle.
II.3.i Justifier l’inégalité (69).