Inégalité de réarrangement

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 :

${\displaystyle W(\sigma )=\sum _{m=1}^{k}w_{m}(\sigma ),}$

où le temps d'attente du client n°m, ${\displaystyle 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 ... ) :

${\displaystyle w_{m}(\sigma )=\sum _{j=1}^{k}p_{j}\ {\text{1}}\!{\text{I}}_{\sigma (j)\,\leq \,\sigma (m)}.}$

Ainsi

${\displaystyle {\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 à :

${\displaystyle p_{\sigma ^{-1}(1)}\ \leq \ p_{\sigma ^{-1}(2)}\ \leq \ p_{\sigma ^{-1}(3)}\ \leq \ \dots \ \leq \ p_{\sigma ^{-1}(k)}.}$

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 ${\displaystyle 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 ${\displaystyle (\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 à ${\displaystyle C_{\sigma (1)},}$ puis à ${\displaystyle C_{\sigma (2)},}$ ${\displaystyle C_{\sigma (3)},}$ etc ... où σ désigne une permutation du groupe symétrique ${\displaystyle {\mathfrak {S}}_{k},}$ choisie une bonne fois pour toutes avant le traitement de la suite ${\displaystyle \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

${\displaystyle {\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ù

${\displaystyle \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 ${\displaystyle {\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 à :

${\displaystyle p_{\sigma (1)}\ \geq \ p_{\sigma (2)}\ \geq \ p_{\sigma (3)}\ \geq \ \dots \ \geq \ p_{\sigma (k)}\ >\ 0.}$

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

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

${\displaystyle {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).}$

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

${\displaystyle {\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 ${\displaystyle \omega \in ]0,1[,}$ on pose

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

A égalité presque sûre près, X₀ et Y₀ sont les seules applications croissantes définies sur ${\displaystyle (\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 ${\displaystyle (\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

${\displaystyle {\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é ${\displaystyle (\Omega ,{\mathcal {A}},\mathbb {P} )}$ sur lequel X et Y sont définies.

Comme

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

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

• (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.