Inégalité de réarrangement

En mathématiques, l'inégalité de réarrangement ou inégalité de réordonnement est un résultat numérique sur l'ordre de produits d'une suite de nombres réels. Il énonce que, lorsqu'on fait la somme des produits des éléments de deux ensembles, le résultat le plus grand est obtenu en multipliant successivement les plus grands nombres entre eux. Le résultat peut être démontré avec un raisonnement par l'absurde.

Concrètement, cette inégalité peut être utilisée pour la priorisation des tâches d'un algorithme de minimisation de temps d'attente ou de tri.

L'inégalité de Tchebychev (relation entre moyenne des produits, et produit des moyennes) découle de l'inégalité de réarrangement.

Énoncé

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

Inégalité de réarrangement —  Si $x_{1}\ \leq \ x_{2}\ \leq \ \dots \ \leq \ x_{n},$ et si $y_{1}\ \leq \ y_{2}\ \leq \ \dots \ \leq \ y_{n},$ alors

$\forall \sigma \in {\mathfrak {S}}_{n},\qquad \sum _{i=1}^{n}x_{i}y_{i}\ \geq \ \sum _{i=1}^{n}x_{i}y_{\sigma (i)}.$

Autrement dit le maximum, sur ${\mathfrak {S}}_{n},$ de l'application :

$\sigma \quad \mapsto \quad \sum _{i=1}^{n}x_{i}y_{\sigma (i)},$

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

$x_{1}y_{1}+\cdots +x_{n}y_{n}\geq x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}\geq x_{1}y_{n}+\cdots +x_{n}y_{1},$

ce qui signifie que le minimum est atteint pour $\sigma =(n,n-1,n-2,\dots ,3,2,1)$.

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

Démonstration

La minoration est obtenue en appliquant la majoration à

$(x_{1}^{\prime },x_{2}^{\prime },\dots ,x_{n}^{\prime })\ =\ (-x_{n},-x_{n-1},\dots ,-x_{1}).$

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

$T(\sigma )\ =\ x_{1}y_{\sigma (1)}+\ \cdots \ +x_{n}y_{\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 ${\mathfrak {S}}_{n}$. Supposons donc que σ n'est pas l'identité. Alors il existe un j dans $[\![1,n]\!]$ tel que σ(j) ≠ j et σ(i) = i pour tout i dans $[\![1,j-1]\!]$ : j est le plus petit élément de $[\![1,n]\!]$ qui ne soit pas un point fixe. Alors σ(j) > j, puisque tous les éléments de $[\![1,j-1]\!]$ ont un antécédent autre que j. Par ailleurs, il existe $k\in [\![j+1,n]\!]$ tel que σ(k) = j, puisque tous les éléments de $[\![1,j-1]\!]$ ont une image autre que j. Maintenant :

$\{j<k\}\ \Rightarrow \ \{x_{j}\leq x_{k}\}\qquad {\text{et}}\qquad \{j=\sigma (k)<\sigma (j)\}\ \Rightarrow \ \{y_{j}\leq y_{\sigma (j)}\}.\qquad (1)$

Par conséquent,

$0\leq (y_{\sigma (j)}-y_{j})(x_{k}-x_{j}).\qquad (2)$

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

$x_{j}y_{\sigma (j)}+x_{k}y_{j}\leq x_{j}y_{j}+x_{k}y_{\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, T(σ) et T(τ) 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_{j}y_{\sigma (j)}+x_{k}y_{\sigma (k)})-(x_{j}y_{\tau (j)}+x_{k}y_{\tau (k)})\ \leq \ 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

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 y_i dans les matières qui ont les plus gros coefficients x_i.

Job-shop à une machine

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 p_i. 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, $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)\,\leq \,\sigma (m)}.$

Ainsi

${\begin{aligned}W(\sigma )&=\sum _{m=1}^{k}\ \left(\sum _{j=1}^{k}p_{j}\ {\text{1}}\!{\text{I}}_{\sigma (j)\,\leq \,\sigma (m)}\right)\\&=\sum _{j=1}^{k}\ p_{j}\ \left(\sum _{m=1}^{k}\ {\text{1}}\!{\text{I}}_{\sigma (j)\,\leq \,\sigma (m)}\right)\\&=\sum _{j=1}^{k}\ p_{j}\ \left(k+1-\sigma (j)\right)\\&=\sum _{i=1}^{k}\ p_{\sigma ^{-1}(i)}\ \left(k+1-i\right).\end{aligned}}$

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)}\ \leq \ p_{\sigma ^{-1}(2)}\ \leq \ p_{\sigma ^{-1}(3)}\ \leq \ \dots \ \leq \ 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

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 C₁, C₂ , ... , C_k 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 $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 C_m.

