Underadditiv lemma
I reel analyse giver Lemma-underadditivet , også kendt lemma fra Fekete, en tilstrækkelig betingelse for, at der findes en efterfølger til de faktiske værdier for grænsen . Det gør det muligt at vise meget simpelt eksistensen af sådanne grænser og derfor at vise, at visse sekvenser har en lineær eller eksponentiel adfærd asymptotisk.
(uikke){\ displaystyle (u_ {n})}
uikke/ikke{\ displaystyle u_ {n} / n}![{\ displaystyle u_ {n} / n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/041670c98d775422eeea325dff0b686f40c1d6c3)
Sub-additivitet
Lad være en sekvens af reelle tal . Vi siger, at det er underadditiv, hvis det opfylder for alle strengt positive heltal m, n .
(uikke)ikke⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
(uikke){\ displaystyle (u_ {n})}
uikke+m⩽uikke+um{\ displaystyle u_ {n + m} \ leqslant u_ {n} + u_ {m}}![{\ displaystyle u_ {n + m} \ leqslant u_ {n} + u_ {m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/050d1f80aac7045dc82172385d6b74ae8c547a49)
Vi definerer på samme måde de overadditive, submultiplikative og overmultiplikative sekvenser.
Underadditiv lemma
Stater
Underadditiv lemma - Lad være en underadditiv sekvens. Derefter findes grænsen, når n har en tendens til sekvensen , og vi har
(uikke)ikke⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
+∞{\ displaystyle + \ infty}
(uikke/ikke)ikke⩾1{\ displaystyle (u_ {n} / n) _ {n \ geqslant 1}}![{\ displaystyle (u_ {n} / n) _ {n \ geqslant 1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c20d30a080d2fa6cd4bfab5e3bea0fab2cd0303)
limikke→+∞uikkeikke=infikke⩾1uikkeikke∈R∪{-∞}.{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {\ dfrac {u_ {n}} {n}} = \ inf _ {n \ geqslant 1} {\ dfrac {u_ {n}} {n}} \ in \ mathbb {R} \ cup \ {- \ infty \}.}
Bemærk: hvis vi bemærker denne grænse, har vi derfor for alt .på{\ displaystyle a}
uikke⩾ikkepå{\ displaystyle u_ {n} \ geqslant na}
ikke⩾1{\ displaystyle n \ geqslant 1}![{\ displaystyle n \ geqslant 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4988f75f48013d159669b6725b19df177ff8a01)
Bevis -
Lad og n være et heltal tilfredsstillende. Den euklidiske opdeling af bygivermedog.
q∈IKKE∗{\ displaystyle q \ in \ mathbb {N} ^ {*}}
ikke⩾q{\ displaystyle n \ geqslant q}
ikke{\ displaystyle n}
q{\ displaystyle q}
ikke=kikkeq+rikke{\ displaystyle n = k_ {n} q + r_ {n}}
kikke⩾1{\ displaystyle k_ {n} \ geqslant 1}
0⩽rikke⩽q-1{\ displaystyle 0 \ leqslant r_ {n} \ leqslant q-1}![{\ displaystyle 0 \ leqslant r_ {n} \ leqslant q-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a7c16d41f4b20cc327eebd67e1baecac4356f3f)
Ved sub-additivitet af har
vi derfor . Ved at dividere denne ulighed med får vi:
(uikke){\ displaystyle (u_ {n})}
uikke=u(kikke-1)q+q+rikke⩽(kikke-1)uq+uq+rikke{\ displaystyle u_ {n} = u _ {(k_ {n} -1) q + q + r_ {n}} \ leqslant (k_ {n} -1) u_ {q} + u_ {q + r_ {n }}}
ikke{\ displaystyle n}![ikke](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
uikkeikke⩽kikke-1ikke⋅uq+uq+rikkeikke=q(kikke-1)ikke⋅uqq+uq+rikkeikke⩽ikke-rikke-qikke⋅uqq+uq+rikkeikke⩽ikke-rikke-qikke⋅uqq+maks0⩽jeg⩽q-1uq+jegikke.{\ displaystyle {\ begin {align} {\ frac {u_ {n}} {n}} & \ leqslant {\ frac {k_ {n} -1} {n}} \ cdot u_ {q} + {\ frac {u_ {q + r_ {n}}} {n}} = {\ frac {q (k_ {n} -1)} {n}} \ cdot {\ frac {u_ {q}} {q}} + {\ frac {u_ {q + r_ {n}}} {n}} \\ & \ leqslant {\ frac {n-r_ {n} -q} {n}} \ cdot {\ frac {u_ {q} } {q}} + {\ frac {u_ {q + r_ {n}}} {n}} \ leqslant {\ frac {n-r_ {n} -q} {n}} \ cdot {\ frac {u_ {q}} {q}} + {\ frac {{\ underset {0 \ leqslant i \ leqslant q-1} {\ max}} u_ {q + i}} {n}}. \ slut {justeret}} }![{\ displaystyle {\ begin {align} {\ frac {u_ {n}} {n}} & \ leqslant {\ frac {k_ {n} -1} {n}} \ cdot u_ {q} + {\ frac {u_ {q + r_ {n}}} {n}} = {\ frac {q (k_ {n} -1)} {n}} \ cdot {\ frac {u_ {q}} {q}} + {\ frac {u_ {q + r_ {n}}} {n}} \\ & \ leqslant {\ frac {n-r_ {n} -q} {n}} \ cdot {\ frac {u_ {q} } {q}} + {\ frac {u_ {q + r_ {n}}} {n}} \ leqslant {\ frac {n-r_ {n} -q} {n}} \ cdot {\ frac {u_ {q}} {q}} + {\ frac {{\ underset {0 \ leqslant i \ leqslant q-1} {\ max}} u_ {q + i}} {n}}. \ slut {justeret}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/93d86988f204e68815a175fac312ee904bfec0f5)
Da vi har gjort det .
0⩽rikke⩽q-1{\ displaystyle 0 \ leqslant r_ {n} \ leqslant q-1}
limikke→+∞ikke-rikke-qikke=1{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {n-r_ {n} -q} {n}} = 1}![{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {n-r_ {n} -q} {n}} = 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/162dd34656dc821ccd1d618473e4c31cff1c8093)
Ved at tage den øvre grænse for det første medlem og det sidste medlem af den foregående ulighed opnår vi
ikke{\ displaystyle n}![ikke](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
lim supikke→+∞uikkeikke⩽uqq.{\ displaystyle {\ begin {align} \ limsup _ {n \ to + \ infty} {\ frac {u_ {n}} {n}} \ leqslant {\ frac {u_ {q}} {q}}. \ slutning {align}}}![{\ displaystyle {\ begin {align} \ limsup _ {n \ to + \ infty} {\ frac {u_ {n}} {n}} \ leqslant {\ frac {u_ {q}} {q}}. \ slutning {align}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d26ab10db94ff899f03874cc1d4005d765f01720)
Da denne sidste ulighed er bekræftet for alle heltal , udleder vi:
q⩾1{\ displaystyle q \ geqslant 1}![{\ displaystyle q \ geqslant 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/054270da5e21e08aeb9a70af712d87bd11267955)
lim supikke→+∞uikkeikke⩽infq⩾1uqq⩽lim infq→+∞uqq,{\ displaystyle {\ begin {align} \ limsup _ {n \ to + \ infty} {\ frac {u_ {n}} {n}} \ leqslant \ inf _ {q \ geqslant 1} {\ frac {u_ { q}} {q}} \ leqslant \ liminf _ {q \ to + \ infty} {\ frac {u_ {q}} {q}}, \ slut {justeret}}}![{\ displaystyle {\ begin {align} \ limsup _ {n \ to + \ infty} {\ frac {u_ {n}} {n}} \ leqslant \ inf _ {q \ geqslant 1} {\ frac {u_ { q}} {q}} \ leqslant \ liminf _ {q \ to + \ infty} {\ frac {u_ {q}} {q}}, \ slut {justeret}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/115af9b7a43e916bb8173560d30bb12ef74cfee6)
Hvilket ender beviset.
Varianter
Det subadditive lemma har mange variationer. Det mest direkte vedrører overadditiv- og under- eller overmultiplikative sekvenser. Beviset for de tre følgende resultater udføres ved at bemærke, at (henholdsvis og ) er underadditive sekvenser.
(-uikke){\ displaystyle (-u_ {n})}
ln(uikke){\ displaystyle \ ln (u_ {n})}
-ln(uikke){\ displaystyle - \ ln (u_ {n})}![{\ displaystyle - \ ln (u_ {n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/408945d1c888f8aa26b882a7c74c0ff1aeb81f22)
Sætning - Lad en reel talrækkefølge sådan, at for alle heltal n og m strengt positive . Så:
(uikke)ikke⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
uikke+m⩾uikke+um{\ displaystyle u_ {n + m} \ geqslant u_ {n} + u_ {m}}![{\ displaystyle u_ {n + m} \ geqslant u_ {n} + u_ {m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abc62efb4962ef858f43528c96437d48523689cd)
limikke→+∞uikkeikke=supikke⩾1uikkeikke∈R∪{+∞}.{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {\ frac {u_ {n}} {n}} = \ sup _ {n \ geqslant 1} {\ frac {u_ {n}} {n}} \ in \ mathbb {R} \ cup \ {+ \ infty \}.}
Er en række af reelle positive tal sådan, at for alle heltal n og m strengt positive . Så:
(uikke)ikke⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
uikke+m⩽uikkeum{\ displaystyle u_ {n + m} \ leqslant u_ {n} u_ {m}}![{\ displaystyle u_ {n + m} \ leqslant u_ {n} u_ {m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57d7aedaf0795b0eee51fc08889a9f801cdd83a9)
limikke→+∞uikke1ikke=infikke≥1uikke1ikke∈R+.{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {u_ {n}} ^ {\ frac {1} {n}} = \ inf _ {n \ geq 1} {u_ {n}} ^ {\ frac {1} {n}} \ in \ mathbb {R} _ {+}.}
Er en række af reelle positive tal sådan, at for alle heltal n og m strengt positive . Så:
(uikke)ikke⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
uikke+m⩾uikkeum{\ displaystyle u_ {n + m} \ geqslant u_ {n} u_ {m}}![{\ displaystyle u_ {n + m} \ geqslant u_ {n} u_ {m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22a03c9feab06eb8bab052cbb5e4fb570db2eb2c)
limikke→+∞uikke1ikke=supikke⩾1uikke1ikke∈R+∗∪{+∞}.{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {u_ {n}} ^ {\ frac {1} {n}} = \ sup _ {n \ geqslant 1} {u_ {n}} ^ {\ frac {1} {n}} \ in \ mathbb {R} _ {+} ^ {*} \ cup \ {+ \ infty \}.}
Andre varianter består i at svække antagelserne om det subadditive lemma. For eksempel kan vi antage, at sekvensen har værdier i , men kun tager værdien for et endeligt antal heltal n .
(uikke){\ displaystyle (u_ {n})}
R∪{+∞}{\ displaystyle \ mathbb {R} \ cup \ {+ \ infty \}}
+∞{\ displaystyle + \ infty}![+ \ infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/bddbb0e4420a7e744cf71bd71216e11b0bf88831)
En tæt konklusion forbliver gyldig, hvis vi svækker betingelsen for subadditivitet:
Sætning - Lad være en rækkefølge af reelle tal. Antag at der er væsentlig M sådan, at for alle heltal n og m strengt positive . Så eksisterer.
(uikke)ikke⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
uikke+m⩽uikke+um+M{\ displaystyle u_ {n + m} \ leqslant u_ {n} + u_ {m} + M}
limikke→+∞uikke/ikke{\ displaystyle \ lim _ {n \ rightarrow + \ infty} u_ {n} / n}![{\ displaystyle \ lim _ {n \ rightarrow + \ infty} u_ {n} / n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f52806ac2f21adca92d08b0b8103f2d1c93bdcca)
Det er tilstrækkeligt at bemærke, at sekvensen er underadditiv og derfor eksisterer. Vi udleder .
(uikke+M){\ displaystyle (u_ {n} + M)}
limikke→+∞uikke+Mikke{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {u_ {n} + M} {n}}}
limikke→+∞uikke+Mikke=limikke→+∞uikkeikke{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {u_ {n} + M} {n}} = \ lim _ {n \ to + \ infty} {\ frac {u_ {n}} {ikke}}}![{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {u_ {n} + M} {n}} = \ lim _ {n \ to + \ infty} {\ frac {u_ {n}} {ikke}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b379dafa1ed3d923818513e2777e27247fafdde)
Ansøgninger
Det subadditive lemma har mange anvendelser, hvad enten det er sandsynlighed, talteori eller kombinatorik.
Store afvigelser
Lad være en sekvens af identisk fordelte uafhængige tilfældige variabler med reelle værdier, integrerbare og med nul gennemsnit. Lad x være et positivt reelt tal. Lad n og m være to strengt positive heltal. Vi bemærker, at:
(xikke)ikke∈IKKE{\ displaystyle (X_ {n}) _ {n \ in \ mathbb {N}}}![(X_ {n}) _ {{n \ in \ mathbb {N}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f72d615b59119dee59b0e70748e31345311103c)
P(1ikke+m∑k=1ikke+mxk⩾x)⩾P(1ikke∑k=1ikkexk⩾x)P(1m∑k=ikke+1ikke+mxk⩾x)=P(1ikke∑k=1ikkexk⩾x)P(1m∑k=1mxk⩾x).{\ displaystyle P \ left ({\ frac {1} {n + m}} \ sum _ {k = 1} ^ {n + m} X_ {k} \ geqslant x \ right) \ geqslant P \ left ({ \ frac {1} {n}} \ sum _ {k = 1} ^ {n} X_ {k} \ geqslant x \ right) P \ left ({\ frac {1} {m}} \ sum _ {k = n + 1} ^ {n + m} X_ {k} \ geqslant x \ right) = P \ left ({\ frac {1} {n}} \ sum _ {k = 1} ^ {n} X_ { k} \ geqslant x \ right) P \ left ({\ frac {1} {m}} \ sum _ {k = 1} ^ {m} X_ {k} \ geqslant x \ right).}
Således er sekvensen overmultiplikativ. Derfor findes grænsen og hører til . Ved at tage logaritmen, kan vi definere en funktion af i sådan, at for alle ,
log(P(1ikke∑k=1ikkexk⩾x))ikke∈IKKE∗{\ displaystyle \ log \ left (P \ left ({\ frac {1} {n}} \ sum _ {k = 1} ^ {n} X_ {k} \ geqslant x \ right) \ right) _ {n \ in \ mathbb {N} ^ {*}}}
limikke→+∞P(1ikke∑k=1ikkexk⩾x)1ikke{\ displaystyle \ lim _ {n \ rightarrow + \ infty} P \ left ({\ frac {1} {n}} \ sum _ {k = 1} ^ {n} X_ {k} \ geqslant x \ right) ^ {\ frac {1} {n}}}
[0,1]{\ displaystyle [0,1]}
jeg{\ displaystyle I}
R{\ displaystyle \ mathbb {R}}
[0,+∞]{\ displaystyle [0, + \ infty]}
x{\ displaystyle x}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
limikke→+∞1ikkelnP(1ikke∑k=1ikkexk⩾x)=-jeg(x).{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {\ frac {1} {n}} \ ln P \ left ({\ frac {1} {n}} \ sum _ {k = 1} ^ { n} X_ {k} \ geqslant x \ right) = - I (x).}
De principper for store afvigelser er raffinementer af dette resultat: de tillader, blandt andet til at beregne hastigheden funktion .
jeg{\ displaystyle I}![jeg](https://wikimedia.org/api/rest_v1/media/math/render/svg/535ea7fc4134a31cbe2251d9d3511374bc41be9f)
Selvundgåelse tilfældig gåtur
Lad være et heltal. Netværket kan ses som en graf, dvs. to punkter er forbundet, hvis og kun hvis de er i en afstand af 1 fra hinanden. En sti med længden n over er en sekvens på n + 1 punkter, således at hvert punkt er forbundet til det næste. For eksempel er tripletten en sti med længde 3 , men er ikke en sti. En sti siges at være selvundgåelig, hvis den ikke passerer flere gange over det samme toppunkt i grafen. Lad n være et strengt positivt heltal. Lad være antallet af selvundgåelige stier, der starter fra oprindelsen og længden n i . En selvundgåelig sti med længde n + m er altid en sammenkædning af en selvundgåelig sti med længde n og en selvundgåelig sti med længde m . Selvom det betyder at oversætte disse stier, kan vi antage, at de starter fra oprindelsen. Derefter : sekvensen er submultiplikativ. Ved det subadditive lemma findes grænsen ; det kaldes konstant for netværksforbindelsen .
d≥1{\ displaystyle d \ geq 1}
Zd{\ displaystyle \ mathbb {Z} ^ {d}}
Zd{\ displaystyle \ mathbb {Z} ^ {d}}
Zd{\ displaystyle \ mathbb {Z} ^ {d}}
Z2{\ displaystyle \ mathbb {Z} ^ {2}}
((0,1),(1,1),(1,0)){\ displaystyle ((0,1), (1,1), (1,0))}
((0,1),(1,0),(1,1)){\ displaystyle ((0,1), (1,0), (1,1))}
vs.ikke(Zd){\ displaystyle c_ {n} (\ mathbb {Z} ^ {d})}
Zd{\ displaystyle \ mathbb {Z} ^ {d}}
vs.ikke+m(Zd)≤vs.ikke(Zd)vs.m(Zd){\ displaystyle c_ {n + m} (\ mathbb {Z} ^ {d}) \ leq c_ {n} (\ mathbb {Z} ^ {d}) c_ {m} (\ mathbb {Z} ^ {d })}
(vs.ikke(Zd))ikke∈IKKE∗{\ displaystyle (c_ {n} (\ mathbb {Z} ^ {d})) _ {n \ in \ mathbb {N} ^ {*}}}
limikke→+∞vs.ikke(Zd)1/ikke{\ displaystyle \ lim _ {n \ rightarrow + \ infty} c_ {n} (\ mathbb {Z} ^ {d}) ^ {1 / n}}
Zd{\ displaystyle \ mathbb {Z} ^ {d}}![{\ displaystyle \ mathbb {Z} ^ {d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/649f796a3703c840a3c78c6c6eb2e31018e5eaa8)
Mere generelt kan forbindelseskonstanten for et almindeligt netværk defineres på samme måde . Vi ved for eksempel, at forbindelsen konstant af et sekskantet netværk i planet er .
2+2{\ displaystyle {\ sqrt {2 + {\ sqrt {2}}}}}![{\ sqrt {2 + {\ sqrt {2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d80bc28c75f4671785f2625a0565ce26efcff038)
Ergodisk teori
Lignende resultater til det subadditive lemma findes i ergodisk teori , såsom Kingmans sætning, en generalisering af Birkhoffs ergodiske sætning . Lad være et dynamisk system, der bevarer sandsynlighedsmålingen . Lad være en række målbare funktioner til reelle værdier. Vi siger, at er subadditive hvis for alle heltal n og m strengt positive og for næsten alle x i X , vi har .
(x,T,μ){\ displaystyle (X, T, \ mu)}
μ{\ displaystyle \ mu}
(fikke)ikke∈IKKE∗{\ displaystyle (f_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}
x{\ displaystyle X}
(fikke)ikke∈IKKE∗{\ displaystyle (f_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}
fikke+m(x)⩽fikke(x)+fm(Tikkex){\ displaystyle f_ {n + m} (x) \ leqslant f_ {n} (x) + f_ {m} (T ^ {n} x)}![{\ displaystyle f_ {n + m} (x) \ leqslant f_ {n} (x) + f_ {m} (T ^ {n} x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fd91d3cbd2b103023b0fe215bc9bd7a289c38fb)
Kingmans ergodiske sætning -
Lad være en sekvens af underadditive funktioner, der kan integreres i . Så findes grænsen for - næsten alle x og er T -variant.
(fikke)ikke∈IKKE∗{\ displaystyle (f_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}
(x,T,μ){\ displaystyle (X, T, \ mu)}
limikke→+∞fikke(x)/ikke{\ displaystyle \ lim _ {n \ rightarrow + \ infty} f_ {n} (x) / n}
μ{\ displaystyle \ mu}![\ mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
Især hvis f er en integrerbar funktion på X , så er rækkefølgen af funktioner defineret af:
fikke(x)=∑k=0ikke-1f(Tkx){\ displaystyle f_ {n} (x) = \ sum _ {k = 0} ^ {n-1} f (T ^ {k} x)}
er subadditiv (såvel som overadditiv). Vi finder derfor den næsten sikre konvergens af Birkhoff- summer , selvom denne sætning ikke giver grænsen.
Noter og referencer
-
H. Duminil-Copin og S. Smirnov, Bindekonstanten af bikagegitteret er lig2+2{\ displaystyle {\ sqrt {2 + {\ sqrt {2}}}}}
med 2010
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">