Cours et vidéos

Cours en ligne Vidéos classées

Concours corrigés

HECS
HECE

Programme de concours

HECS

Chaîne Youtube


Pour me soutenir



Autour du site

Auteur du site.
Cours particuliers.


Partie II. Transport optimal dans une situation déterministe


Dans toute cette partie, $N$ dsigne un entier supérieur ou égal à 2.

On considère $N$ réels $d_1,d_2,\dots,d_N$ (appelés points de départ) et $N$ réels $a_1,a_2,\dots,a_N$ (appelés points d'arrivée) vérifiant $d_1<\! d_2<\! \dots<\! d_N$ et $a_1<\! a_2<\! \dots<\! a_N$.

On pose : $D=\{d_1,d_2,\dots,d_N\}$ et $A=\{a_1,a_2,\dots,a_N \}$.

8.a) Montrer que pour tout couple $(k,l)\in[\![1,N]\!]^2$, on a : $d_ka_k\geq d_ka_l+d_la_k-d_la_l$.

Afficher

Référence programme : I-3.

Si $k\geq l$ alors $d_l-d_k\leq 0$ et $a_l-a_k\leq 0$, par conséquent $(d_l-d_k)(a_l-a_k)\geq 0$. De la même manière on montre que si $k\leq l$ on a aussi $(d_l-d_k)(a_l-a_k)\geq 0$. Donc dans tous les cas on a $(d_l-d_k)(a_l-a_k)\geq 0$. Il ne reste plus qu'à développer cette dernière inégalité et organiser pour trouver l'inégalité recherchée.

b) En déduire à l'aide d'une double sommation que pour tout $N$-uplet $(p_1,p_2,\dots,p_N)\in\mathbb R_+^N$ tel que $\sum_{k=1}^Np_k=1$, on a : $$\sum_{k=1}^Np_kd_ka_k\geq\left(\sum_{k=1}^Np_kd_k\right)\times\left(\sum_{k=1}^Np_ka_k\right)\ (1)$$

Afficher

Référence programme : I-1,3.

On multiplie l'inégalité de la question précédente par $p_kp_l$ puis on double somme sur $k$ et $l$. Grâce au fait que $\sum_{k=1}^Np_k=1$, on a : $$\begin{align} &\sum_{k=1}^N\sum_{l=1}^Np_kp_ld_ka_k\geq \sum_{k=1}^N\sum_{l=1}^Np_kp_l(d_ka_l+d_la_k-d_la_l)\\ &\Longleftrightarrow \sum_{l=1}^Np_l \sum_{k=1}^Np_kd_ka_k\sum_{k=1}^Np_kd_k\geq \sum_{k=1}^Np_kd_k\sum_{l=1}^Np_la_l+\sum_{k=1}^Np_ka_k\sum_{l=1}^Np_ld_l-\sum_{k=1}^Np_k\sum_{l=1}^Np_ld_la_l\\ &\Longleftrightarrow \sum_{k=1}^Np_kd_ka_k\geq \sum_{k=1}^Np_kd_k\sum_{l=1}^Np_la_l+\sum_{k=1}^Np_ka_k\sum_{l=1}^Np_ld_l-\sum_{l=1}^Np_ld_la_l. \end{align}$$ Il ne reste plus qu'à réorganiser et à changer le noms des indices de sommation pour obtenir le résultat recherché.

9. Soit $t\in{\cal E}_N$. On réordonne la liste $(t(1),t(2),\dots,t(N))$ selon les valeurs croissantes et on note alors $(\hat t(1),\hat t(2),\dots,\hat t(N))$ la liste ordonnée obtenue. On a donc $\hat t(1)\leq\hat t(2)\leq\dots\leq\hat t(N)$.

a) Justifier pour tout $n\in[\![1,N]\!]$, l'inégalité : $\sum_{k=n}^Na_{t(k)}\leq\sum_{k=n}^Na_{\hat t(k)}$.

Afficher

Références programme : I-1,3.

On observe que si on prend la somme des $p$ plus grand éléments parmi une liste donnée, cette somme sera plus grande qu'une somme quelconque d'autres éléments. Ici, comme $(a_1,\dots,a_N)$ est ordonée et que $(\hat t(1),\dots,\hat t(N))$ aussi, $\sum_{k=n}^Na_{\hat t(k)}$ est donc la somme des $N-n+1$ plus grand éléments de $(a_{t(1)},\dots,a_{t(N)})$ ce qui justifie l'inégalité.

