Corrigé ESSEC-HEC 2026 Maths appliquées ECG — Johnson-Lindenstrauss — Concentration (Q7.a à Q10) : Inégalité de Markov exponentielle, majoration P(|Z−1| > ε) ≤ 2exp(−mε²/8), réunion sur r vecteurs et existence d'une isométrie dès que m > 8ln(2r)/ε², fonction Isom

Sujet officiel du concours ESSEC-HEC, session 2026, épreuve Maths appliquées ECG. Corrigé rédigé par Ibrahim Alame.

Énoncé

Notations de la partie précédente : $∥ X ∥ = 1$ , $Z = ∥ M X ∥^{2} = \frac{1}{m} \sum_{i = 1}^{m} Y_{i}^{2}$ , $ε \in] 0, 1 [$ , $t \in] 0, \frac{1}{4}]$ , et $E (e^{t Y_{i}^{2}}) = (1 - 2 t)^{- 1/2}$ . On rappelle l'inégalité de Markov.

Q7.a. Montrer que $E (e^{t m Z})$ existe et que $P (Z > 1 + ε) ⩽ P (Z ⩾ 1 + ε) ⩽ E (e^{t m Z}) e^{- t m (1 + ε)}$ .
Q7.b. En déduire $P (Z > 1 + ε) ⩽ (e^{- t} / 1 - 2 t)^{m} e^{- t m ε}$ .
Q7.c. Établir $- t - \frac{1}{2} ln (1 - 2 t) ⩽ 2 t^{2}$ , puis $P (Z > 1 + ε) ⩽ e^{m (2 t^{2} - tε)}$ .
Q7.d. Conclure : $P (Z > 1 + ε) ⩽ e^{- m ε^{2} /8}$ .
Q8. On admet $P (Z < 1 - ε) ⩽ e^{- m ε^{2} /8}$ . En déduire $P ([Z < 1 - ε] \cup [Z > 1 + ε]) ⩽ 2 e^{- m ε^{2} /8}$ .

Soit $X = {X_{1}, \dots, X_{r}} \subset M_{n, 1} (R)$ et $B_{i}$ l'événement $[(1 - ε) ∥ X_{i} ∥^{2} ⩽ ∥ M X_{i} ∥^{2} ⩽ (1 + ε) ∥ X_{i} ∥^{2}]$ .

Q9.a. Si $X_{i} \neq = 0$ et $U_{i} = X_{i} /∥ X_{i} ∥$ , montrer que $∥ U_{i} ∥ = 1$ et $B_{i} = [1 - ε ⩽ ∥ M U_{i} ∥^{2} ⩽ 1 + ε]$ .
Q9.b. En admettant que la probabilité d'une réunion finie est majorée par la somme des probabilités, montrer que la probabilité que $M$ ne soit pas une $(ε, X)$ -isométrie est inférieure à $2 r e^{- m ε^{2} /8}$ .
Q9.c. Si $m > 8 ln (2 r) / ε^{2}$ , montrer qu'il existe $A \in M_{m, n} (R)$ qui est une $(ε, X)$ -isométrie.
Q10. Écrire Isom(LX,m,eps) qui renvoie une matrice à $m$ lignes et $n$ colonnes qui est une $(ε, X)$ -isométrie, $X$ étant donné par la liste LX de vecteurs colonnes.

Corrigé

Q7.a. Existence. Par Q5.c, $t m Z = t \sum_{i = 1}^{m} Y_{i}^{2}$ , donc

$e^{t m Z} = i = 1 \prod m e^{t Y_{i}^{2}} .$

La variable $Y_{i}$ est fonction de la seule ligne $(G_{i, 1}, \dots, G_{i, n})$ ; ces $m$ lignes sont des paquets disjoints de la famille indépendante $(G_{i, j})$ . Par le lemme des coalitions, $Y_{1}, \dots, Y_{m}$ sont mutuellement indépendantes, donc aussi $e^{t Y_{1}^{2}}, \dots, e^{t Y_{m}^{2}}$ . Chacune admet une espérance (Q6). On utilise alors le résultat suivant : si $U$ et $V$ sont indépendantes et admettent une espérance, $U V$ admet une espérance et $E (U V) = E (U) E (V)$ . Le cours l'énonce pour des variables discrètes ; on l'admet ici pour des variables à densité (le sujet ne demande pas de le démontrer). Par récurrence sur le nombre de facteurs, en appliquant à chaque étape le lemme des coalitions ( $\prod_{i ⩽ p} e^{t Y_{i}^{2}}$ est fonction de $Y_{1}, \dots, Y_{p}$ , donc indépendante de $e^{t Y_{p + 1}^{2}}$ ), on l'étend à $m$ facteurs. D'où l'existence et, par Q6.b,

$E (e^{t m Z}) = i = 1 \prod m E (e^{t Y_{i}^{2}}) = (\frac{1}{1 - 2 t})^{m} .$

Inégalités. D'abord $[Z > 1 + ε] \subset [Z ⩾ 1 + ε]$ , d'où la première inégalité par croissance de $P$ . Ensuite, $t m > 0$ donc $x \mapsto e^{t m x}$ est strictement croissante sur $R$ : $[Z ⩾ 1 + ε] = [e^{t m Z} ⩾ e^{t m (1 + ε)}]$ . On applique l'inégalité de Markov à $U = e^{t m Z}$ , variable positive qui admet une espérance, avec $a = e^{t m (1 + ε)} > 0$ :

$P (Z ⩾ 1 + ε) = P (e^{t m Z} ⩾ e^{t m (1 + ε)}) ⩽ \frac{E ( e ^{t m Z} )}{e ^{t m (1 + ε)}} = E (e^{t m Z}) e^{- t m (1 + ε)} .$

Q7.b. En reportant la valeur de $E (e^{t m Z})$ et en écrivant $e^{- t m (1 + ε)} = (e^{- t})^{m} e^{- t m ε}$ :

$P (Z > 1 + ε) ⩽ \frac{( e ^{- t} ) ^{m}}{( 1 - 2 t ) ^{m}} e^{- t m ε} = (\frac{e ^{- t}}{1 - 2 t})^{m} e^{- t m ε} .$

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →