Inégalité de réarrangement

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Énoncé[modifier | modifier le code]

Dans ce qui suit, \scriptstyle\ \mathfrak{S}_n\ désigne le groupe symétrique à n! éléments, et \scriptstyle\ \sigma\ désigne une permutation, un élément typique de \scriptstyle\ \mathfrak{S}_n.\

Inégalité de réarrangement —  Si \scriptstyle\ x_1\ \le\ x_2\ \le\ \dots\ \le\ x_n,\ et si \scriptstyle\  y_1\ \le\ y_2\ \le\ \dots\ \le\ y_n,\ alors

\forall \sigma\in\mathfrak{S}_n,\qquad\sum_{i=1}^nx_iy_i\ \ge\ \sum_{i=1}^nx_iy_{\sigma(i)}.

Autrement dit le maximum, sur \scriptstyle\ \mathfrak{S}_n,\ de l'application :

\sigma\quad\mapsto\quad \sum_{i=1}^nx_iy_{\sigma(i)},

est atteint pour σ=Id. On a un résultat similaire pour le minimum de l'application :

x_1y_1 + \cdots + x_ny_n \geq x_1y_{\sigma (1)} + \cdots + x_ny_{\sigma (n)} \geq x_1y_n + \cdots + x_ny_1,

ce qui signifie que le minimum est atteint pour σ=(n, n-1, n-2, ... , 3, 2, 1).

Si toutes les inégalités des hypothèses sont strictes, il n'y a égalité que pour σ=Id.

Démonstration[modifier | modifier le code]

La minoration est obtenue en appliquant la majoration à

(x^{\prime}_{1}, x^{\prime}_{2}, \dots, x^{\prime}_{n})\ =\ (-x_n, -x_{n-1}, \dots, -x_1).

Il suffit donc de démontrer la majoration. Comme \scriptstyle\ \mathfrak{S}_n\ est un ensemble fini, il existe au moins une permutation σ telle que

T(\sigma)\ =\ x_1y_{\sigma (1)}+\ \cdots\ + x_ny_{\sigma (n)}

soit maximal. S'il existe plusieurs permutations maximales, notons σ une des permutations maximales, choisie parmi les permutations maximales qui possèdent le plus grand nombre de points fixes (s'il y en a plusieurs).

On va démontrer par l'absurde que σ est nécessairement l'élément identité de \scriptstyle\ \mathfrak{S}_n\ . Supposons donc que σ n'est pas l'identité. Alors il existe un j dans \scriptstyle\ [\![1,n]\!]\ tel que σ(j) ≠ j et σ(i) = i pour tout i dans \scriptstyle\ [\![1,j-1]\!]\  : j est le plus petit élément de \scriptstyle\ [\![1,n]\!]\ qui ne soit pas un point fixe. Alors σ(j) > j, puisque tous les éléments de \scriptstyle\ [\![1,j-1]\!]\ ont un antécédent autre que j. Par ailleurs, il existe \scriptstyle\ k\in[\![j+1,n]\!]\ tel que σ(k) = j, puisque tous les éléments de \scriptstyle\ [\![1,j-1]\!]\ ont une image autre que j. Maintenant :

\{j<k\}\ \Rightarrow\ \{x_j\le x_k\}\qquad\text{et}\qquad\{j=\sigma(k)<\sigma(j)\}\ \Rightarrow\ \{y_j\le y_{\sigma(j)}\}.\qquad(1)

Par conséquent,

0\le(y_{\sigma(j)}-y_j)(x_k-x_j). \qquad(2)

En développant et en réordonnant, on obtient :

x_jy_{\sigma(j)}+x_ky_j\le x_jy_j+x_ky_{\sigma(j)}. \qquad(3)

On remarque que la permutation τ définie par

\tau(i):=\begin{cases}\sigma(i)&\text{pour }i\notin\{j,k\},\\
j&\text{pour }i=j,\\
\sigma(j)&\text{pour }i=k,\end{cases}

obtenue à partir de σ en échangeant les valeurs de σ(j) et σ(k), possède au moins un point fixe de plus que σ, à savoir j, et aucun point fixe de moins puisque le seul autre élément dont l'image change, l'élément k, n'était pas un point fixe. De plus, les deux sommes, \scriptstyle\ T(\sigma)\ et \scriptstyle\ T(\tau),\ ne diffèrent qu'en les deux termes indexés par j et k. Ainsi, la permutation τ réalise le maximum tout autant que la permutation σ, puisque (3) se réécrit :