b) On pose $d_0=0$. Justifier l'égalité : $\sum_{n=1}^Nd_na_{t(n)}=\sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\right)$.

Afficher

Référence programme : I-1.

On a $$\begin{align} \sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\right)&= \sum_{n=1}^Nd_n\sum_{k=n}^Na_{t(k)}-\sum_{n=1}^Nd_{n-1}\sum_{k=n}^Na_{t(k)}\\ &=\sum_{n=1}^Nd_n\sum_{k=n}^Na_{t(k)}-\sum_{n=0}^{N-1}d_{n}\sum_{k=n+1}^{N}a_{t(k)}\text{ (par changement d'indice)}\\ &=d_Na_N+\sum_{n=1}^{N-1}d_n\sum_{k=n}^Na_{t(k)}-\sum_{n=1}^{N-1}d_{n}\sum_{k=n+1}^{N}a_{t(k)}\text{ (on rapelle que }d_0=0)\\ &=d_Na_N+\sum_{n=1}^{N-1}d_n\left(\sum_{k=n}^Na_{t(k)}-\sum_{k=n+1}^{N}a_{t(k)}\right)\\ &=d_Na_N+\sum_{n=1}^{N-1}d_na_{t(n)}\\ &=\sum_{n=1}^{N}d_na_{t(n)} \end{align}$$

c) Etablir l'inégalité : $\sum_{n=1}^Nd_na_{t(n)}\leq\sum_{n=1}^Nd_na_{\hat t(n)}\ (2).$

Afficher

Références programme : I-1,3.

Puisque les $d_n$ sont strictements ordonnés, on a $(d_n-d_{n-1})>0$, par conséquent d'après 9.a), on a $(d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\leq (d_n-d_{n-1})\sum_{k=n}^Na_{\hat t(k)}$. Il suit alors par 9.b) $$\sum_{n=1}^Nd_na_{t(n)}=\sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\right)\leq \sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{\hat t(k)}\right)=\sum_{n=1}^Nd_na_{\hat t(n)},$$ et le résultat est prouvé.

On appelle programme de transport, toute bijection $T$ de $D$ sur $A$, et coût d'un programme de transport $T$, la somme $c(T)$ définie par : $c(T)=\sum_{k=1}^N(d_k-T(d_k))^2$.

10. Soit $\hat T$ le programme de transport défini par : pour tout $k\in[\![1,N]\!],\ \hat T(d_k)=a_k$.

Déduire des questions précédentes que le programme $\hat T$ est optimal, c'est à dire que pour tout programme de transport $T$, on a : $c(T)\geq c(\hat T)$.

Afficher

Références programme : I-1,3,4.

D'abord on développe : $$c(T)=\sum_{k=1}^N(d_k-T(d_k))^2=\sum_{k=1}^Nd_k^2-2\sum_{k=1}^Nd_kT(d_k)+\sum_{k=1}^N(T(d_k))^2.$$ $T$ étant une bijection et l'ordre ne comptant pas dans la sommation de $\sum_{k=1}^NT(d_k)$, nous avons : $$\sum_{k=1}^N(T(d_k))^2=\sum_{k=1}^Na_k^2=\sum_{k=1}^N(\hat T(d_k))^2.$$ D'autre part, $T$ étant une bijection, le n-uplet $(T(d_1),\dots,T(d_n))$ peut être représenté à l'aide des notations du dessus $(a_{t(1)},\dots,a_{t(n)})$ et le n-uplet $(\hat T(d_1),\dots,\hat T(d_n))$ par $(a_{\hat t(1)},\dots,a_{\hat t(n)})$, de sorte que 9.c) nous donne l'inégalité suivante : $$\sum_{k=1}^Nd_kT(d_k)=\sum_{k=1}^Nd_ka_{t(k)}\leq \sum_{k=1}^Nd_ka_{\hat t(k)}=\sum_{k=1}^Nd_k\hat T(d_k).$$ On a finalement : $$c(T)=\sum_{k=1}^Nd_k^2-2\sum_{k=1}^Nd_kT(d_k)+\sum_{k=1}^N(T(d_k))^2\geq \sum_{k=1}^Nd_k^2-2\sum_{k=1}^Nd_k\hat T(d_k)+\sum_{k=1}^N(\hat T(d_k))^2=c(\hat T),$$ d'où le résultat.

