X/ENS Maths PSI 2023

ECOLES NORMALES SUPERIEURES
ECOLE POLYTECHNIQUE

CONCOURS D'ADMISSION 2023

LUNDI 17 AVRIL 2023
08h00 - 12h00

FILIERE PSI

MATHEMATIQUES (XUSR)

Durée : 4 heures

L'utilisation des calculatrices n'est pas
autorisée pour cette épreuve

NOTATIONS ET RAPPELS

e On notera R, l'ensemble des réels positifs ou nuls et R' l'ensemble des réels 
strictement
positifs.

e On rappelle que si FC R" est un fermé borné et f : F -- KR est continue, 
alors le minimum
de f sur Fest atteint, c'est-à-dire qu'il existe x EUR F tel que f(x) < f(y) pour tout y EUR F. e joit Æ un espace vectoriel sur R. On dit que C EUR E est un ensemble convexe si pour tous x,yeC'et tout t E [0,1] on a (1 ---t)x +ty EC. Pour C EUR Æ convexe, une fonction f : C -- KR est dite convexe, si pour tous x, y élé- ments de C et tout t EUR [0,1}, on a f((1--t)x +ty) < (1 ---t)f(x) +tf(y). On dit que f est strictement convexe si cette inégalité est stricte pour t EUR]0, 1{ et x £ y. e Soient À et B deux ensembles et f : À x B -- KR. On dit que f admet un point selle en (az,b,) EUR À X B si pour tout (a,b)E Ax Bona fax, bd) < f(ax,b4) < f(a,b). e 'Toutes les variables aléatoires seront supposées définies sur un espace probabilisé commun (Q,F,P). Les parties I et IT sont indépendantes. I. CONVEXITÉ ET POINTS SELLES Soient m et n deux entiers positifs non nuls et Æ un espace vectoriel sur R. (1) Soient CC E un ensemble convexe. Soient f et g deux fonctions convexes de C' dans R. (a) Montrer que f + g est convexe, et strictement convexe s'il l'une des deux fonctions f ou g est strictement convexe. (b) On suppose f strictement convexe. Vérifier que le minimum de f est atteint sur C en au plus un point de C. (2) Soit À EUR M n(R) une matrice de m lignes et n colonnes. On note (u,v)rr le produit scalaire entre deux vecteurs u et v de R" et (u,17)Rm celui entre deux vecteurs u et de R7. (a) Montrer que pour tout (x,v) EUR R? x R",on a (Ax, v\rm = (x, Alvin, où A! désigne la matrice transposée de À. (b) En déduire que ker À EUR (Im A'})+ où £+ désigne l'orthogonal de Æ pour le produit scalaire sur R7 pour tout sous-espace vectoriel E de R?. (c) Montrer que ker A = (Im A')+ (3) On considère un ouvert U EUR KR", h : U -- R une application Cl et b EUR R'". On suppose qu'il existe x, EUR U un minimum de h sur l'ensemble V, = { x EU | Ax+b=0}. (a) Montrer que pour tout u EUR R" tel que Au = 0 on a (VA(x,),u)rr = 0 où VA(x) désigne le gradient de À en x. (b) Montrer l'existence de , EUR IR"? tel que Vh(x:) -- Al, = 0. (c) En déduire que l'application L : U x R" -- KR telle que L(x,v) = h(x) -- (v, Ax + b)rm vérifie DE (as, 4) = 0 pour tout 1 < k < n où DE (x, y) désigne la dérivée partielle de L par rapport à la k-ième coordonnées de x EUR R". 1 (d) Conclure que si U est convexe, et h convexe sur U, alors L admet un point selle en (x,, 1), c'est-à-dire que l'on a L(x,,v) < L(x,,v) < L(x, 14), pour tout (x,v) EU x R. II. ENTROPIE ET CODAGE Soient X un ensemble fini et p = (pPr)xex une loi de probabilité sur X. On suppose que p charge tous les points de X : p; > 0 pour tout x EUR X. On appelle entropie de 
p la quantité

H(p) = -- d Pr M(px) :

xEeX

On considère l'ensemble Qx = { q = (qr}rex EUR R'|Vx EX, qx > 0}. Pour tous 
q,q! EUR Qx
tels que q'. > 0 pour tout x EUR X, on définit :

