Inégalité de réarrangement

Inégalité de réarrangement

Sommaire

Énoncé

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\rightarrow\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

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

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

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

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}

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)[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

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

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 Y0 dé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

Notes

  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 (en) Godfrey Harold Hardy, John Edensor Littlewood et George Polya, Inequalities, Cambridge University Press, 26 février 1988, 2e éd., 324 p. (ISBN 0521358809)  .
  3. ↑ (en) Godfrey Harold Hardy, John Edensor Littlewood et George Polya, Inequalities, Cambridge University Press, 26 février 1988, 2e éd., 324 p. (ISBN 0521358809) , sections 10.12 et 10.13

Pages liées

Bibliographie

  • G. H. Hardy, J. E. Littlewood, G. Polya: Inequalities, Cambridge University Press (1952), 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, 1re é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, 1re éd., 245 p. (ISBN 0853122997) , Theorem 3.3, page 37.



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Inégalité de réarrangement de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Inégalité de Nesbitt — Sommaire 1 Énoncé 2 Démonstration 3 Bibliographie 4 Pages liées Énoncé L inégalité de Nesbitt peut …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Fonction De Répartition — Fonctions de répartition d une variable discrète, d une variable diffuse et d une variable avec atome, mais non discrète. En théorie des probabilités ou en statistiques, la fonction de répartition d une variable aléatoire réelle caractérise la lo …   Wikipédia en Français

  • Fonction de repartition — Fonction de répartition Fonctions de répartition d une variable discrète, d une variable diffuse et d une variable avec atome, mais non discrète. En théorie des probabilités ou en statistiques, la fonction de répartition d une variable aléatoire… …   Wikipédia en Français

  • Fonction de répartition — Fonctions de répartition d une variable discrète, d une variable diffuse et d une variable avec atome, mais non discrète. En théorie des probabilités ou en statistiques, la fonction de répartition d une variable aléatoire réelle caractérise la… …   Wikipédia en Français

  • Théorie du transport — En mathématique et en économie, la théorie du transport est le nom donné à l étude du transfert optimal de matière et à l allocation optimale de ressources. Le problème a été formalisé par le mathématicien français Gaspard Monge en 1781[1]. D… …   Wikipédia en Français

  • Distance (mathématiques) — Pour les articles homonymes, voir Distance. En mathématiques, une distance est une application qui formalise l idée intuitive de distance, c est à dire la longueur qui sépare deux points. C est par l analyse des principales propriétés de la… …   Wikipédia en Français

  • Distance (Mathématiques) — Pour les articles homonymes, voir Distance. En mathématiques, une distance est une application qui formalise l idée intuitive de distance, c est à dire la longueur qui sépare deux points. Sommaire 1 Distance sur un ensemble …   Wikipédia en Français

  • Distance (mathematiques) — Distance (mathématiques) Pour les articles homonymes, voir Distance. En mathématiques, une distance est une application qui formalise l idée intuitive de distance, c est à dire la longueur qui sépare deux points. Sommaire 1 Distance sur un… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”