Átrendezési egyenlőtlenség
A matematika , rendezési egyenlőtlenség egy numerikus eredményt nagyságrendű termékek sorozatából a valós számok.
Államok
A következőkben jelöli a szimmetrikus csoport a n ! elemek, és σ a permutációt , a tipikus elemét jelöliSnem{\ displaystyle {\ mathfrak {S}} _ {n}}Snem.{\ displaystyle {\ mathfrak {S}} _ {n}.}
Átrendezési egyenlőtlenség - Ha és ha akkor
x1 ≤ x2 ≤ ... ≤ xnem,{\ displaystyle x_ {1} \ \ leq \ x_ {2} \ \ leq \ \ dots \ \ leq \ x_ {n},}y1 ≤ y2 ≤ ... ≤ ynem,{\ displaystyle y_ {1} \ \ leq \ y_ {2} \ \ leq \ \ dots \ \ leq \ y_ {n},}
∀σ∈Snem,∑én=1nemxényén ≥ ∑én=1nemxényσ(én).{\ displaystyle \ 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)}.}
Más szavakkal, maximálisan az alkalmazáson:
Snem,{\ displaystyle {\ mathfrak {S}} _ {n},}
σ↦∑én=1nemxényσ(én),{\ displaystyle \ sigma \ quad \ mapsto \ quad \ sum _ {i = 1} ^ {n} x_ {i} y _ {\ sigma (i)},}
eléri a σ = Id értéket. Hasonló eredményt kapunk a minimális alkalmazás esetén is:
x1y1+⋯+xnemynem≥x1yσ(1)+⋯+xnemyσ(nem)≥x1ynem+⋯+xnemy1,{\ displaystyle x_ {1} y_ {1} + \ cdots + x_ {n} y_ {n} \ geq x_ {1} y _ {\ sigma (1)} + \ cdots + x_ {n} y _ {\ szigma (n)} \ geq x_ {1} y_ {n} + \ cdots + x_ {n} y_ {1},}
ami azt jelenti, hogy elértük a minimumot σ = ( n , n -1, n -2, ..., 3, 2, 1) esetén.
Ha a feltételezések összes egyenlőtlensége szigorú, akkor csak a σ = Id esetén van egyenlőség .
Demonstráció
A csökkentést úgy kapjuk meg, hogy a növekedést alkalmazzuk
(x1′,x2′,...,xnem′) = (-xnem,-xnem-1,...,-x1).{\ displaystyle (x_ {1} ^ {\ prime}, x_ {2} ^ {\ prime}, \ pontok, x_ {n} ^ {\ prime}) \ = \ (-x_ {n}, - x_ { n-1}, \ pontok, -x_ {1}).}
Ezért elegendő a felár bemutatása. Mivel ez egy véges halmaz, létezik legalább egy σ olyan permutáció , amely
Snem{\ displaystyle {\ mathfrak {S}} _ {n}}
T(σ) = x1yσ(1)+ ⋯ +xnemyσ(nem){\ displaystyle T (\ sigma) \ = \ x_ {1} y _ {\ sigma (1)} + \ \ cdots \ + x_ {n} y _ {\ sigma (n)}}
maximális. Ha több maximális permutáció létezik , jelöljük σ-val a maximális permutációk egyikét, amelyet a legnagyobb fix mutatókkal rendelkező maximális permutációk közül választunk (ha több van).
Az abszurddal be fogjuk bizonyítani, hogy σ szükségszerűen identitáseleme . Tegyük fel tehát, hogy σ nem az azonosság. Ekkor létezik egy j az olyan, hogy σ ( j ) ≠ j és σ ( i ) = i minden i in : j a legkisebb eleme , amely nem egy fix pont. Ekkor σ ( j )> j , mivel a (z ) összes elemének előzménye van, kivéve j-t . Sőt, létezik olyan, hogy σ ( k ) = j , hiszen minden eleme van egy kép eltérő j . Most :
Snem{\ displaystyle {\ mathfrak {S}} _ {n}}[[1,nem]]{\ displaystyle [\! [1, n] \!]}[[1,j-1]]{\ displaystyle [\! [1, j-1] \!]}[[1,nem]]{\ displaystyle [\! [1, n] \!]}[[1,j-1]]{\ displaystyle [\! [1, j-1] \!]}k∈[[j+1,nem]]{\ displaystyle k \ itt: [\! [j + 1, n] \!]}[[1,j-1]]{\ displaystyle [\! [1, j-1] \!]}
{j<k} ⇒ {xj≤xk}és{j=σ(k)<σ(j)} ⇒ {yj≤yσ(j)}.(1){\ displaystyle \ {j <k \} \ \ Rightarrow \ \ {x_ {j} \ leq x_ {k} \} \ qquad {\ text {és}} \ qquad \ {j = \ sigma (k) <\ sigma (j) \} \ \ Rightarrow \ \ {y_ {j} \ leq y _ {\ sigma (j)} \}. \ qquad (1)}
Ebből kifolyólag,
0≤(yσ(j)-yj)(xk-xj).(2){\ displaystyle 0 \ leq (y _ {\ sigma (j)} - y_ {j}) (x_ {k} -x_ {j}). \ qquad (2)}
Bővítéssel és átrendezéssel a következőket kapjuk:
xjyσ(j)+xkyj≤xjyj+xkyσ(j).(3){\ displaystyle x_ {j} y _ {\ sigma (j)} + x_ {k} y_ {j} \ leq x_ {j} y_ {j} + x_ {k} y _ {\ sigma (j)}. \ qquad (3)}
Ne feledje, hogy a τ permutáció a
τ(én): ={σ(én)mert én∉{j,k},jmert én=j,σ(j)mert én=k,{\ displaystyle \ tau (i): = {\ begin {cases} \ sigma (i) & {\ text {for}} i \ notin \ {j, k \}, \\ j & {\ text {for} } i = j, \\\ sigma (j) és {\ text {for}} i = k, \ end {esetek}}}
a σ- ból σ ( j ) és σ ( k ) értékeinek felcserélésével nyerték , legalább egy fix pontja több mint σ , nevezetesen j , és nincs fix pontja kevesebb, mint az egyetlen másik elem, amelynek képe megváltozik, a k elem , nem volt fix pont. Sőt, a két összeg, T ( σ ) és T ( τ ), csak a j és k által indexelt két kifejezésben különbözik egymástól . Így a τ permutáció ugyanúgy éri el a maximumot, mint a σ permutáció , mivel (3) átíródik:
T(σ)-T(τ) = (xjyσ(j)+xkyσ(k))-(xjyτ(j)+xkyτ(k)) ≤ 0.(3′){\ displaystyle 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})}
Végül a (3 ') ellentmond a σ választásának .
Igen
x1<⋯<xnemésy1<⋯<ynem,{\ displaystyle x_ {1} <\ cdots <x_ {n} \ quad {\ text {és}} \ quad y_ {1} <\ cdots <y_ {n},}
akkor az (1) , (2) és (3) egyenlőtlenségek szigorúak, tehát a maximumot csak identitásban lehet elérni, bármely más τ permutáció szigorúan nem optimális.
Alkalmazások
Ennek az egyenlőtlenségnek többé-kevésbé konkrét alkalmazása van; az egyik az, ami először eszembe jut, hogy érdeke, hogy a legjobb y i pontszámot kapja azokban az alanyokban, amelyeknek a legmagasabb az x i együtthatója .
Van egy gépünk k feladatsor végrehajtására, amelyet k kliens irányít . Az i. Feladat feldolgozásához a gép p i időt vesz igénybe . A gép egyszerre csak egy munkát végezhet. A cél az, hogy minimalizálja k ügyfelek teljes várakozási idejét :
W(σ)=∑m=1kwm(σ),{\ displaystyle W (\ sigma) = \ sum _ {m = 1} ^ {k} w_ {m} (\ sigma),}
ahol a várakozási idő a kliens n ° m , attól függ, hogy a sorrendben σ , amelyben a feladatok bemutatásával, hogy a gép (a gép első feldolgozza a feladatot σ (1), majd a σ (2), stb.):
wm(σ),{\ displaystyle w_ {m} (\ sigma),}
wm(σ)=∑j=1koj 1énσ(j)≤σ(m).{\ displaystyle w_ {m} (\ sigma) = \ sum _ {j = 1} ^ {k} p_ {j} \ {\ text {1}} \! {\ text {I}} _ {\ sigma ( j) \, \ leq \, \ sigma (m)}.}
Így
W(σ)=∑m=1k (∑j=1koj 1énσ(j)≤σ(m))=∑j=1k oj (∑m=1k 1énσ(j)≤σ(m))=∑j=1k oj (nem+1-σ(j))=∑én=1k oσ-1(én) (nem+1-én).{\ 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} \ \ balra (\ sum _ {m = 1} ^ {k} \ {\ text {1}} \! {\ text {I}} _ {\ sigma (j) \, \ leq \, \ sigma (m)} \ jobbra \\ & = \ sum _ {j = 1} ^ {k} \ p_ {j} \ \ balra (n + 1- \ sigma (j) \ jobbra) \\ & = \ sum _ {i = 1} ^ {k} \ p _ {\ sigma ^ {- 1} (i)} \ \ balra (n + 1-i \ jobbra). \ end {igazítva}} }
Ezután az átrendeződési egyenlőtlenség (és a józan ész) azt mondja, hogy optimális a megfelelő σ permutációt választani :
oσ-1(1) ≤ oσ-1(2) ≤ oσ-1(3) ≤ ... ≤ oσ-1(k).{\ displaystyle p _ {\ sigma ^ {- 1} (1)} \ \ leq \ p _ {\ sigma ^ {- 1} (2)} \ \ leq \ p _ {\ sigma ^ {- 1} ( 3)} \ \ leq \ \ dots \ \ leq \ p _ {\ sigma ^ {- 1} (k)}.}
Értelmezés:
Más szavakkal, a szupermarketben az ügyfelek teljes várakozási idejének minimalizálása érdekében először a legkevésbé teljes kosárral rendelkezőket kell előtérbe helyezni.
Rendezés stratégia nélkül
A következő rendezési algoritmus célja az elemek (egyedek) tagságának meghatározása indexeltetés vagy tárolás céljából a C 1 , C 2 , ..., C k szétválasztott k osztály halmazának követésével :
[10] i = 1 ; u = 0
[20] Enregistrer l'individu w
[30] Tant que u = 0, faire :
[40] Si
w∈Ci,{\displaystyle w\in C_{i},} ranger w dans le fichier Fi et faire u = 1
[50] i = i+1
[60] Fin tant
[70] Fin
Jelölje X ( w ) annak a kategóriának a számát, amelyhez az w tartozik, és T ( w ) az algoritmus w rangsorolásához szükséges időt . Könnyen meggyőződhetünk arról, hogy T az X növekvő affin függvénye (legyen T = aX + b , a > 0): valóban, a hurok , amíg m- szer ismétlődik, ha az egyén a C m kategóriába tartozik .
Azt gondoljuk
- az algoritmus által kezelt egyedeket véletlenszerűen választjuk ki egy k diszjunkt C 1 , C 2 , ..., C k kategóriába osztott populációból ;(ωén)1 ≤ én ≤ nem{\ displaystyle (\ omega _ {i}) _ {1 \ \ leq \ i \ \ leq \ n}}
- Kezdetben a számozása a kategóriák szabadon választható: lehet választani, hogy teszteljék a tagság az egyes első, majd stb ... ahol σ jelöli a permutációs a szimmetrikus csoport választott egyszer és mindenkorra a kezelés előtt a folytatást ;VSσ(1),{\ displaystyle C _ {\ sigma (1)},}VSσ(2),{\ displaystyle C _ {\ sigma (2)},} VSσ(3),{\ displaystyle C _ {\ sigma (3)},} Sk,{\ displaystyle {\ mathfrak {S}} _ {k},}ω=(ωén)1 ≤ én ≤ nem{\ displaystyle \ omega = (\ omega _ {i}) _ {1 \ \ leq \ i \ \ leq \ n}}
- a C i kategóriába tartozó egyének aránya a populációban p i .
Az algoritmus futtatásának teljes C (ω) költségét a
vs.(ω)=∑én=1nemT(ωén)=bnem+nál nél∑én=1nemx(ωén)=bnem+nál nélnemE[x]+o(nem),{\ 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 {igazítva}}}
vagy
E[x]=∑m=1koσ(k)k{\ displaystyle \ mathbb {E} [X] = \ összeg _ {m = 1} ^ {k} p _ {\ sigma (k)} k}
az elvárás a véletlen változó X . A c (ω) aszimptotikus tágulása a nagy számok erős törvényéből következik , feltételezve, hogy az egyének a populációból származnak pótlással . Az o ( n ) kifejezés tisztázható például a Central Limit tétel vagy Hoeffding egyenlőtlenségének felhasználásával .
O(nem){\ displaystyle {\ mathcal {O}} ({\ sqrt {n}})}
Az átrendeződési egyenlőtlenség (és a józan ész) azt mondja, hogy a gazdaságosság érdekében optimális az σ kielégítő permutációt választani :
oσ(1) ≥ oσ(2) ≥ oσ(3) ≥ ... ≥ oσ(k) > 0.{\ displaystyle p _ {\ sigma (1)} \ \ geq \ p _ {\ sigma (2)} \ \ geq \ p _ {\ sigma (3)} \ \ geq \ \ dots \ \ geq \ p _ {\ sigma (k)} \> \ 0.}
Értelmezés:
Más szavakkal, optimális, ha különböző kategóriákba tartozó tagságot tesztelünk, ha ezeket a kategóriákat csökkenő fontosságú sorrendbe rendezzük.
Például a legkedvezőtlenebb költség (vagy a legkedvezőbb), ha n = 3 és { p 1 , p 2 , p 3 } = {0,1; 0,6; 0,3} , megegyezik a 132-vel és ad (ill. Megfelel a 231-nek és ad ).E[x]=2.5,{\ displaystyle \ mathbb {E} [X] {=} 2,5,}E[x]=1.5{\ displaystyle \ mathbb {E} [X] {=} 1,5}
Csebisev összegegyenlőtlensége Pafnouti Cebisevnek köszönhető . Ez közvetlenül az átrendeződési egyenlőtlenségből következik, és az FKG egyenlőtlenség vagy a korrelációs egyenlőtlenség speciális esete . Nem szabad összetéveszteni a Bienayme-Chebyshev egyenlőtlenséggel .
Csebisev egyenlőtlenség összegekért - Ha és akkor
nál nél1≥nál nél2≥⋯≥nál nélnem{\ displaystyle a_ {1} \ geq a_ {2} \ geq \ cdots \ geq a_ {n}}b1≥b2≥⋯≥bnem,{\ displaystyle b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n},}
1nem∑k=1nemnál nélkbk≥(1nem∑k=1nemnál nélk)(1nem∑k=1nembk).{\ displaystyle {1 \ over n} \ sum _ {k = 1} ^ {n} a_ {k} b_ {k} \ geq \ left ({1 \ over n} \ sum _ {k = 1} ^ { n} a_ {k} \ jobbra) \ balra ({1 \ felett n} \ összeg _ {k = 1} ^ {n} b_ {k} \ jobbra).}
Hasonlóképpen, ha és akkor
nál nél1≥nál nél2≥⋯≥nál nélnem{\ displaystyle a_ {1} \ geq a_ {2} \ geq \ cdots \ geq a_ {n}}b1≤b2≤⋯≤bnem,{\ displaystyle b_ {1} \ leq b_ {2} \ leq \ cdots \ leq b_ {n},}
1nem∑k=1nemnál nélkbk≤(1nem∑k=1nemnál nélk)(1nem∑k=1nembk).{\ displaystyle {1 \ over n} \ sum _ {k = 1} ^ {n} a_ {k} b_ {k} \ leq \ left ({1 \ over n} \ sum _ {k = 1} ^ { n} a_ {k} \ jobbra) \ balra ({1 \ felett n} \ összeg _ {k = 1} ^ {n} b_ {k} \ jobbra).}
Távolság a Wasserstein L2-től
Analóg probléma a valószínűségekben, hogy megtalálja a mennyiség szélsőségeit, amikor a pár ( X , Y ) együttes törvénye tetszőleges, ráadásul az a valószínűségi tér , amelyen X és Y van definiálva, míg a marginálisok ( a két véletlen változó ( X és Y ) - mondjuk μ és ν - valószínűségi törvényei fixek. A megoldás idézi, hogy a rendezési egyenlőtlenség , mivel a maximális elérésekor, többek között, a két növekvő térképek X 0 és Y 0 definiált segítségével inverz tétel : a mi meg
E[xY]{\ displaystyle \ mathbb {E} [XY]}(Ω,NÁL NÉL,P){\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P})} (Ω,NÁL NÉL,P)=(]0,1[,B(]0,1[),dx){\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P}) = (] 0,1 [, {\ mathcal {B}} (] 0,1 [), dx)}ω∈]0,1[,{\ displaystyle \ omega \ in] 0,1 [,}
x0(ω)=inf{x∈R | μ(]-∞,x])≥ω},Y0(ω)=inf{x∈R | v(]-∞,x])≥ω}.{\ 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 {igazított}}}
Elértük a minimumot X 0 és Y 1 együttes megválasztásához , ahol beállítottuk
ω∈]0,1[,{\ displaystyle \ omega \ in] 0,1 [,}
Y1(ω) = Y0(1-ω).{\ displaystyle Y_ {1} (\ omega) \ = \ Y_ {0} (1- \ omega).}
Jegyzet :
Hardy, Littlewood, és Pólya hívás X 0 és Y 0 a növekvő átrendeződések a μ és ν . Hasonlóképpen, Y 1 jelentése egy csökkenő átrendezése a ν .
Szinte bizonyos egyenlőség, X 0 és Y 0 az egyetlen növekvő térképek meghatározni , amelynek megfelelő valószínűségi törvények ji és ν , Y 1 az egyetlen csökkenő térkép meghatározni , amelynek a valószínűsége törvény ν ...
(Ω,NÁL NÉL,P)=(]0,1[,B(]0,1[),dx){\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P}) = (] 0,1 [, {\ mathcal {B}} (] 0,1 [), dx)}(Ω,NÁL NÉL,P)=(]0,1[,B(]0,1[),dx){\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P}) = (] 0,1 [, {\ mathcal {B}} (] 0,1 [), dx)}
Meghatározás - A Wasserstein távolság (a) L2 a két valószínűség törvényi ji és ν a infimum mennyiségek
E[(x-Y)2] = E[x2]+E[Y2]-2E[xY],{\ displaystyle {\ sqrt {\ mathbb {E} \ left [\ left (XY \ right) ^ {2} \ right]}} = = {{sqrt {\ mathbb {E} \ left [X ^ {2 } \ right] + \ mathbb {E} \ left [Y ^ {2} \ right] -2 \ mathbb {E} \ left [XY \ right]}},}
amikor a két véletlen változó X és Y megfelelő valószínűségi törvényei egyenlően vannak μ-vel és ν -vel, de a pár ( X , Y ) együttes törvénye tetszőleges, tehát azon a valószínűségi téren , ahol X és Y Y jelentése.
(Ω,NÁL NÉL,P){\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P})}
Mint
E[x2]=∫R x2 μ(dx){\ displaystyle \ mathbb {E} \ balra [X ^ {2} \ right] = \ int _ {\ mathbb {R}} \ x ^ {2} \ \ mu (dx)}
nem függ a közös jog, de csak μ , ez a probléma a minimalizálása egyenértékű a korábbi probléma (a lehető legnagyobb mértékű ), feltéve, hogy és mindkettő véges.
E[(x-Y)2]{\ displaystyle \ mathbb {E} \ bal [\ bal (XY \ jobb) ^ {2} \ jobb]}E[xY]{\ displaystyle \ mathbb {E} \ bal [XY \ jobb]}E[x2]=∫R x2 μ(dx){\ displaystyle \ mathbb {E} \ balra [X ^ {2} \ right] = \ int _ {\ mathbb {R}} \ x ^ {2} \ \ mu (dx)}E[Y2]=∫R x2 v(dx){\ displaystyle \ mathbb {E} \ balra [Y ^ {2} \ right] = \ int _ {\ mathbb {R}} \ x ^ {2} \ \ nu (dx)}
Két valószínűségi törvény közötti Wasserstein L2 távolság kiszámításának problémája a Monge - Kantorovitch szállítási probléma egyik változata .
Lásd is
Megjegyzések
-
Lásd a " Landau jelölés " oldalt .
-
Ez az analógia Hardy, Littlewood és Pólya 1988 10.12. És 10.13 .
-
Hardy, Littlewood és Pólya 1988 , 10.12. És 10.13. Szakasz
Kapcsolódó cikkek
Bibliográfia
-
en) GH Hardy , JE Littlewood és G. Pólya , Egyenlőtlenségek , CUP ,1988. február 26, 2 nd ed. ( 1 st ed. 1952), 324 p. ( ISBN 978-0-521-35880-4 , online olvasás ), 10.2. Szakasz
-
(en) J. Michael Steele , A Cauchy-Schwarz mesterkurzus: Bevezetés a matematikai egyenlőtlenségek művészetébe , Cambridge University Press ,2004. április 26, 1 st ed. , 316 p. ( ISBN 0-521-54677-X , online olvasás ), 5.3. Feladat, 78. oldal.
-
(en) Simon French , Sorrend és ütemezés: Bevezetés a Job-Shop matematikájába , John Wiley és fiai, coll. "Ellis Horwood matematikai sorozat és alkalmazásai",1982, 1 st ed. , 245 p. ( ISBN 0-85312-299-7 ), 3.3. Tétel, 37. oldal.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">