KL(q, q') = ÿ_ +(qx/q,.),
xEX

avec & : R+ -- R définie par (x) = xlog(x) -- x +1 pour x > 0 et prolongée en 0 
par continuité.
(4) (a) Préciser (0).

(b) Vérifier que y est continue strictement convexe positive et que w(x) = 0 si 
et seulement

Si T = Î.

(c) Montrer que Qx est convexe et que q -- KL(q, q') est strictement convexe 
positive et

s'annule ssi g = q'.

Soit À un ensemble fini. On appelle mot sur À une suite finie d'éléments de À, 
on le note
u = u...un et n est la longueur du mot uw, notée [u|. Le mot vide est noté EUR, 
il est de longueur
nulle. On note A* l'ensemble des mots sur À et AT = A*\{e} l'ensemble des mots 
privé du mot
vide.

On définit la concaténation u - v de deux mots u,v EUR A* par ue = eE-u--=uet 
uv --
U1... Uju[U1 - +: Uly] Si U,U EUR AT. On dit que u est un préfixe de v si vu = 
u - w pour w EUR A*.

Soient X un ensemble fini non vide et EUR : X -- {0,1} une application 
ingjective. On dira que
cest un code binaire sur X. On suppose de plus que c est un code préfixe, c'est 
à dire que pour
tous x £ y dans X, c(x) n'est pas un préfixe de c(y).

(5) On définit EUR : X -- {0,1}* tel que pour tout x EUR X, c(x) = c(x)1 - C(x) 
où c(x)1 est le
premier élément du mot c(x).
(a) Vérifier que pour tout x £ y EUR X, si c(x)1 = c(y)1 alors C(x) À y) et 
C(x) n'est pas
un préfixe de c(y).

(b) Pour a EUR {0,1} on note X, = {x EUR X | c(x)1 = a}. Montrer que si X, 
contient au moins
deux éléments, alors la restriction de EUR à X, est un code préfixe sur X4.

(c) En déduire que D 4x 2-1) EUR 1, (Ind. : On pourra décomposer la somme en une

somme sur Xo et X1 et raisonner par récurrence sur L(c) = max{ [c(x)| | x E X})

Soient q -- (2 et À une variable aléatoire à valeurs dans X de loi p.

(6) (a) Vérifier que In(2)E(|c(X)|) = -- 5 ex Px M(qx).

(b) En déduire que E(|c(X)|) > TE

(nd. : On pourra chercher à exprimer In(2)E{(|c(x)|) en fonction de H(p) et 
KL(p, q))

III. TRANSPORT RÉGULARISÉ

Dans toute la suite 1 et J désignent deux ensembles finis.
e On considère à = (@;);ier EUR (Ri)' et B = (Bj);jey EUR (R*)" tels que 7 & -- 
D je P5 = 1
si bien que à et 5 peuvent être considérés comme définissant deux lois de 
probabilités sur
I et J.
e Dans la suite on notera
Q = { (Qijju,perxz EUR R'*" | qij > O0 pour tout (i,j)EURelI x J }
et
F(a,B)={aEUReQl d Gi -- à; et dd; -- B; pour tout (i,j) EI x J }.
j'EJ ET
On notera p l'élément de F(a, B) défini par pi; = @;B; > 0 pour tout (5,3) EUR 
I x J.
(7) Vérifier que F(a, B) est un ensemble convexe de l'espace vectoriel E -- R/*

(8) Soient X1 et X2 deux variables aleatoires telles que X, est à valeurs dans 
1 et X2 à valeurs
dans J.

(a) Vérifier que si q EUR Fa, 8), alors De D jes Qij = 1.
(b) On suppose que P(X1 = à, X2 = j) = q;; avec q EUR F(a,B). Calculer la loi 
de X3 et
celle de X2 en fonction de « et B.

(c) Que dire de X; et X2 lorsque q = p?
Soient C = (Cij)tijerxz EUR R°*7 et EUR > 0. On considère Je : Q -- R définie 
par
J(q) = S dijCi + eKL(q,p)
1j
où KL(q, p) est défini dans la partie précédente en prenant X = 1 x J.
(9) Montrer que J. est strictement convexe sur Q.
(10) (a) Vérifier que F(a@, B) est un fermé borné de R!*".
(b) Montrer qu'il existe un unique q(e) EUR Q minimisant J- sur F(a, B).

(c) En considérant un contre-exemple simple, montrer que l'unicité n'est plus 
vraie si on

suppose que EUR = Ü.

(11) (a) Vérifier que q(e);; > 0 pour tout (4,3) EUR I xX J (Ind : On pourra 
raisonner par l'absurde
et considérer pour tout t EÏ0, 1] q(e,t) = (1 --t)q(e) +tp puis observer le 
comportement
de Y(x) au voisinage de x = 0).

(b) Montrer que ceci n'est plus vrai si on suppose que EUR = 0.

IV. DUALITÉ
On définit Q=0 = (Ri)/*7 et Z : Q=o x (R! x R°) +R défini par
Z(gq,(f,g)) = Je(g) + D fito -- d di) + D g5(B -- d_ di)
CI JET JEJ iCI
(12) (a) Vérifier que Q=0 est un ouvert convexe R/*".
(b) Montrer qu'il existe (f(e), g(e)) EUR R! x R° tel que Z(q(e), (f(e), g(e)) 
est un point selle
de Z. (Indication : On pourra identifier R!*7 avec R" et R! x R? avec R" pour n

cardinal de T X J et m somme des cardinaux de TI et J puis utiliser la question 
3 de la

partie I.)
(13) (a) Montrer que pour tout (f,g) EUR R? x R°, le minimum de gr Z(q,(f,g)) 
sur Q0 est
atteint en q(f, gi; = edi+95-Gis) lp.

(b) Calculer la valeur de G{(f, g) = Z(q(f,g),(f,g)).
(c) Vérifier que G est concave sur R! x R'.
(14) Vérifier que si f, : R7 -- R? et g, : R? -- R' sont définies par
Pa(g}i = --elog() et 068,) et ga (f); = --elog(> ea)

jEJ iel

I J 0G __ôG EL .
alors pour tout (f,g) EUR R° x R°, on à 55 (f:(9),9) -- 09; (f,gx(f)) = 0 pour 
tout (4,3) EUR
TX J.

Soit (f9,g°) EUR R!*7. Pour tout 4 > 0, on considère
go -- ga(f") et f"*? -- f(g°)
(15) Montrer que la suite (G(f*,g"))>0 est croissante.

(16) On suppose qu'il existe f® = (fier et g®° = (9% )jes tel que |fF--f>%] -- 
0 et gi gs --
0 pour tous à EUR I et j EUR J. On note G, = sup{ G(f,g) | (f,g9) ET xXJ }.

(a) Montrer que G(f%,g°%°) = Gx.
(b) Montrer que G(f(e),g(e)) = Gx.

(c) Montrer qu'il existe une constante a EUR R telle f(e); = fÿ° + a et g(e); 
-- gÿ° -- a pour
tout (4,3) EUR I x J.

(d) En déduire que q(f",g") -- q(e).