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