T(\sigma)-T(\tau)\ =\ (x_jy_{\sigma(j)}+x_ky_{\sigma(k)})-(x_jy_{\tau(j)}+x_ky_{\tau(k)})\ \le\ 0.\qquad(3^{\prime})

Finalement, (3') est en contradiction avec le choix de σ.

Si

x_1<\cdots<x_n\quad\text{et}\quad y_1<\cdots<y_n,

alors les inégalités (1), (2), et (3) sont strictes, donc le maximum ne peut être atteint qu'en l'identité, tout autre permutation τ étant strictement suboptimale.

Applications[modifier | modifier le code]

Il existe beaucoup d'applications plus ou moins concrètes de cette inégalité ; une de celles qui viennent à l'esprit en premier est qu'on a intérêt à avoir les meilleures notes yi dans les matières qui ont les plus gros coefficients xi.

Job-shop à une machine[modifier | modifier le code]

On dispose d'une machine pour accomplir un ensemble de k tâches, commandées par k clients. Pour traiter la tâche n°i, la machine consomme un temps pi. La machine ne peut effectuer qu'une tâche à la fois. L'objectif est de minimiser le temps d'attente total des k clients :

W(\sigma)=\sum_{m=1}^k w_{m}(\sigma),

où le temps d'attente du client n°m, \scriptstyle\ w_{m}(\sigma),\ dépend de l'ordre σ dans lequel les tâches sont présentées à la machine (la machine traite d'abord la tâche σ(1), puis σ(2), etc ... ) :

w_{m}(\sigma)=\sum_{j=1}^k p_{j}\ \text{1}\!\text{I}_{\sigma(j)\,\le\,\sigma(m)}.

Ainsi

\begin{align}
W(\sigma)&= \sum_{m=1}^k\ \left(\sum_{j=1}^k p_{j}\ \text{1}\!\text{I}_{\sigma(j)\,\le\,\sigma(m)}\right)\\
    &=  \sum_{j=1}^k\ p_{j}\ \left(\sum_{m=1}^k\ \text{1}\!\text{I}_{\sigma(j)\,\le\,\sigma(m)}\right)\\ 
    &= \sum_{j=1}^k\ p_{j}\ \left(n+1-\sigma(j)\right)\\ 
&= \sum_{i=1}^k\ p_{\sigma^{-1}(i)}\ \left(n+1-i\right).
\end{align}

Alors, l'inégalité de réarrangement (et le bon sens) disent qu'il est optimal de choisir une permutation σ satisfaisant à :

p_{\sigma^{-1}(1)}\ \le\ p_{\sigma^{-1}(2)}\ \le\ p_{\sigma^{-1}(3)}\ \le\ \dots\ \le\ p_{\sigma^{-1}(k)}.


Interprétation  :

Autrement dit, au supermarché, pour minimiser le temps total d'attente des clients, il faut faire passer en premier ceux qui ont le caddy le moins plein.

Tri sans stratégie[modifier | modifier le code]

L'algorithme de tri suivant a pour but de déterminer l'appartenance d'éléments (individus) d'une suite à un ensemble de k catégories C1 , C2 , ... , Ck disjointes, à des fins d'indexation ou de rangement :

[10] i = 1 ; u = 0
[20] Enregistrer l'individu w
[30] Tant que u = 0, faire : 
  [40] Si \scriptstyle\ w\in C_i,\  ranger w dans le fichier Fi et faire u = 1
  [50] i = i+1
[60] Fin tant
[70] Fin

Notons X(w) le numéro de la catégorie à laquelle appartient l'individu w et T(w) le temps nécessaire à l'algorithme pour ranger w. On se convainc facilement que T est une fonction affine croissante de X (posons T = aX + b, a>0) : en effet, la boucle tant que est itérée m fois si l'individu appartient à la catégorie Cm.

On suppose que

  • les individus \scriptstyle\ (\omega_{i})_{1\ \le\ i\ \le\ n}\ traités par l'algorithme sont tirés au hasard dans une population divisée en k catégories disjointes C1 , C2 , ... , Ck  ;
  • au départ la numérotation des catégories peut-être choisie librement : on peut choisir de tester l'appartenance de l'individu d'abord à \scriptstyle\ C_{\sigma(1)},\ puis à \scriptstyle\ C_{\sigma(2)},\ \scriptstyle\ C_{\sigma(3)},\ etc ... où σ désigne une permutation du groupe symétrique \scriptstyle\ \mathfrak{S}_{k},\ choisie une bonne fois pour toutes avant le traitement de la suite \scriptstyle\ \omega=(\omega_{i})_{1\ \le\ i\ \le\ n}\  ;
  • la proportion d'individus de catégorie Ci dans la population est pi .

Le coût total C(ω) de l'exécution de l'algorithme est donné par

\begin{align}
c(\omega)&= \sum_{i=1}^n   T(\omega_{i})\\
    &= bn+a\sum_{i=1}^n   X(\omega_{i})\\  
    &= bn+an\mathbb{E}[X]+o(n),\\  
\end{align}

\mathbb{E}[X]=\sum_{m=1}^k p_{\sigma(k)}k

est l'espérance de la variable aléatoire X. Le développement asymptotique de c(ω) découle de la loi forte des grands nombres, si l'on suppose que les individus sont tirés de la population avec remise. Le terme o(n)[1] peut être précisé en \scriptstyle\ \mathcal{O}(\sqrt n)\ en utilisant, par exemple, le théorème central limite, ou bien l'inégalité de Hoeffding.

L'inégalité de réarrangement (et le bon sens) disent que, dans un but d'économie, il est optimal de choisir une permutation σ satisfaisant à :

p_{\sigma(1)}\ \ge\ p_{\sigma(2)}\ \ge\ p_{\sigma(3)}\ \ge\ \dots\ \ge\ p_{\sigma(k)}\ >\ 0.
Interprétation  :

Autrement dit, il est optimal, lorsqu'on teste l'appartenance aux différentes catégories, de ranger ces catégories dans l'ordre d'importance décroissante.

Par exemple le coût le plus défavorable (resp. le plus favorable), si n = 3 et {p1 , p2 , p3 } = {0.1 ; 0.6 ; 0.3}, correspond à 132 et donne \scriptstyle\ \mathbb{E}[X]{{=}}2.5, \ (resp. correspond à 231 et donne \scriptstyle\ \mathbb{E}[X]{{=}}1.5 \ ).

Inégalité de Tchebychev pour les sommes[modifier | modifier le code]

L'inégalité de Tchebychev pour les sommes est due à Pafnouti Tchebychev. Elle découle directement de l'inégalité de réarrangement, et est un cas particulier de l'inégalité FKG ou inégalité de corrélation. Elle ne doit pas être confondue avec l'inégalité de Bienaymé-Tchebychev.

Inégalité de Tchebychev pour les sommes — Si \scriptstyle\ a_1 \geq a_2 \geq \cdots \geq a_n\ et \scriptstyle\ b_1 \geq b_2 \geq \cdots \geq b_n,\ alors

{1\over n} \sum_{k=1}^n a_kb_k \geq \left({1\over n}\sum_{k=1}^n a_k\right)\left({1\over n}\sum_{k=1}^n b_k\right).

De même, si \scriptstyle\ a_1 \geq a_2 \geq \cdots \geq a_n\ et \scriptstyle\ b_1 \leq b_2 \leq \cdots \leq b_n,\ alors

{1\over n} \sum_{k=1}^n a_kb_k \leq \left({1\over n}\sum_{k=1}^n a_k\right)\left({1\over n}\sum_{k=1}^n b_k\right).

Distance de Wasserstein L2[modifier | modifier le code]

Un problème analogue[2], en probabilités, est de trouver les extrémas de la quantité \scriptstyle\  \mathbb{E}[XY]\ lorsque la loi jointe du couple (X,Y) est arbitraire, ainsi, d'ailleurs, que l'espace probabilisé \scriptstyle\  (\Omega, \mathcal{A}, \mathbb{P})\ sur lequel X et Y sont définies, alors que les marginales (les lois de probabilités des deux variables aléatoires X et Y), disons μ et ν, sont fixées. La solution évoque celle de l'inégalité de réarrangement, puisque le maximum est atteint, entre autres, par les deux applications croissantes X0 et Y0définies sur \scriptstyle\  (\Omega, \mathcal{A}, \mathbb{P})=(]0,1[,\mathcal{B}(]0,1[), dx)\ à l'aide du théorème de la réciproque : pour \ \scriptstyle \omega \in]0,1[,\ on pose

\begin{align}
X_0(\omega)&= \inf\left\{x\in\mathbb{R}\ |\ \mu(]-\infty, x])\ge\omega\right\},
\\
Y_0(\omega)&= \inf\left\{x\in\mathbb{R}\ |\ \nu(]-\infty, x])\ge\omega\right\}.
\end{align}

