X/ENS Maths PC 2019

Thème de l'épreuve Principe du maximum, étude de grandes déviations, reconstruction à partir d’observations bruitées
Principaux outils utilisés Matrices, étude de fonctions, nombres complexes, probabilités, analyse de première année, polynômes, probabilités
Mots clefs matrices unitaires, probabilités sur des ensembles finis, Bernoulli, observation bruitée, échantillon

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


ECOLE POLYIECHNIQUE - ESPCI
ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2019

JEUDI 18 AVRIL 2019 - 8h00 - 12h00
FILIERE PC - Epreuve n° 1

MATHEMATIQUES
(XEULC)

Durée : 4 heures

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Les quatre parties sont indépendantes entre elles.

Dans l'ensemble du sujet, pour répondre à une question, on pourra admettre les 
résultats des questions
précédentes.

Notations

Dans l'ensemble du sujet m et n désignent des entiers strictement positifs. 
L'ensemble C désigne le corps
des nombres complexes. Le module d'un nombre complexe z est noté |z| et son 
conjugué est noté z. On
note D={zeC:12| <1} le disque unité fermé, et S={z2eC:12| =1}. On note Myn(C) l'ensemble des matrices à m lignes et à n colonnes à coefficients dans EUR et M,(C) = Mnn(C) l'ensemble des matrices à n lignes et à n colonnes à coefficients dans C. On note I, la matrice identité de MA(C). La matrice transposée d'une matrice À EUR Myn(C) est notée AT. Si À = (a; j)o 1. On 
considère un nombre
complexe z EUR D et on définit les matrices M EUR Mh41(C) et P EUR Myr11(C) par

[2 0 O0 :.. 0 1--[:P) Ne Ne
Vi=EE 0 0. 0 -Z 2 :
0 1 0 :.. 0 0 or 0 0 0 N
UM 0 0 1 '+ 0 0 E |
. . ! 1
: 0
0 0
| 0 0 0 1 0
et
1
0
P=|.
0

5. Montrer que M est une matrice unitaire.
6. Montrer que 26 -- PTMFP pour tout entier 0  l'un entier et A(z) = 5Y2, axz* un polynôme non nul tel 
que ax EUR {--1,0,1}
pour tout 0 < k £ n -- 1. Alors pour tout entier L >lona

1
SUP | A(e))] Z L=-1.
0E[-7,7] "0
Pour démontrer ce résultat, on fixe un entier n > 1 et A(z2) = YY2$ axz* un 
polynôme tel que ax EUR

{--1,0,1} pour tout 0 < k < n -- 1. On fixe également un entier L > 1.
9. Size C vérifie |2| = 1, montrer que |[A(z)| < n. 10. On suppose dans cette question que ao = 1, et on pose, pour tout z EUR C, L--1 dir; F(2) = IT 4 (se L ) | a. Montrer qu'il existe 20 EUR C tel que |20| = 1 et |F(20)| > 1.

b. Montrer que [F(20)| & 1 un entier et soit S,, une somme 
de n variables aléatoires
à valeurs dans {0,1} mutuellement indépendantes de Bernoulli de paramètre p. 
Alors

S (p--a)?
Dm -r)) < es. Sn T T Pour démontrer ce résultat, on fixe p, q EUR [0,1] et (X;)1 0.

a. Montrer que g est bien définie et de classe C° sur R.. Pour x > 0, exprimer 
g/(x) sous la
forme 7: où «à et 5 sont des réels positifs pouvant dépendre de x.
b. Montrer que g"(x) < + pour tout æ > 0.

c. Montrer que
2

