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

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.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}.

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.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}.

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.

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

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}}