Mines Maths 2 MP 2015

Thème de l'épreuve Norme d'une matrice aléatoire
Principaux outils utilisés variable aléatoire réelle, topologie, norme matricielle
Mots clefs matrice aléatoire, recouvrement de la boule unité

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


A 2015 MATH. II MP ÉCOLE DES PONTS PARISTECH, SUPAÉRO (ISAE), ENSTA PARISTECH, TÉLÉCOM PARISTECH, MINES PARISTECH, MINES DE SAINT-ÉTIENNE, MINES DE NANCY, TÉLÉCOM BRETAGNE, ENSAE PARISTECH (F ILIÈRE MP), ÉCOLE POLYTECHNIQUE (F ILIÈRE TSI). CONCOURS 2015 SECONDE ÉPREUVE DE MATHÉMATIQUES Filière MP (Durée de l'épreuve : 4 heures) L'usage d'ordinateur ou de calculette est interdit. Sujet mis à la disposition des concours : C YCLE I NTERNATIONAL, ENSTIM, TÉLÉCOM INT, TPE-EIVP. Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : MATHÉMATIQUES II - MP. L'énoncé de cette épreuve comporte 5 pages de texte. Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre. Norme d'une matrice aléatoire L'objectif de ce problème est d'étudier une inégalité de concentration pour la norme opérationnelle d'une matrice aléatoire dont les coefficients sont mutuellement indépendants et « uniformément sous-gaussiens ». Soit n un entier strictement positif. On identifie Rn à l'espace M n,1 (R) des vecteurs colonnes à n coordonnées réelles. Pour tout x = t (x 1 , . . . , x n ) dans Rn on note : s n X (x i )2 kxk = i =1 n n-1 © ª La sphère unité de R est notée S = x Rn , kxk = 1 . On identifie une matrice carrée M Mn (R) à l'endomorphisme de Rn canoniquement associé et on note (M ) l'ensemble de ses valeurs propres réelles. Les parties A, B et C sont mutuellement indépendantes. A. Norme d'opérateur d'une matrice Soit M Mn (R). 1) Montrer que S n-1 est un compact de Rn et en déduire l'existence de : © ª kM kop = max kM xk ; x S n-1 . 2) Montrer que l'application qui à M Mn (R) associe kM kop est une norme sur Mn (R). Montrer en outre que pour tous x et y dans Rn , on a l'inégalité kM x - M yk É kM kop kx - yk. ª © 3) Si M est symétrique, établir l'égalité kM kop = max || ; (M ) . On pourra commencer par le cas où M est diagonale. On note J n la matrice de Mn (R) dont tous les coefficients sont égaux à 1. 4) Déterminer les valeurs propres et les espaces propres de J n en précisant la dimension des espaces propres. En déduire la valeur de kJ n kop . Soit M = (M i , j )1Éi , j Én Mn (R). © ª 5) Démontrer l'inégalité kM kop Ê max |M i , j | ; 1 É i , j É n . 6) Etablir que : v un n uX X (M i , j )2 kM kop É t i =1 j =1 et donner une condition nécessaire et suffisante sur le rang de M pour que cette inégalité soit une égalité. 2 On note n l'ensemble des matrices M = (M i , j )1Éi , j Én de Mn (R) telles que |M i , j | É 1 pour tous i , j dans {1, . . . , n}. 7) Montrer que pour tout M n , kM kop É n. Caractériser et dénombrer les matrices M de n pour lesquelles kM kop = n. B. Variables aléatoires sous-gaussiennes Dans toute la suite du problème, toutes les variables aléatoires considérées sont réelles et discrètes, définies sur un espace probabilisé (, A , P ) . Soit > 0. On dit que la variable aléatoire X est -sous-gaussienne si : ³ 2 t 2 ´ ¡ ¢ t R, E exp(t X ) É exp . 2 exp(t ) + exp(-t ) . On rappelle la notation : ch(t ) = 2 ³t2 ´ 8) Montrer que pour tout t R, on a ch(t ) É exp . On pourra au préalable 2 établir le développement de la fonction ch en série entière sur R. 9) Soit t R. Démontrer que si x [-1, 1], on a l'inégalité de convexité : exp(t x) É 1-x 1+x exp(t ) + exp(-t ). 2 2 10) Soit X une variable aléatoire réelle bornée par 1 et centrée. Montrer que X est 1-sous-gaussienne. En déduire que, si X est une variable aléatoire bornée par > 0 et centrée, alors elle est -sous-gaussienne. 11) Soit X 1 , . . . , X n des variables aléatoires mutuellement indépendantes et P sous-gaussiennes, et µ1 , . . . , µn des nombres réels tels que ni=1 (µi )2 = 1. n X Montrer que la variable aléatoire µi X i est -sous-gaussienne. i =1 12) Soit X une variable aléatoire -sous-gaussienne et > 0. Montrer que pour tout t > 0 : ´ ³ 2 t 2 - t P (X Ê ) É exp 2 En déduire que : ³ 2 ´ P (|X | Ê ) É 2 exp - 2 . 2 Dans la suite du problème, on admet qu'une variable aléatoire X à valeurs P dans N est d'espérance finie si et seulement si la série P (X Ê k) converge et que, dans ce cas : + X E(X ) = P (X Ê k). k=1 3 13) Si X est une variable aléatoire à valeurs dans R+ , montrer que X est d'espérance finie si et seulement si la série de terme général P (X Ê k) converge et que, dans ce cas : + X k=1 P (X Ê k) É E(X ) É 1 + + X k=1 P (X Ê k). On pourra pour cela considérer la partie entière X . + X -s Pour tout s ]1, +[, on note (s) = k . k=1 14) Soit X une variable aléatoire -sous-gaussienne et > 0. Montrer que pout tout entier k > 0 : µ ¶ ³ 2 X 2 ´ P exp Ê k É 2k - 2 où on a posé = -2 -2 . En déduire que si < 1, la variable aléatoire ¡ ¢ ¡ 2 X 2 ¢ exp 2 est d'espérance finie majorée par 1 + 2 . 1 En particulier, en prenant = p et en utilisant l'inégalité 1 + 2(2) É 5 (que 2 l'on ne demande pas de justifier), on obtient immédiatement, et on l'admet, que si X est une variable aléatoire -sous-gaussienne, on a l'inégalité d'Orlicz : µ ³ X 2 ´¶ E exp É5 . 42 C. Recouvrements de la sphère © ª Si a Rn , on note B a,r = x Rn ; kx - ak É r la boule fermée de centre a et de rayon r . Soit K une partie compacte non vide de Rn , et soit > 0. 15) Montrer que l'on peut trouver un sous-ensemble fini A de K tel que : [ B a, K aA 2 On pourra raisonner par l'absurde en utilisant le théorème de BolzanoWeierstrass. 16) Soit un sous-ensemble de K tel que pour tous x, y distincts dans , kx - yk > . Montrer que est fini et que son cardinal est majoré par celui d'un ensemble A du type considéré à la question précédente. Si de plus est de cardinal maximal, montrer que : [ B a, K a 4 On admet l'existence d'une fonction µ, appelée volume, définie sur l'ensemble des parties compactes de Rn et vérifiant les propriétés suivantes. ¡ ¢ (i) Pour tout vecteur a de Rn et tout nombre réel r > 0, µ B a,r = r n . (ii) Pour toute famille finie K 1 , . . . , K m de compacts de Rn deux à deux disjoints, on a : ´ X ³[ m m µ µ(K i ). Ki = i =1 i =1 (iii) Pour tous compacts K , K de Rn , K K implique µ(K ) É µ(K ). Soit une partie finie de S n-1 telle que pour tous x,y distincts dans , kx -yk > . 17) Vérifier que les boules B a, pour a sont toutes contenues dans B 0,1+ . 2 2 ¢n ¡ . Montrer alors que le cardinal de est majoré par 2+ 18) Justifier l'existence d'une partie finie n de S n-1 , de cardinal majoré par 5n , et telle que : [ S n-1 B a, 1 an 2 D. Norme d'une matrice aléatoire 1 . 42 Soit n un entier strictement positif. On définit une famille de variables aléatoires réelles M i(n) , indexées par i , j {1, 2, . . . , n}, mutuellement indépendantes ,j ¢ ¡ . et -sous-gaussiennes. On note M (n) la matrice aléatoire M i(n) , j 1Éi , j Én On fixe un nombre réel > 0 et on pose = Si x S n-1 , on note y = M (n) x qui est ainsi un vecteur aléatoire dont les composantes y 1 , . . . , y n sont des variables aléatoires réelles. aléatoire y i est -sous19) Montrer que pour tout i {1, . .¡. , n}, la variable ¢ gaussienne. En déduire que E exp(kyk2 ) É 5n et que pour tout réel r >0: ¡ p ¢ ¡ 2 ¢n P kyk Ê r n É 5 e -r . 20) Soit n une partie de S n-1 vérifiant les conditions de la question 18). p Pour tout réel r > 0, montrer que kM (n) kop Ê 2r n implique l'existence p d'un a n tel que kM (n) ak Ê r n. En déduire que : ¡ p ¢ ¡ 2 ¢n P kM (n) kop Ê 2r n É 25 e -r . F IN DU PROBLÈME 5

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


 Mines Maths 2 MP 2015 -- Corrigé Ce corrigé est proposé par Kévin Destagnol (ENS Cachan) ; il a été relu par Juliette Brun Leloup (Professeur en CPGE) et Nicolas Martin (Professeur agrégé). Le sujet a pour objectif d'établir une « inégalité de concentration » de la forme a > 0 b > 0 P kMkop > a 6 b où M est une matrice aléatoire dont les coefficients sont mutuellement indépendants et « uniformément sous-gaussiens » et k · kop est une norme sur Mn (R) qui donne la valeur absolue de la plus grande valeur propre pour les matrices symétriques. Ce cadre d'étude intervient, en le généralisant, dans la technique d'analyse en composantes principales : on manipule des matrices de corrélation d'un échantillon de données, dont on cherche les éléments propres pour décrire, décorréler, débruiter... les données. Une inégalité de concentration apporte par exemple un outil statistique pour quantifier la validité des résultats obtenus. Le problème se compose de quatre parties ; les trois premières sont indépendantes et la dernière utilise les précédentes pour démontrer l'inégalité recherchée. · La première partie, très classique, mélange topologie et algèbre linéaire. Pour M Mn (R), la norme opérationnelle kMkop = max kMxk | x Sn-1 est introduite. On en établit quelques propriétés, on la compare aux normes usuelles sur Mn (R) et on calcule sa valeur sur les matrices symétriques. · La deuxième partie introduit la notion de variable aléatoire sous-gaussienne. Elle utilise des notions élémentaires d'analyse et de probabilités discrètes pour en étudier quelques propriétés. Une inégalité de concentration est établie pour ce type de variables aléatoires. · La troisième partie porte exclusivement sur la topologie de Rn . Il s'agit de démontrer que l'on peut recouvrir toute partie compacte par une union finie de boules fermées de rayon prescrit. Il s'agit de la partie la plus délicate du sujet. · La dernière partie montre l'inégalité de concentration recherchée. Elle nécessite d'avoir bien intégré le reste du sujet et d'avoir pris suffisamment de recul sur les résultats démontrés et admis. Globalement, le sujet est plutôt bien guidé et abordable, hormis la troisième partie qui demande des initiatives ­ mais le sujet énonce précisément tous les résultats utiles dans la suite. Par ailleurs, cette épreuve nécessite de maîtriser beaucoup de notions pour espérer en venir à bout. Les thèmes abordés vont en effet des probabilités discrètes à la topologie en passant par l'algèbre linéaire. Il constitue un bon problème de révision. Indications Partie A 1 Penser au fait qu'on est en dimension finie puis remarquer que, pour une matrice M Mn (R), l'application x 7 kMxk est continue sur Sn-1 . 2 Tirer parti du fait que pour tout x dans Rn non nul, le vecteur x/kxk est unitaire. 3 Pour passer du cas diagonal au cas général, se souvenir qu'une matrice symétrique réelle est diagonalisable en base orthonormée, de sorte que la matrice de passage est une matrice orthogonale (qui conserve par conséquent la norme). 4 Remarquer que Jn est symétrique puis déterminer son rang. En déduire une première valeur propre et sa multiplicité. Conclure en calculant ensuite l'image par Jn t du vecteur (1, . . . , 1). 5 Écrire, pour tout (i, j) [[ 1 ; n ]]2 , le coefficient Mi,j comme un produit scalaire puis majorer |Mi,j | grâce à l'inégalité de Cauchy-Schwarz. 6 Utiliser l'inégalité de Cauchy-Schwarz. 7 Se servir de la question 6 et se souvenir qu'une inégalité est une égalité si, et seulement si, toutes les inégalités écrites pour la démontrer sont des égalités. Pour dénombrer les matrices M n vérifiant kMkop = n, voir qu'une telle matrice est caractérisée par les coefficients de sa première colonne et les coefficients de proportionnalité entre la ie colonne et la première colonne pour tout i [[ 2 ; n ]]. Partie B 8 Comparer pour t R les développements en séries entières de ch (t) et exp t2 /2 . 9 Remarquer que, pour t R et x [ -1 ; 1 ], on a tx = 1+x 1-x t- t 2 2 et 1+x 1-x + =1 2 2 10 Se servir des questions 9 et 8 pour la première partie de la question. Puis, voir que X/ vérifie les hypothèses de la première partie de la question. 11 Utiliser la relation fonctionnelle de l'exponentielle : (x, y) R2 exp(x + y) = exp(x) exp(y) Se souvenir ensuite que pour deux variables aléatoires réelles indépendantes, on a E(XY) = E(X)E(Y). 12 Utiliser l'inégalité de Markov. Pour la deuxième partie de la question, remarquer que si X est -sous-gaussienne, il en est de même pour -X. 13 Revenir à la double inégalité définissant la partie entière et comparer les deux événements (X > k) et (X > k) pour tout k N . 14 Écrire, pour k N , l'événement exp 2 X2 /2 > k sous la forme d'un événement du type (|X| > K) pour un certain K > 0 puis utiliser les questions 12 et 13. Partie C 15 Remarquer qu'on peut traiter le cas où K est fini facilement. Dans le cas où K est infini, construire, en raisonnant par l'absurde comme le suggère l'énoncé, une suite (xn )nN de K vérifiant i 6= j kxi - xj k > 2 Aboutir à une contradiction en utilisant le théorème de Bolzano-Weierstrass. [ 16 Considérer un sous-ensemble A fini de K tel que K Ba, 2 . Établir alors par aA l'absurde que toute boule Ba, 2 avec a A contient au plus un point de . Pour la seconde moitié de la question, raisonner à nouveau par l'absurde. Pour contredire la maximalité, exhiber alors un sous-ensemble vérifiant la même propriété mais de cardinal strictement plus grand. 17 Pour la deuxième partie de la question, appliquer la fonction volume µ à l'inclusion [ Ba, 2 B0,1+ 2 a 18 Considérer la partie de N constituée de tous les Card () pour décrivant les sous-ensembles de K vérifiant i 6= j 2 kxi - xj k > pour un judicieusement choisi. Utiliser alors les questions 16 et 17. Partie D 19 Pour la deuxième partie de la question, établir que les variables aléatoires yi indexées par i [[ 1 ; n ]] sont mutuellement indépendantes. Pour la dernière partie de la question, utiliser l'inégalité de Markov. 20 Concernant le début de la question, raisonner par l'absurde et obtenir une contradiction en tirant parti du fait qu'il existe x Sn-1 tel que l'on ait l'égalité w (n) w w (n) w wM xw = wM w op Remarquer alors que la première partie de la question se traduit par l'inclusion w w [ w w w (n) w wM(n) w > 2rn a > r n wM w op an A. Norme d'opérateur d'une matrice 1 Soit M Mn (R). On note N l'application de Rn dans R définie par N : x 7 kxk. Par définition, on a alors Sn-1 = N-1 ({1}). Or, le singleton {1} est un fermé de R et N est continue (car 1-lipschitzienne). On en déduit que Sn-1 est un fermé de Rn . De plus, Sn-1 est borné par définition. Rn étant de dimension finie, La sphère unité Sn-1 est un compact de Rn . L'application de Rn dans lui-même définie par f : x 7 Mx est linéaire en dimension finie et par conséquent continue. Ainsi, l'application de Rn dans R définie par x 7 kMxk est continue en tant que composée d'applications continues. Sa restriction au compact Sn-1 est donc bornée et atteint ses bornes, si bien que La quantité kMkop = max kMxk | x Sn-1 est bien définie. 2 Commençons par établir que k.kop est une norme sur Mn (R). · Homogénéité : Soient R et M Mn (R). D'après la question 1, il existe x Sn-1 tel que kMkop = k(M)xk. Par homogénéité de k.k, il s'ensuit que kMkop = ||kMxk. Puis, par définition de k.kop et puisque || > 0, il vient kMkop 6 ||kMkop De même, la question 1 fournit l'existence d'un y Sn-1 tel que kMkop = kMyk. Ainsi, par homogénéité de k.k, on a ||kMkop = k(M)yk. Par définition de k.kop , cela entraîne l'inégalité ||kMkop 6 kMkop qui permet de conclure à l'égalité kMkop = ||kMkop . · Inégalité triangulaire : Soient M et N dans Mn (R). Pour tout x Sn-1 , en utilisant l'inégalité triangulaire pour k.k et la définition de k.kop , il vient k(M + N)xk = kMx + Nxk 6 kMxk + kNxk 6 kMkop + kNkop En passant au maximum sur tous les x Sn-1 , on aboutit à l'inégalité triangulaire kM + Nkop 6 kMkop + kNkop · Caractère défini : Soit M dans Mn (R) telle que kMkop = 0. Par définition de la norme opérationnelle, on a donc pour tout x Sn-1 , kMxk = 0. Par caractère défini de k.k, on en déduit que pour tout x Sn-1 , Mx = 0. Or, quel que soit z Rn non nul, z/kzk Sn-1 . D'où, M (z/kzk) = 0 puis par linéarité Mz = 0. Finalement, cela entraîne que M = 0Mn (R) . L'application qui à M Mn (R) associe kMkop est une norme sur Mn (R). Soient M Mn (R) et x, y dans Rn . Lorsque x = y, l'inégalité demandée est x-y évidente. Supposons donc x 6= y. Le vecteur est alors dans Sn-1 . Ainsi, par kx - yk définition de k.kop , on obtient w w w x-y w wM w 6 kMkop w kx - yk w Par linéarité de M et homogénéité de k.k, cela se réécrit kM (x - y) k 6 kMkop kx - yk d'où M Mn (R) 2 (x, y) (Rn ) kMx - Myk 6 kMkop kx - yk