Inégalité de réarrangement

En mathématiques, lModèle:'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, ${𝔖}_n$ désigne le groupe symétrique à n! éléments, et σ désigne une permutation, un élément typique de ${𝔖}_n.$ Modèle:Théorème

Autrement dit le maximum, sur ${𝔖}_n,$ de l'application :

$\sigma \mapsto \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\ge x_1{y}_{\sigma (1)}+\cdots +x_n{y}_{\sigma (n)}\ge 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 ${𝔖}_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 ${𝔖}_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\le x_k\}\text{et}\{j=\sigma (k)<\sigma (j)\}\Rightarrow \{y_j\le y_{\sigma (j)}\}.(1)$

Par conséquent,

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

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

$x_j{y}_{\sigma (j)}+x_k{y}_j\le x_j{y}_j+x_k{y}_{\sigma (j)}.(3)$

On remarque que la permutation τ définie par

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

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)})\le 0.(3^{\prime })$

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

Si

$x_1<\cdots <x_n\text{et}{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)\le \sigma (m)}.$

Ainsi

$\begin{array}{cc}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(k+1-\sigma (j))\\ & =\sum _{i=1}^k{p}_{{\sigma }^{-1}(i)}(k+1-i).\end{array}$

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

Modèle:Exemple

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\le i\le 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 ${𝔖}_k,$ choisie une bonne fois pour toutes avant le traitement de la suite $\omega =({\omega }_i{)}_{1\le i\le 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{array}{cc}c(\omega )& =\sum _{i=1}^{n}T({\omega }_i)\\ & =bn+a\sum _{i=1}^{n}X({\omega }_i)\\ & =bn+an𝔼[X]+o(n),\\ \end{array}$

où

$𝔼[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 $𝒪(\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.$

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. Modèle:Théorème

Distance de Wasserstein L2

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

$\begin{array}{cc}{X}_0(\omega )& =\inf \{x\in ℝ|\mu (]-\mathrm{\infty },x])\ge \omega \},\\ Y_0(\omega )& =\inf \{x\in ℝ|\nu (]-\mathrm{\infty },x])\ge \omega \}.\end{array}$

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 ).$

Modèle:Exemple A égalité presque sûre près, XModèle:Ind et YModèle:Ind sont les seules applications croissantes définies sur $(\mathrm{\Omega },𝒜,\mathbb{P})=(]0,1[,ℬ(]0,1[),dx)$ et ayant pour lois de probabilités respectives μ et ν, Y₁ étant la seule application décroissante définie sur $(\mathrm{\Omega },𝒜,\mathbb{P})=(]0,1[,ℬ(]0,1[),dx)$ et ayant pour loi de probabilité ν ...

Modèle:Théorème Comme

$𝔼\left[X^2\right]=\underset{ℝ}{\int }{x}^2\mu (dx)$

ne dépend pas de la loi jointe, mais seulement de μ, ce problème de minimisation de $𝔼\left[{(X-Y)}^2\right]$ est équivalent au problème précédent (de maximisation de $𝔼\left[XY\right]$), pour peu que $𝔼\left[X^2\right]=\underset{ℝ}{\int }{x}^2\mu (dx)$ et $𝔼\left[Y^2\right]=\underset{ℝ}{\int }{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

• Modèle:Ouvrage, Section 10.2.
• Modèle:Ouvrage, Problem 5.3, page 78.
• Modèle:Ouvrage, Theorem 3.3, page 37.

Modèle:Portail