Le minimum étant atteint, lui, pour le choix conjoint de X0 et Y1 , où, pour \ \scriptstyle \omega \in]0,1[,\ on pose

Y_1(\omega)\ =\ Y_0(1-\omega).
Remarque  :

Hardy, Littlewood, et Polya[3] appellent X0 et Y0 les réarrangées croissantes de μ et ν. De la même manière, Y1 est une réarrangée décroissante de ν.

A égalité presque sûre près, X0 et Y0 sont les seules applications croissantes définies sur \scriptstyle\  (\Omega, \mathcal{A}, \mathbb{P})=(]0,1[,\mathcal{B}(]0,1[), dx)\ et ayant pour lois de probabilités respectives μ et ν, Y1 étant la seule application décroissante définie sur \scriptstyle\  (\Omega, \mathcal{A}, \mathbb{P})=(]0,1[,\mathcal{B}(]0,1[), dx)\ et ayant pour loi de probabilité ν ...

Définition — La distance de Wasserstein (en) L2 entre les deux lois de probabilité μ et ν est l'infimum des quantités

\sqrt{\mathbb{E}\left[\left(X-Y\right)^2\right]}\ =\ \sqrt{\mathbb{E}\left[X^2\right]+\mathbb{E}\left[Y^2\right]-2\mathbb{E}\left[XY\right]},

lorsque les lois de probabilités respectives des deux variables aléatoires X et Y sont fixées égales à μ et ν, respectivement, mais que la loi jointe du couple (X,Y) est arbitraire, ainsi, d'ailleurs, que l'espace probabilisé \scriptstyle\  (\Omega, \mathcal{A}, \mathbb{P})\ sur lequel X et Y sont définies.

Comme

\mathbb{E}\left[X^2\right]=\int_{\mathbb{R}}\ x^2\ \mu(dx)

ne dépend pas de la loi jointe, mais seulement de μ, ce problème de minimisation de \scriptstyle\ \mathbb{E}\left[\left(X-Y\right)^2\right] est équivalent au problème précédent (de maximisation de \scriptstyle\ \mathbb{E}\left[XY\right]\ ), pour peu que \scriptstyle\ \mathbb{E}\left[X^2\right]=\int_{\mathbb{R}}\ x^2\ \mu(dx) et \scriptstyle\ \mathbb{E}\left[Y^2\right]=\int_{\mathbb{R}}\ x^2\ \nu(dx) soient toutes deux finies.

Le problème du calcul de la distance de Wasserstein L2 entre deux lois de probabilités est une variante du problème de transport de Monge-Kantorovitch.

Voir aussi[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Voir la page "Notation de Landau".
  2. Cette analogie est détaillée (et la démonstration est donnée) dans les sections 10.12 et 10.13 de Hardy, Littlewood et Polya 1988.
  3. Hardy, Littlewood et Polya 1988, sections 10.12 et 10.13

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) G. H. Hardy, J. E. Littlewood et G. Polya, Inequalities, CUP,‎ 26 février 1988, 2e éd. (1re éd. 1952), 324 p. (ISBN 978-0-521-35880-4, lire en ligne), Section 10.2.
  • (en) J. Michael Steele, The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities, Cambridge University Press,‎ 26 avril 2004, 1e éd., 316 p. (ISBN 052154677X), Problem 5.3, page 78.
  • (en) Simon French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, John Wiley & sons, coll. « Ellis Horwood series in mathematics and its applications »,‎ 1982, 1e éd., 245 p. (ISBN 0853122997), Theorem 3.3, page 37.