2023-X-Ens-Psi-Corrigé

X-ENS — PSI — 2023

Notations et rappels

On note {\mathbb R_+} l’ensemble des réels positifs ou nuls, et {\mathbb R_+^*} celui des réels strictement positifs.
Une fonction continue sur un fermé borné non vide de {\mathbb R^n} y atteint son minimum.
Un sous-ensemble {C} d’un espace vectoriel réel est convexe si {(1-t)x+ty\in C} pour tous {x,y\in C} et {t\in[0,1]}.
Une fonction {f:C\to\mathbb R} est convexe si
{f((1-t)x+ty)\le(1-t)f(x)+tf(y).}Elle est strictement convexe si l’inégalité est stricte lorsque {x\ne y} et {0\lt t\lt1}.
Une fonction {f:A\times B\to\mathbb R} admet un point selle en {(a_*,b_*)} si, pour tous {a\in A} et {b\in B},
{f(a_*,b)\le f(a_*,b_*)\le f(a,b_*).}Toutes les variables aléatoires sont définies sur un même espace probabilisé {(\Omega,\mathcal F,P)}. Les parties I et II sont indépendantes.

I. Convexité et points selles

Soient {m,n\ge1} et {E} un espace vectoriel réel.
(1) Soit {C\subset E} convexe ; soient {f,g:C\to\mathbb R} convexes.

(2) Soit {A\in\mathcal M_{m,n}(\mathbb R)}. On utilise les produits scalaires usuels sur {\mathbb R^n} et {\mathbb R^m} ; {A^\top} désigne la transposée.

(3) Soit {U\subset\mathbb R^n} ouvert, {h:U\to\mathbb R} de classe {C^1}, et {b\in\mathbb R^m}. On suppose que {x_*\in U} minimise {h} sur
{V_b=\{x\in U:Ax+b=0\}.}

II. Entropie et codage

Soit {\mathcal X} un ensemble fini et {p=(p_x)_{x\in\mathcal X}} une loi de probabilité telle que {p_x\gt0} pour tout {x}. Son entropie est
{H(p)=-\sum_{x\in\mathcal X}p_x\ln p_x.}On pose {Q_{\mathcal X}=\{q\in\mathbb R^{\mathcal X}:q_x\ge0\}}.
Pour {q,q'\in Q_{\mathcal X}}, avec {q'_x\gt0} pour tout {x}, on définit
{\operatorname{KL}(q,q')=\sum_{x\in\mathcal X}q'_x\varphi(q_x/q'_x),}où {\varphi(t)=t\ln t-t+1} pour {t\gt0}, prolongée en {0} par continuité.

Soit {A} un ensemble fini. Un mot {u=u_1\cdots u_n} sur {A} est une suite finie d’éléments de {A}, de longueur {|u|=n}. Le mot vide {\epsilon} a longueur {0}.
On note {A^*} l’ensemble des mots et {A^+=A^*\setminus\{\epsilon\}}. La concaténation {u\cdot v} juxtapose les lettres, le mot vide étant neutre. Un mot {u} est un préfixe de {v} s’il existe {w\in A^*} tel que {v=u\cdot w}.
Soit {\mathcal X} fini non vide et {c:\mathcal X\to\{0,1\}^+} injective : c’est un code binaire. On suppose ce code préfixe : si {x\ne y}, {c(x)} n’est pas un préfixe de {c(y)}.
(5) On définit {\bar c:\mathcal X\to\{0,1\}^*} en retirant la première lettre : {c(x)=c(x)_1\cdot\bar c(x)}.

On pose {q_x=2^{-|c(x)|}}, et {X} est une variable aléatoire à valeurs dans {\mathcal X}, de loi {p}.

III. Transport régularisé

Dans la suite, {I,J} sont deux ensembles finis. Les familles {\alpha=(\alpha_i)_{i\in I}} et {\beta=(\beta_j)_{j\in J}} ont des coordonnées strictement positives et vérifient
{\sum_{i\in I}\alpha_i=\sum_{j\in J}\beta_j=1.}Elles définissent des lois de probabilités. On pose {E=\mathbb R^{I\times J}} et {Q=\{q\in E:q_{ij}\ge0\}}.
L’ensemble {F(\alpha,\beta)} est formé des {q\in Q} tels que
{\sum_{j\in J}q_{ij}=\alpha_i,\quad\sum_{i\in I}q_{ij}=\beta_j.}La famille {p}, définie par {p_{ij}=\alpha_i\beta_j\gt0}, appartient à {F(\alpha,\beta)}.

(8) Soient {X_1,X_2} deux variables aléatoires à valeurs respectives dans {I,J}.

Soient {C=(C_{ij})\in\mathbb R_+^{I\times J}} et {\varepsilon\gt0}. On définit sur {Q}{J_\varepsilon(q)=\sum_{i,j}q_{ij}C_{ij}+\varepsilon\operatorname{KL}(q,p),}où la divergence est celle de la partie II, avec {\mathcal X=I\times J}.

IV. Dualité

On pose {Q_{\gt0}=(\mathbb R_+^*)^{I\times J}} et, sur {Q_{\gt0}\times(\mathbb R^I\times\mathbb R^J)},
{\begin{array}{rl}\mathcal L(q,(f,g))&=J_\varepsilon(q)\\[8pt]&\displaystyle\quad+\sum_i f_i\left(\alpha_i-\sum_jq_{ij}\right)\\[8pt]&\displaystyle\quad+\sum_j g_j\left(\beta_j-\sum_iq_{ij}\right).\end{array}}

Soit {(f^0,g^0)\in\mathbb R^I\times\mathbb R^J}. Pour {k\ge0}, on définit
{g^{k+1}=g_*(f^k),\quad f^{k+1}=f_*(g^{k+1}).}La mention {\mathbb R^{I\times J}} pour le couple initial dans le sujet est une coquille de domaine : {f^0} est indexé par {I} et {g^0} par {J}.

(16) On suppose que {f^k_i\to f_i^\infty} et {g^k_j\to g_j^\infty} pour tous {i,j}. On note
{G_* =\sup_{(f,g)\in\mathbb R^I\times\mathbb R^J}G(f,g).}