On suppose que

• les individus $(\omega _{i})_{1\ \leq \ i\ \leq \ n}$ traités par l'algorithme sont tirés au hasard dans une population divisée en k catégories disjointes C₁, C₂, ... , C_k  ;
• 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 à $C_{\sigma (1)},$ puis à $C_{\sigma (2)},$ $C_{\sigma (3)},$ etc ... où σ désigne une permutation du groupe symétrique ${\mathfrak {S}}_{k},$ choisie une bonne fois pour toutes avant le traitement de la suite $\omega =(\omega _{i})_{1\ \leq \ i\ \leq \ n}$ ;
• la proportion d'individus de catégorie C_i dans la population est p_i .

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

${\begin{aligned}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{aligned}}$

où

$\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) peut être précisé en ${\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)}\ \geq \ p_{\sigma (2)}\ \geq \ p_{\sigma (3)}\ \geq \ \dots \ \geq \ 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 {p₁ , p₂ , p₃} = {0.1 ; 0.6 ; 0.3}, correspond à 132 et donne $\mathbb {E} [X]{=}2.5,$ (resp. correspond à 231 et donne $\mathbb {E} [X]{=}1.5$).

Inégalité de Tchebychev pour les sommes

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 $a_{1}\geq a_{2}\geq \cdots \geq a_{n}$ et $b_{1}\geq b_{2}\geq \cdots \geq b_{n},$ alors

${1 \over n}\sum _{k=1}^{n}a_{k}b_{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 $a_{1}\geq a_{2}\geq \cdots \geq a_{n}$ et $b_{1}\leq b_{2}\leq \cdots \leq b_{n},$ alors

${1 \over n}\sum _{k=1}^{n}a_{k}b_{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

Un problème analogue, en probabilités, est de trouver les extrémas de la quantité $\mathbb {E} [XY]$ lorsque la loi jointe du couple (X,Y) est arbitraire, ainsi, d'ailleurs, que l'espace probabilisé $(\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 X₀ et Y₀définies sur $(\Omega ,{\mathcal {A}},\mathbb {P} )=(]0,1[,{\mathcal {B}}(]0,1[),dx)$ à l'aide du théorème de la réciproque : pour $\omega \in ]0,1[,$ on pose

${\begin{aligned}X_{0}(\omega )&=\inf \left\{x\in \mathbb {R} \ |\ \mu (]-\infty ,x])\geq \omega \right\},\\Y_{0}(\omega )&=\inf \left\{x\in \mathbb {R} \ |\ \nu (]-\infty ,x])\geq \omega \right\}.\end{aligned}}$

Le minimum étant atteint, lui, pour le choix conjoint de X₀ et Y₁, où, pour $\omega \in ]0,1[,$ on pose

$Y_{1}(\omega )\ =\ Y_{0}(1-\omega ).$

Remarque :

Hardy, Littlewood, et Pólya appellent X₀ et Y₀ les réarrangées croissantes de μ et ν. De la même manière, Y₁ est une réarrangée décroissante de ν.

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

Définition — La distance de Wasserstein 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é $(\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 $\mathbb {E} \left[\left(X-Y\right)^{2}\right]$ est équivalent au problème précédent (de maximisation de $\mathbb {E} \left[XY\right]$), pour peu que $\mathbb {E} \left[X^{2}\right]=\int _{\mathbb {R} }\ x^{2}\ \mu (dx)$ et $\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

Articles connexes

• Permutation
• Groupe symétrique
• Inégalité de Nesbitt
• Inégalité de Hardy-Littlewood
• Flow-shop
• Théorie du transport
• Fonction de répartition

Bibliographie

• (en) G. H. Hardy, J. E. Littlewood et G. Pólya, Inequalities, CUP, 26 février 1988, 2^e éd. (1^re é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, 1^re éd., 316 p. (ISBN 0-521-54677-X, lire en ligne), 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, 1^re éd., 245 p. (ISBN 0-85312-299-7), Theorem 3.3, page 37.