Centrale Maths 1 MP 2018

Thème de l'épreuve Aplatissement aléatoire d'un ensemble de points en grande dimension
Principaux outils utilisés probabilités, espérance conditionnelle, produits scalaires, distances
Mots clefs famille orthonormée, projeté orthogonal, inégalité de Talagrand, théorème de Johnson-Lindenstrauss, variables aléatoires à queue sous-gaussienne, variables aléatoires de Rademacher

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


î, % Mathématiques 1 O0 °.) , 1--l --/ MP o tnucnuns EENÏHHLE--SUPËLEE 4 heures Calculatrices autorisées N Aplatz'ssement aléatoire d'un ensemble de points en grande dimension Notations -- Dans tout le problème N, le et d désignent des entiers supérieurs ou égaux à deux. -- Pour tous entiers naturels non nuls p et q, on note Mpfiq([R) l'ensemble des matrices a p lignes et q colonnes à coefficients réels. -- On note AT la transposée d'une matrice A. -- Pour tous entiers naturels p et q, avec p < q, la notation [|p, q|| désigne l'ensemble {i EUR N | p g i < q}. -- Dans tout le problème on note ( Q, A, P) un espace probabilisé fini. Toutes les variables aléatoires considérées sont définies sur Q. -- Pour tout événement A de probabilité non nulle, et pour tout événement B, on note [PA(B) ou [P(B | A) la probabilité conditionnelle de B sachant A. -- Etant donnée une variable aléatoire Z à valeurs réelles, on note : (Z) son espérance. -- On dit qu'une variable aléatoire Z est une variable de Rademacher lorsque Z (Q) : {--1, 1} et -- De façon générale, si E est un espace euclidien, son produit scalaire et sa norme seront respectivement notés (. | > et |||.| Ces notations seront utilisées notamment pour Rd et Rk, munis de leurs structures euclidiennes canoniques. Problématique On s'intéresse à la question suivante : étant donnés N points dans un espace euclidien de grande dimension, est--il possible de les envoyer linéairement dans un espace de petite dimension sans trop modifier les distances entre ces points '? Pour préciser cette question, considérons N vecteurs distincts vl, ..., 'UN dans [Rd. Pour tout réel 5 tel que 0 < 6 < 1, on dit qu'une application linéaire f : [Rd --> lR'" est une e--isométrie pour vl, ..., U N lorsque : V(i,j) EUR ll, Nl2, (1-- EUR)llm- -- va| < ||f(w) -- f(w)|l < (1 + EUR>|lw -- vj|l La question peut se reformuler ainsi : -- Objectif Pour quelles valeurs de k existe--t--il f : Rd --> [Rk qui soit une e--isométrie pour vl, ..., 'UN '? On se propose d'établir le théorème suivant, démontré par William B. Johnson et J oram Lindenstrauss en 1984 : Il existe une constante absolue e strictement positive telle que : quels que soient N et d, entier naturels supérieurs ou égaux à 2 et quels que soient "1: , 'UN distincts dans Rd, il suffit que pour qu'il existe une e--isométrie f : Rd --> [Rk pour vl, , UN. Les seules méthodes connues à ce jour pour démontrer ce théorème sont de nature probabiliste. Dans la partie l, on établit des résultats préliminaires portant sur la convexité et les probabilités. La partie Il est consacrée à la démonstration d'une inégalité de concentration, qui est utilisée dans la partie 111 où le théorème de Johnson--Lindenstrauss est démontré. 2018-03--02 14:50:23 Page 1/6 («à BY--NC-SA I Préliminaires I.A + Projection sur un conveoee fermé Soit E un espace euclidien. Q 1. Soient a et b dans E. Montrer la relation suivante et en donner une interprétation géométrique : la + b|l2 + la -- b|l2 : 2 (|IOE|l2 + |lb|l2) , . . , . u + u' Q 2. En dedu1re que s1 u, v et U' dans E ver1fient v # u" et ||u-- v|| : ||u -- v' || alors ||u -- 2 || < ||u -- v||. Q 3. Soient F un fermé non vide de E et u dans E. Montrer qu'il existe fu dans F tel que VwEF, |lu--v|l<|lu--wll Q 4. En déduire que si C est un convexe fermé non vide de E et u est un vecteur de E alors il existe un unique 1) dans C tel que ... e F. |u -- v| < |u -- ...| On dira que 1) est le projeté de u sur C et on notera d(u, C) : ||u -- v||. LB + Inégalité de Hälder pour l'espérance 1 1 Soient p et q deux réels strictement positifs tels que -- + -- : 1. P q Q 5. Montrer que, pour tous réels positifs a et b, ap bq ab g -- + -- P Q On pourra utiliser la concavité du logarithme. Q 6. En déduire que si X et Ysont deux variables aléatoires réelles sur l'espace probabilisé fini (Q, A, [P) alors "(IXYI) < "(IXIP)W '(lqu)l/q On pourra d'abord montrer ce résutat lorsque -(|X|p) : -(|Y|q) : 1. LG -- Espérance conditionnelle Soit X : Q _) B? une variable aléatoire à valeurs réelles. Pour tout événement A C Q de probabilité non nulle, l'espérance conditionnelle de X sachant A, notée - (X | A), est par définition le réel *(X|A)= î: Û°A(X=OE)'OE OEEX(Q) En d'autres termes, -(X | A) est l'espérance de X dans l'espace (Q, A, lPA). Les propriétés usuelles de linéarité et de positivité de l'espérance, qu'on ne demande pas de redémontrer, sont ainsi valables pour l'espérance conditionnelle sachant A. Q 7. Soit (Al, ..., A...) un système complet d'événements de probabilités non nulles. Montrer que - = ÎP - Çî(X | A.> i=1 I.D + Variables aléatoires à queue sous-gaussienne Soit X : Q --> R une variable aléatoire réelle. On suppose qu'il existe deux réels strictement positifs (1 et b tels que, pour tout réel positif t, [P(|X| ; 15) < aexp(--bt2) Q 8. Montrer que +oo -(X2) =2 / t[P(|X| 2t)dt () On pourra noter X2(Q) : {y1, ...,yn} avec 0 < yl < y2 < < yn. 2018-03--02 14:50:23 Page 2/6 | @'3 (1 Q 9. Montrer que le moment d'ordre deux de X est inférieur ou égal à E' Soit 6 un réel tel que 0 < |5| g %. Q 10. Justifier que, pour tout réel t, [P(|X+ôl ? t) < [P(|Xl ? t-- |6|) Q 11. Montrer que, pour tout réel t, 2 1 2 --b(t-- |5|> < a-- 5bt Q 12. En déduire que pour tout réel t tel que t ; |5| on a 1 [P(|X + (?| 2 75) < a exp(a) exp (--äbt2> Q 13. Justifier que l'inégalité précédente reste valable si 0 < t < |6 | II L'inéga1îté de concentration de Talagrand Soit E un espace euclidien de dimension n 2 1 muni d'une base orthonormée (el, ..., en). Soient el, , en : Q --> {--1, 1} des variables aléatoires de Rademacher indépendantes dans leur ensemble. n On pose X : EE,-e,. 7'=1 L'objectif de cette partie est de montrer, pour tout convexe fermé non vide 0 de E, U°(X EUR c>- » (exp (%d(X,C)?)) g 1 (11.1) II.A -- Étude de deus: cas particuliers Q 14. Traiter le cas où C est un convexe fermé de E ne rencontrant pas X (Q) On suppose, dans la suite de cette sous--partie 11.A uniquement, que C est un convexe fermé de E qui rencontre X(Q) en un seul vecteur u. 1 Q 15. Montrer que ÂdE' n nf1 7TI E 332--61-- l--> % 331--61- i=1 i=1 nil On pose X ' : 7r 0 X = E eiei. C'est une variable aléatoire à valeurs dans E'. i=1 Pour t dans {--1, 1} on note -- Ht l'hyperplan affine E' + ten ; -- Ct : 7T(C fi Ht). Q 19. Montrer, pour :C' E E' et 75 EUR {--1, 1}, que a:' E Ct (:> :C' +ten E C. Q 20. Montrer que C +1 et CL1 sont des convexes fermés non vides de E'. 2018-03--02 14:50:23 Page 3/6 (GQ BY--NC-SA Pour t dans { --1, l}, on note Y,, le projeté de X ' sur le convexe fermé non vide C,. C'est une variable aléatoire à valeurs dans E'. Q 21. Montrer que 1 1 [P(X EUR C) : îlP(X' EUR CH) + 5P(X' EUR 011) II.D -- Une inégalité cruciale Soit A un réel tel que 0 { À { 1. Q 22. Montrer que d(X1 0) < "(1 _ À)(î/sn + EURnen) + )'(st _ Enfin) _ X" 'n. Q 23. En déduire que d(Xa @" < 4À2 + ll(1 -- À)(st -- X') + À(stn -- X')ll2 puis que d(X7C)2 < 4À2 + (1 -- À)llY.n -- X'll2 + ÀllYfen -- X'll2 Ainsi, on a montré l'inégalité d(X, C)2 { 4À2 + (1 -- À)d(X', CE )2 + Àd(X', CLE )2 n n ILE * Espérances conditionnelles On note p+=[P(X'ECH) et pÿ:lP(X/EURCÿl) On va supposer, sans perte de généralité, que p + 2 pi. Q 24. Montrer que pi > 0. Q 25. Montrer que pour tout A dans (0, 1] -- (exp (êdZ) | e.. = --1) < exp (',) - ((exp (âd(XflCl)2))U . (exp (àd(X',C,l)2))À) Q 26. En déduire que - (exp (êd2)))w . ( (exp (%d(X', c.1>2)))À Q 27. À l'aide de l'hypothèse de récurrence, justifier que ' (exp (âd(X,C)2) | En :1) { L p+ Q 28. Déduire de ce qui précède que pour tout A dans (0, 1] ' (eXp (âd) < % (à +...) (AZ--2) (rtlH ' (pî)') II. F * Optimisation Q 29. On pose À : 1 -- &. Montrer que p+ ' (exp (%d(X,C)2)) < 2;+ (l +exp (ÿ) (1 -- A)") Q 30. Montrer que pour tout 93 EUR {0,11 OE2 2 +(oe--l)ln(l--oe) (x e C) - P(d(X, C) ; t) < exp (32) III Démonstration du théorème de Johnson-Lindenstrauss Dans cette partie on considère l'espace E : Mk,d([R) muni du produit scalaire défini par V(A,B) EUR E2, (A | B) : tr(AT - B) On notera |||| F la norme euclidienne associée. On rappelle que Rd et [R]" sont munis de leurs normes euclidiennes canoniques, notées indistinctement ||||. On identifie [Rd a Md71([R), de sorte qu'un vecteur quelconque x : (æ1,....,æd) de [Rd peut être identifié à la matrice colonne (acl æd)T. On fixe un vecteur (ul, ..., ud) dans [Rd, identifié comme ci--dessus a la matrice colonne (ul...ud)T de Md,1([R>)a et tel que ||u|| : 1. On définit l'application . Mk,d<[R) --> |? 9' Mi-->||Mw|l Soit X : (eij) 1 0. Q 36. Montrer que pour toute matrice JW dans Mk,d([R) d(M,C) g(M) III.B * Médianes On dit qu'un réel m est une médiane de g(X ) lorsque n>(g(X) ; m) 2% et n>(g(X) < m) ; Q 38. Justifier que g(X ) admet au moins une médiane. On pourra considérer la fonction G de [R dans [R telle que, pour tout réel t, G(t) : P(g(X) < t), et examiner l'ensemble G*1(|1/2,1|). Q 39. Déduire de ce qui précède que, pour tout réel strictement positif t 1 t) < 4exp (--ët2) \\/ P(|g -- ml où m est une médiane de g(X ) 2018-03--02 14:50:23 Page 5/6 (CÔ BY--NC-SA Q 40. En déduire que ' <(g(X) -- m)2) < 32. Q 41. Montrer que ' (g(X)2) : k, et en déduire que - (g(X)) < \/Ë. Q 42. En déduire que (xÆ -- m)2 < - ((g(X) - m)2). III.C * Un lemme-clé Q 43. Montrer que, pour tout réel strictement positif t [P(|g(X) -- \/Ë| } 75) < 4exp(4) exp (--11--6t2) X 1 1 On pose Ak : --. Soient EUR dans ]0,1{ et 6 dans ]0,1/2{. On suppose que k: 2 160 M /5). \/Ë Q 44. Montrer que, pour tout vecteur unitaire u dans Rd : [P({||Ak-uu--iy>s) <5 III.D * Conclusion On conserve les notations et les hypothèses précédentes. Soient vl, UN des vecteurs distincts dans [Rd. Pour tout (i,j) EUR [[LN]]2 tel que i < j on note Eij l'événement (1--5)H"i _UjH < "Ale 'Ui_ Ak ' "j" < (1 + 5)""i _ "j" 45. Montrer que [P E -- < 5, Où Î dési ne l'événement contraire de E- -. 13 1] g 'L] Q 46. En déduire que [P ( fi Bij) } 1-- wé. igi 

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Centrale Maths 1 MP 2018 -- Corrigé Ce corrigé est proposé par Céline Chevalier (enseignant-chercheur à l'université) ; il a été relu par Florian Metzger (docteur en mathématiques) et Vincent Puyhaubert (professeur en CPGE). L'objectif de ce problème est la preuve d'un théorème de Johnson­Lindenstrauss concernant l'aplatissement aléatoire d'un ensemble de points en grande dimension : étant donné v1 , . . . , vN distincts dans Rd , on cherche à envoyer linéairement ces points dans un espace de plus petite dimension sans trop modifier les distances. Plus précisément, on fixe > 0 puis on cherche f : Rd - Rk linéaire telle que (i, j) [[ 1 ; N ]]2 (1 - )kvi - vj k 6 kf (vi ) - f (vj )k 6 (1 + )kvi - vj k Le théorème que l'on cherche à démontrer assure l'existence d'une telle application dès lors que k > c ln N/2 où la constante c ne dépend ni de N, ni de . Ce sujet combine un peu d'algèbre euclidienne et beaucoup de probabilités. · Dans une première partie, on montre d'abord un résultat de projection sur un convexe fermé, puis une inégalité classique de Hölder pour l'espérance, qui servira fréquemment dans la suite. Le sujet définit ensuite la notion d'espérance conditionnelle et introduit les variables aléatoires à queue sous-gaussienne, qui sont les variables aléatoires réelles X telles qu'il existe deux réels strictement positifs a et b vérifiant t > 0 P(|X| > t) 6 a exp(-bt2 ) La partie se conclut en prouvant l'inégalité suivante sur ces variables, qui sera p elle aussi utilisée plus loin : si est un réel tel que 0 6 || 6 a/b, alors t > 0 P(|X + | > t) 6 a exp(a) exp -bt2 /2 · La deuxième partie, assez longue et technique, introduit les variables aléatoires de Rademacher (vérifiant Z() = {-1; 1} et P(Z = -1) = P(Z = 1) = 1/2) et se donne pour objectif de prouver l'inégalité de concentration de Talagrand, d'abord sur un cas particulier puis par récurrence : si E est un espace vectoriel euclidien muni d'une base orthonormée (e1 , . . . , en ), si 1 , . . . , n sont des variables aléatoires de Rademacher indépendantes dans leur ensemble et si X = 1 e1 + · · · + n en , alors, pour tout convexe fermé non vide C de E, P(X C) · E exp d(X, C)2 /8 6 1 · Enfin, la troisième partie commence par quelques résultats préliminaires de probabilité, dont la difficulté consiste à réutiliser de nombreuses questions des deux premières parties. Elle s'achève par une mobilisation de tous ces résultats pour démontrer le théorème de Johnson­Lindenstrauss. Ce sujet est long et technique. Il permet de faire le point sur ses capacités à manipuler tous les outils du programme liés aux probabilités, tout en y mêlant un peu d'algèbre euclidienne et de calculs standards en analyse (inégalités). C'est également une bonne occasion d'apprendre à réutiliser des questions, parfois bien plus loin dans le problème. Indications Partie I 2 Poser a = (u - v)/2 et b = (u - v )/2 dans l'égalité de la question 1. 3 Montrer que l'ensemble {ku - wk | w F} admet une borne inférieure et utiliser la caractérisation séquentielle puis le théorème de Bolzano­Weierstrass. 4 Utiliser la convexité de C ainsi que la question 2 afin de prouver l'unicité. 6 En suivant l'indication de l'énoncé, utiliser la question 5 pour chaque terme de la somme définissant E (|XY|), puis la formule des probabilités totales. 8 À l'aide de la relation de Chasles, exprimer l'intégrale comme somme des intégrales yi ; yi+1 . sur tous les intervalles de la forme 10 Procéder par inclusion d'événements. 13 Justifier que le majorant de la question 12 est supérieur à 1 dans ce cas. Partie II 15 Expliciter d(X, u) à l'aide des coordonnées de u. 17 Combiner les questions 16 et 15. 20 Expliciter les deux éléments de C X() (ils reserviront également dans la suite du problème). 22 Montrer que Y-n - n en et Yn + n en appartiennent à C. 23 Pour la première inégalité, séparer les termes sur E et ceux sur Ren puis utiliser le théorème de Pythagore. Pour la deuxième, utiliser l'inégalité triangulaire puis une inégalité de convexité. 24 Utiliser le vecteur appartenant à C-1 puis l'indépendance des variables 1 , . . . , n . 25 Démontrer le lemme suivant : ( n-1 R × {-1; 1} - R Lemme : Soit F : une fonction quelconque. Alors (u, ) 7- F(u, ) E (F(X , n ) | n = -1) = E (F(X , -1)) puis conclure à l'aide de la linéarité et la croissance de l'espérance conditionnelle. 26 Combiner les questions 25 et 6. 27 La question 26 reste vraie en échangeant les rôles de 1 et -1. Appliquer ce résultat modifié à = 0. 28 Appliquer l'hypothèse de récurrence à C-1 puis la question 7. Conclure à l'aide des questions 26, 27 et 28. 30 On pourra dériver deux fois la fonction pour étudier son signe. 32 Combiner les questions 29, 31 et 21. 33 Utiliser l'inégalité de Markov et la question 32. Partie III 35 Détailler la valeur des normes et appliquer l'inégalité de Cauchy­Schwarz. 36 Écrire M · u = (M - N) · u + N · u, où N Mk,d (R) vérifie d(M, C) = kM - NkF . 37 Utiliser la contraposée de la question 36 et la question 33. 38 Noter g1 , . . . , gn les valeurs prises par g(X) et poser m = gi pour un entier i bien choisi. 39 Appliquer la question 37 à des réels particuliers dépendant de m et de t, puis la question 38. 40 Calculer l'espérance à l'aide de la question 8 et la majorer à l'aide de la question 39. 41 Développer g(X)2 et détailler le calcul de l'espérance en utilisant l'indépendance des variables ij et la valeur de la norme de u. 42 Il suffit de développer le carré dans l'espérance. 43 D'après la question 39, la variable aléatoire g(X) - m vérifie les hypothèses de la partie I.D avec a = 4 et b = 1/8. Noter alors g(X) - k = (g(X) - m) + m - k Vérifier les hypothèses sur à l'aide des questions 40 et 42 et conclure à l'aide des questions 12 et 13. 44 Détailler la probabilité et appliquer la question 43. 45 Poser uij = vi - vj kvi - vj k pour i 6= j C'est un vecteur unitaire de Rd . Réécrire Eij en fonction de ce vecteur afin de pouvoir appliquer la question 44. 46 Passer à l'événement contraire et exprimer le contraire d'une intersection en fonction de l'union des contraires. 47 Faire le lien avec les événements Eij . I. Préliminaires 1 Soit (a, b) E . La linéarité et la symétrie du produit scalaire donnent 2 ka + bk2 = ha + b | a + bi = kak2 + kbk2 + 2ha | bi et d'où ka - bk2 = ha - b | a - bi = kak2 + kbk2 - 2ha | bi (a, b) E2 ka + bk2 + ka - bk2 = 2 kak2 + kbk2 Ce résultat porte le nom d'égalité du parallélogramme. Il signifie que Dans un parallélogramme, la somme des carrés des longueurs des diagonales est égale à la somme des carrés des longueurs des quatre côtés. - - - - Par exemple, dans le schéma suivant dans R2 , si a = AB et b = AC, on a AD2 + BC2 = 2(AB2 + AC2 ) = AB2 + AC2 + CD2 + BD2 B - a D A - b C On peut justifier qu'une norme vérifie l'identité du parallélogramme si, et seulement si, elle est euclidienne (c'est-à-dire qu'elle provient d'un produit scalaire). C'est la caractérisation de Fréchet­Von Neumann­Jordan. 2 Soit (u, v, v ) E3 . Supposons v 6= v et ku - vk = ku - v k. Posons u-v u - v et b= 2 2 v + v v - v de sorte que a+b=u- et a-b= 2 2 Appliquons la question 1 à a et b : w w w w w w w ! w w2 w w v - v w2 w u - v w2 w u - v w2 v + v wu - w +w w w w w w w 2 w = 2 w 2 w +w 2 w w 2 w 1 1 2 =2 ku - vk2 + ku - v k 4 4 w w w w w2 w w v - v w2 v + v 2 wu - w +w w w w 2 w = ku - vk 2 w a= puisque ku - vk = ku - v k. Comme v 6= v , w w w w w2 w v - v w2 w w w >0 wu - v + v w < ku - vk2 donc w 2 w w 2 w La norme d'un vecteur étant positive, il vient, par croissance de la racine carrée, w w w w wu - v + v w < ku - vk w 2 w