x
In(1 ---p+pe") < px + TR Pour tout x > 0.
13. On suppose dans cette question que p < q. a. Justifier que Sn Sn n n b. Soit X une variable aléatoire de Bernoulli de paramètre p. Pour u > 0, 
calculer E(e"*).

c. Montrer que pour tout u > 0,

Indication. On pourra admettre que si (Z;)1<;5en sont n variables aléatoires réelles mutuelle- ment indépendantes et prenant un nombre fini de valeurs, alors E(T[;_, Zi) = II; E(Z;). 2 _n (p--a) d. Montrer que P(S,, > Pin) Ze 2

14. Démontrer le Théorème 3.
Quatrième partie

Dans cette partie, on s'intéresse à la reconstruction d'une suite de 0 ou 1 à 
partir d'un échantillon
d'observations bruitées (on pourra utiliser le Théorème 2 et le Théorème 3).

Plus précisément, étant donné un élément æ = (x%0,...,4n-1) EUR {0,1}", appelé 
la source, et un paramètre
p EUR [0,1] fixé, on considère la variable aléatoire O(x) à valeurs dans {0,1} 
construite comme suit :

-- soient (B;)o 1 --
b. Montrer que Un < j+1et1; =k)=p Cri -- pi.

b. Montrer que, pour tout 0 < j  ---

nm
b. Démontrer que |
eo --(1--p)|
D

p
> 1.
7 nln-1

S_ [E(O,(x)] - E(O,(y)]| |
j=--0

c. Justifier l'existence d'un entier 7, (x, y) tel que 0 < jn(x,y) < n -- 1 et p | 1-p 7 | EXP | ----  --n |. n£n 2p? I? Dans la suite, on fixe une fois pour toutes un entier n qu'il faut considérer comme étant très grand. Pour chaque couple (x,y) EUR ({0,1}")° tel que x £ y, on fixe un entier 7,(x,y) dont l'existence est prouvée dans la question 17c. Soient T >1et (E',E°,...,E") EUR ({0,1}")". Ainsi, pour 1  e alors pour tout x EUR {0,1} et toute suite

Ol(x), O°(x),...,O"(x)

de 7} variables aléatoires à valeurs dans {0,1}° mutuellement indépendantes de 
même loi que
O(x), on a
max P (R, T. (O'(x). O*(x),...... O7"(x)) L r) < Un xEe{0,1}"7 | OÙ (Un)n>1 est une suite tendant vers 0 lorsque n tend vers l'infini.

Indication. On pourra commencer par écrire, en le justifiant, que

P (Rrr(O (x), O(x)......,OT(x)) Z r)

< > P (x n'est pas meilleur que y compte tenu de O'(x), O*(x), ... O"(x))

ye{0,1}"
VFX

On a donc démontré qu'en partant de x EUR {0,1} inconnu, on peut retrouver x à 
partir de la donnée
d'une suite

Ol(x), O'(x),...,O!(x)

de T' variables aléatoires à valeurs dans {0,1}"" mutuellement indépendantes de 
même loi que O(x)

(qui représentent la donnée de T' échantillons bruités obtenus à partir d'une 
même source), avec grande

3In(n})n1/3

probabilité à partir de e échantillons différents.

* *X *

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



X/ENS Maths PC 2019 -- Corrigé
Ce corrigé est proposé par Thierry Limoges (professeur en CPGE) ; il a été relu
par Sélim Cornet (ENS Paris-Saclay) et Benjamin Monmege (enseignant-chercheur
à l'université).

Dans ce sujet, on étudie des propriétés sur les modules de polynômes à 
coefficients
complexes, que l'on applique ensuite pour obtenir des inégalités dans le 
domaine des
probabilités. Il est composé d'une partie préliminaire puis de quatre parties 
quasiment
indépendantes. Chacune des parties 1 à 3 démontre un théorème à utiliser dans 
les
suivantes.
· La partie préliminaire définit les matrices unitaires et présente 
quelques-unes
de leurs propriétés.
· Dans la première partie, on montre que le module maximum d'un polynôme à
coefficients complexes sur le disque unité est atteint sur le bord, en utilisant
des matrices unitaires.
· Dans la seconde partie, on minore le module d'un polynôme à coefficients
dans {-1 ; 0 ; 1} sur un arc du cercle unité.
· Dans la troisième partie, on majore la probabilité qu'une moyenne de variables
aléatoires mutuellement indépendantes, suivant une loi de Bernoulli, s'éloigne
de son espérance en utilisant l'inégalité de Markov.
· Enfin, dans la quatrième partie, on cherche à reconstituer avec grande 
probabilité un mot binaire x à partir d'un grand nombre d'observations bruitées 
O(x).
Curieusement, ce sujet utilise exclusivement des outils de première année : 
matrices, inégalités, étude de fonctions simples, intégration d'inégalités, 
probabilités sur
des ensembles finis. Il est de difficulté progressive, balaye un large spectre 
de chapitres
et fournit une bonne révision entre les deux années de prépa.

Indications
1 S'inspirer de l'écriture matricielle du produit scalaire dans un espace 
euclidien.
2 Utiliser la question 1 et la définition d'une matrice unitaire.
3 Montrer séparément les deux inégalités.
4 Montrer que si U est unitaire, alors U-1 également. Montrer séparément les
deux inégalités.
t

5 Effectuer le calcul M M = In+1 .
6 Remarquer que multiplier une matrice par P à droite revient à en prendre la
t
première colonne, et que multiplier par P à gauche revient à en prendre la
première ligne.
7 Utiliser la bilinéarité du produit matriciel, puis la définition de la norme 
d'une
matrice dans l'énoncé.
8 Écrire M = UDU-1 avec U unitaire, vérifier que f (M) = Uf (D)U-1 et utiliser
la question 3.
9 Utiliser l'inégalité triangulaire.
10.a Utiliser le théorème 1.
2ij

10.b Montrer qu'un des z0 e L pour 0 6 j 6 L-1 possède un argument appartenant
à l'intervalle [ -/L ; /L ], puis utiliser la question 9.
11 Utiliser les questions 10.a et 10.b pour le cas a0 = 1, puis s'y ramener 
pour les
autres cas.
12.a Calculer successivement g  (x) et g  (x).
12.b Effectuer un changement de coordonnées polaires pour exprimer g  (x).
12.c Intégrer des inégalités.
13.a Raisonner géométriquement pour observer que pour tout x  R,
|x - q| 6 |x - p| si et seulement si x >

p+q
2

13.b Utiliser le théorème du transfert.
13.c Appliquer l'inégalité de Markov à la variable aléatoire e uSn .
13.d Mettre à profit les questions 12.c et 13.c.
14 Utiliser les questions 13.a et 13.d si p < q. Sinon, considérer les variables aléatoires Xi = 1 - Xi . 2 15.b Se servir de la relation |z| = zz et de la question 15.a. 16.a Décrire l'événement (N > j + 1 et Ij = k) par la phrase « le j-ième 1 dans 
la
suite (B0 , . . . , Bk ) est obtenu au rang k ».
16.b Utiliser que Oj (x) = 1 si et seulement si N > j + 1 et xIj = 1.
16.c Faire appel à la linéarité de l'espérance.
17.a Invoquer le théorème 2.
17.b Utiliser l'inégalité triangulaire et la question 17.a avec w bien choisi.
17.c Raisonner par l'absurde et contredire le résultat de la question 17.b.
18 Utiliser la sous-additivité d'une probabilité pour montrer l'indication 
fournie
par l'énoncé, puis la question 17.c et le théorème 3.

Préliminaires
1 Soit x  Cn , de coordonnées (x0 , . . . , xn-1 ). Calculons le nombre 
complexe suivant, vu comme un élément de M1 (C)
t

xx =

n-1
P

xi xi =

i=0

Ainsi,

n-1
P

|xi |2 = kxk2 2

i=0

t

x  Cn

x x = kxk2

2

t

2 Soit x  Cn . D'après la question 1 et comme U U = In , on a
2

t

t

t

t

t

kUxk2 = Ux Ux = x U Ux = x In x = x x = kxk2

2

Comme ces nombres sont positifs, on obtient
x  Cn

kUxk2 = kxk2

3 Remarquons d'abord que les normes des matrices sont bien définies. En effet, 
la
norme 2 est la racine carrée d'une fonction polynomiale en les coordonnées de 
Cn ,
donc continue, et on considère cette fonction sur Sn = {x  Cn | kxk2 = 1} qui 
est
un ensemble fermé et borné de l'espace vectoriel normé Cn . Celle-ci est donc 
bornée
et atteint ses bornes, ce qui prouve l'existence de la borne supérieure.
La norme sur Mn (C) est appelée norme subordonnée.
t

Pour tout x = (x0 , . . . , xn-1 )  Cn avec kxk2 = 1, comme D = diag(d0 , . . . 
, dn-1 ),
t
on a Dx = (d0 x0 , . . . , dn-1 xn-1 ). Posons M = max06i6n-1 |di |  R+ et 
calculons
2

kDxk2 =

n-1
P

di xi di xi =

i=0

Ainsi,

n-1
P

2

2

|di | |xi | 6

i=0

n-1
P

2

2

M2 |xi | = M2 kxk2 = M2

i=0

kDk = Sup kDxk2 6 M
xSn
t

Soit i0  [[ 0 ; n - 1 ]] vérifiant |di0 | = M. Pour y = (0, . . . , 0, 1, 0, . 
. . , 0) avec
t
un 1 au rang i0 et des 0 ailleurs, on a y  Sn et Dy = (0, . . . , 0, di0 , 0, . 
. . , 0),
2
2
d'où kDyk2 = |di0 | = M2 et kDyk2 = M. On obtient
kDk = Sup kDxk2 > kDyk2 > M
xSn

Finalement,

kDk =

Max |di |

06i6n-1

4 Soit U  Mn (C) avec U unitaire vérifiant B = UAU-1 . Remarquons que U-1 est
également unitaire car

t
t -1
U-1 = U
En effet, pour M  Mn (C), d'après le cours

t

M-1 =

t

M

-1

M-1 × M = M-1 M = In = In
la conjugaison dans C commutant avec les additions et les multiplications.

-1

, et M-1 = M

car

Pour x  Sn , d'après la question 2, kU-1 xk2 = kxk2 = 1 et
kBxk2 = kUAU-1 xk2 = kAU-1 xk2 6 kAk
car kU-1 xk2 = 1. Ceci étant vrai pour tout x  Sn , on a kBk 6 kAk. Par 
symétrie,
comme A = U-1 BU, on a kAk 6 kBk.
Si B = UAU-1 avec U unitaire, alors kBk = kAk.

Première partie
5 Pour k  [[ 2 ; n ]], le coefficient mk+1,k de M à la (k + 1)-ième ligne et la 
k-ième
colonne vaut 1, puisque c'est le coefficient diagonal du bloc In-1 . Notons
q

2
z
1 - |z| 0 · · · 0

0
0

t

..
..
N= M=

.
.
In-1

0
q 0

2
1 - |z|
-z
0 ··· 0
On a de même nk,k+1 = 1 pour k  [[ 2 ; n ]]. On obtient

q
2
2
zz
+
1
-
|z|
0 ···
0

0
1
0

t
..
..
..
MM = 
.
.
.

0
1
0

q

2
2
0
···
0
1 - |z| + zz
car zz +

 = In+1

q
2
2
2
2
1 - |z| = |z| + 1 - |z| = 1 et pour k  [[ 2 ; n ]],
n
P

nk, m,k = nk,k+1 mk+1,k = 1

=0

les autres calculs étant des sommes de 0. Ainsi, M est inversible et M-1 =
t
d'où M M = In+1 également. En conclusion,

t

M,

La matrice M est unitaire.
Les matrices unitaires interviennent dans le cadre des espaces hermitiens, qui
sont l'analogue des espaces euclidiens pour des espaces vectoriels complexes
de dimension finie.