11. Interprétation probabiliste des inégalités (1) et (2).

Soit $h$ une application croissante de $\mathbb R$ dans $\mathbb R$.

a) En utilisant l'inégalité (1), établir pour toute variable aléatoire discrète $X$ ne prenant qu'un nombre fini de valeurs, l'inégalité : $E(Xh(X))\geq E(X)E(h(X))$.

Afficher

Référence programme : I-3.

Si on note $a_1,\dots,a_n$ les valeurs distinctes prises par $X$ et qu'on les suppose ordonnée dans l'ordre croissant (donc strictement croissant car les $a_i$ sont distincts), on se trouve dans le champs d'application de (1). D'autre part si on note, $d_i=h(a_i)$, comme $h$ est croissante, les $d_i$ sont également ordonnée dans l'ordre croissant. On observe en reprenant la démonstration de (1) que l'inégalité reste vraie en supposant un ordre large des $d_i$, c'est à dire $d_1\leq\dots\leq d_n$. Donc notre choix des $d_i$ est encore dans le champs d'application de (1). Enfin si on pose $p_i=P(X_i=a_i)$, on a bien $\sum_{k=1}^np_i=1$ et on est encore bien dans le champs d'application de (1). On a enfin avec le théorème de transfert et (1) que : $$\begin{align} E(Xh(X))&=\sum_{k=1}^na_kh(a_k)P(X=a_k)\\ &=\sum_{k=1}^na_kd_kp_k\\ &\geq\left(\sum_{k=1}^np_kd_k\right)\left(\sum_{k=1}^np_ka_k\right)\\ &=\left(\sum_{k=1}^nh(a_k)P(X=a_k)\right)\left(\sum_{k=1}^na_kP(X=a_k)\right)\\ &=E(h(X))E(X) ,\end{align}$$ ce qui prouve le résultat.

b) Que peut-on en déduire pour le coefficient de corrélation linéaire de $X$ et $h(X)$ lorsque les variances de $X$ et $h(X)$ sont strictement positives?

Afficher

Référence programme : VII-21.

Les variances de $X$ et $h(X)$ existent donc le coefficient de corrélation linéaire est bien défini. D'après 11.a) : $$\rho(X,h(X))=\frac{Cov(X,h(X))}{\sqrt{V(X)V(h(X))}}=\frac{E(Xh(X))-E(X)E(h(X))}{\sqrt{V(X)V(h(X))}}\geq 0,$$ donc le coefficient de corélation linéaire est positif.

c) En utilisant l'inégalité (2), montrer que si $X$ est une variable aléatoire discrète suivant la loi uniforme sur $[\![1,N]\!]$ et $t$ un élément de ${\cal E}_N$, on a : $E(h(X)t(X))\leq E(h(X)\hat t(X))$.

Afficher

Référence programme : VII-6.

Par la formule de transfert $$E(h(X)t(X))=\sum_{k=1}^Nh(k)t(k)\frac{1}{N}=\frac{1}{N}\sum_{k=1}^Nh(k)t(k).$$ Si on pose $d_k=h(k)$, par croissance de $h$, on observe que les $d_k$ sont ordonnés par ordre croissants. En reprenant la preuve de (2), on observe que l'inégalité reste vraie si on suppose les $d_k$ ordonnés au sens large, par conséquent les $d_k$ posés précédemments sont dans le cadre d'application de (2). D'autre part si on pose $a_{t(n)}=t(k)$, on a d'après (2) : $$E(h(X)t(X))=\frac{1}{N}\sum_{k=1}^Nh(k)t(k)=\frac{1}{N}\sum_{k=1}^Nd_ka_{t(k)}\leq \frac{1}{N}\sum_{k=1}^Nd_ka_{\hat t(k)}=\frac{1}{N}\sum_{k=1}^Nh(k)\hat t(k)=E(h(X)\hat t(X)),$$ d'où le résultat.

Pour afficher le fil des commentaires : Commentaires.


Pour poster un commentaire ou obtenir de l'aide : c'est ici!




Formulaire

L'insertion de formules suit la syntaxe LATEX. Toute formule doit être encadrée par des dollars : $\bf{\$formule\$}$. Par exemple $\bf{\$ u\_n \$}$ sera interprétée comme une formule et donnera $\bf{u_n}$. Voici quelques exemples pour ceux qui ne sont pas habitués :

Contacter l'auteur du site : frederic.millet @ math-sup.fr