Lemma subadditivo
In analisi reale , il subadditivo Lemma , noto anche lemma di Fekete, fornisce una condizione sufficiente su un seguito ai valori effettivi per il limite esiste. Permette di mostrare molto semplicemente l'esistenza di tali limiti, e quindi di mostrare che certe sequenze hanno un comportamento asintoticamente lineare o esponenziale.
(unon){\ displaystyle (u_ {n})}
unon/non{\ displaystyle u_ {n} / n}![{\ displaystyle u_ {n} / n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/041670c98d775422eeea325dff0b686f40c1d6c3)
Sub-additività
Sia una sequenza di numeri reali . Diciamo che è subadditivo se soddisfa tutti gli interi strettamente positivi m, n .
(unon)non⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
(unon){\ displaystyle (u_ {n})}
unon+m⩽unon+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)
Definiamo in modo simile le sequenze iperadditive, sub-moltiplicative e iper-moltiplicative.
Lemma subadditivo
stati
Lemma subadditivo - Sia una sequenza subadditiva. Allora il limite quando n tende verso la sequenza esiste e abbiamo
(unon)non⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
+∞{\ displaystyle + \ infty}
(unon/non)non⩾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)
limnon→+∞unonnon=infnon⩾1unonnon∈R∪{-∞}.{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {\ dfrac {u_ {n}} {n}} = \ inf _ {n \ geqslant 1} {\ dfrac {u_ {n}} {n}} \ in \ mathbb {R} \ cup \ {- \ infty \}.}
Nota: se notiamo questo limite, abbiamo quindi per tutto .a{\ displaystyle a}
unon⩾nona{\ displaystyle u_ {n} \ geqslant na}
non⩾1{\ displaystyle n \ geqslant 1}![{\ displaystyle n \ geqslant 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4988f75f48013d159669b6725b19df177ff8a01)
Proof -
Let e n sia un intero soddisfacente. La divisione euclidea di perdàcone.
q∈NON∗{\ displaystyle q \ in \ mathbb {N} ^ {*}}
non⩾q{\ displaystyle n \ geqslant q}
non{\ displaystyle n}
q{\ displaystyle q}
non=Knonq+rnon{\ displaystyle n = k_ {n} q + r_ {n}}
Knon⩾1{\ displaystyle k_ {n} \ geqslant 1}
0⩽rnon⩽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)
Per sub-additività di
abbiamo quindi . Dividendo questa disuguaglianza per , otteniamo:
(unon){\ displaystyle (u_ {n})}
unon=u(Knon-1)q+q+rnon⩽(Knon-1)uq+uq+rnon{\ Displaystyle u_ {n} = u _ {(k_ {n} -1) q + q + r_ {n}} \ leqslant (k_ {n} -1) u_ {q} + u_ {q + r_ {n }}}
non{\ displaystyle n}![non](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
unonnon⩽Knon-1non⋅uq+uq+rnonnon=q(Knon-1)non⋅uqq+uq+rnonnon⩽non-rnon-qnon⋅uqq+uq+rnonnon⩽non-rnon-qnon⋅uqq+max0⩽io⩽q-1uq+ionon.{\ 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}}. \ end {align}} }![{\ 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}}. \ end {align}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/93d86988f204e68815a175fac312ee904bfec0f5)
Dal momento che abbiamo .
0⩽rnon⩽q-1{\ displaystyle 0 \ leqslant r_ {n} \ leqslant q-1}
limnon→+∞non-rnon-qnon=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)
Prendendo il limite superiore sul primo elemento e l'ultimo membro della disuguaglianza precedente, otteniamo
non{\ displaystyle n}![non](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
lim supnon→+∞unonnon⩽uqq.{\ displaystyle {\ begin {align} \ limsup _ {n \ to + \ infty} {\ frac {u_ {n}} {n}} \ leqslant {\ frac {u_ {q}} {q}}. \ fine {allineato}}}![{\ displaystyle {\ begin {align} \ limsup _ {n \ to + \ infty} {\ frac {u_ {n}} {n}} \ leqslant {\ frac {u_ {q}} {q}}. \ fine {allineato}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d26ab10db94ff899f03874cc1d4005d765f01720)
Poiché quest'ultima disuguaglianza è verificata per tutti gli interi , deduciamo:
q⩾1{\ displaystyle q \ geqslant 1}![{\ displaystyle q \ geqslant 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/054270da5e21e08aeb9a70af712d87bd11267955)
lim supnon→+∞unonnon⩽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}}, \ end {align}}}![{\ 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}}, \ end {align}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/115af9b7a43e916bb8173560d30bb12ef74cfee6)
Il che pone fine alla prova.
Varianti
Il lemma subadditivo ha molte varianti. Le più dirette riguardano le sequenze sovra-additive e sotto- o iper-moltiplicative. La prova dei tre risultati seguenti viene eseguita notando che (rispettivamente, e ) sono sequenze subadditive.
(-unon){\ displaystyle (-u_ {n})}
ln(unon){\ displaystyle \ ln (u_ {n})}
-ln(unon){\ displaystyle - \ ln (u_ {n})}![{\ displaystyle - \ ln (u_ {n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/408945d1c888f8aa26b882a7c74c0ff1aeb81f22)
Teorema - Sia una sequenza di numeri reali tale che per tutti gli interi n e m sia strettamente positiva . Allora :
(unon)non⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
unon+m⩾unon+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)
limnon→+∞unonnon=supnon⩾1unonnon∈R∪{+∞}.{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {\ frac {u_ {n}} {n}} = \ sup _ {n \ geqslant 1} {\ frac {u_ {n}} {n}} \ in \ mathbb {R} \ cup \ {+ \ infty \}.}
È una sequenza di numeri positivi reali tale che per tutti gli interi n e m strettamente positivi . Allora :
(unon)non⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
unon+m⩽unonum{\ 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)
limnon→+∞unon1non=infnon≥1unon1non∈R+.{\ displaystyle \ lim _ {n \ rightarrow + \ infty} {u_ {n}} ^ {\ frac {1} {n}} = \ inf _ {n \ geq 1} {u_ {n}} ^ {\ frac {1} {n}} \ in \ mathbb {R} _ {+}.}
È una sequenza di numeri positivi reali tale che per tutti gli interi n e m strettamente positivi . Allora :
(unon)non⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
unon+m⩾unonum{\ 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)
limnon→+∞unon1non=supnon⩾1unon1non∈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 \}.}
Altre varianti consistono nell'indebolire le ipotesi del lemma subadditivo. Ad esempio, possiamo supporre che la sequenza abbia valori in , ma prenda solo il valore per un numero finito di interi n .
(unon){\ displaystyle (u_ {n})}
R∪{+∞}{\ displaystyle \ mathbb {R} \ cup \ {+ \ infty \}}
+∞{\ displaystyle + \ infty}![+ \ infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/bddbb0e4420a7e744cf71bd71216e11b0bf88831)
Una conclusione ravvicinata resta valida se indeboliamo la condizione di subadditività:
Teorema - Sia una sequenza di numeri reali. Supponiamo che ci sia M sostanziale tale che per tutti gli interi n e m sia strettamente positivo . Quindi esiste.
(unon)non⩾1{\ displaystyle (u_ {n}) _ {n \ geqslant 1}}
unon+m⩽unon+um+M{\ displaystyle u_ {n + m} \ leqslant u_ {n} + u_ {m} + M}
limnon→+∞unon/non{\ 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)
Basta notare che la sequenza è subadditiva e quindi che esiste. Ne deduciamo .
(unon+M){\ displaystyle (u_ {n} + M)}
limnon→+∞unon+Mnon{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {u_ {n} + M} {n}}}
limnon→+∞unon+Mnon=limnon→+∞unonnon{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {u_ {n} + M} {n}} = \ lim _ {n \ to + \ infty} {\ frac {u_ {n}} {non}}}![{\ displaystyle \ lim _ {n \ to + \ infty} {\ frac {u_ {n} + M} {n}} = \ lim _ {n \ to + \ infty} {\ frac {u_ {n}} {non}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b379dafa1ed3d923818513e2777e27247fafdde)
Applicazioni
Il lemma subadditivo ha molte applicazioni, sia in probabilità, teoria dei numeri o calcolo combinatorio.
Grandi deviazioni
Sia una sequenza di variabili casuali indipendenti distribuite in modo identico, con valori reali, integrabili e con media zero. Sia x un numero reale positivo. Siano n e m due interi strettamente positivi. Notiamo che:
(Xnon)non∈NON{\ 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(1non+m∑K=1non+mXK⩾X)⩾P(1non∑K=1nonXK⩾X)P(1m∑K=non+1non+mXK⩾X)=P(1non∑K=1nonXK⩾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).}
Pertanto, la sequenza è iper-moltiplicativa. Pertanto, il limite esiste e appartiene a . Prendendo il logaritmo, possiamo definire una funzione di in tale che, per tutti ,
log(P(1non∑K=1nonXK⩾X))non∈NON∗{\ displaystyle \ log \ left (P \ left ({\ frac {1} {n}} \ sum _ {k = 1} ^ {n} X_ {k} \ geqslant x \ right) \ right) _ {n \ in \ mathbb {N} ^ {*}}}
limnon→+∞P(1non∑K=1nonXK⩾X)1non{\ 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]}
io{\ 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)
limnon→+∞1nonlnP(1non∑K=1nonXK⩾X)=-io(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).}
I principi delle grandi deviazioni sono perfezionamenti di questo risultato: consentono, tra le altre cose, di calcolare la funzione di tasso .
io{\ displaystyle I}![io](https://wikimedia.org/api/rest_v1/media/math/render/svg/535ea7fc4134a31cbe2251d9d3511374bc41be9f)
Camminata casuale auto-evitante
Sia un numero intero. La rete può essere vista come un grafico, ovvero due punti sono collegati se e solo se si trovano a una distanza di 1 l' uno dall'altro. Un percorso di lunghezza n su è una sequenza di n + 1 punti tale che ogni punto è connesso al successivo. Ad esempio, su , la terzina è un percorso di lunghezza 3 , ma non è un percorso. Si dice che un percorso si eviti da solo se non passa più volte sullo stesso vertice del grafico. Sia n un intero strettamente positivo. Sia il numero di cammini autoevitanti a partire dall'origine e di lunghezza n in . Un percorso di auto-evitando di lunghezza n + m è sempre una concatenazione di un percorso di auto-evitando di lunghezza n e un percorso di auto-evitando di lunghezza m . Anche se significa tradurre questi percorsi, possiamo presumere che partano dall'origine. Quindi : la sequenza è sub-moltiplicativa. Per il lemma subadditivo, il limite esiste; si chiama costante di connettività di rete .
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))}
vsnon(Zd){\ displaystyle c_ {n} (\ mathbb {Z} ^ {d})}
Zd{\ displaystyle \ mathbb {Z} ^ {d}}
vsnon+m(Zd)≤vsnon(Zd)vsm(Zd){\ displaystyle c_ {n + m} (\ mathbb {Z} ^ {d}) \ leq c_ {n} (\ mathbb {Z} ^ {d}) c_ {m} (\ mathbb {Z} ^ {d })}
(vsnon(Zd))non∈NON∗{\ displaystyle (c_ {n} (\ mathbb {Z} ^ {d})) _ {n \ in \ mathbb {N} ^ {*}}}
limnon→+∞vsnon(Zd)1/non{\ 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)
Più in generale, la costante di connettività di una rete regolare può essere definita allo stesso modo . Sappiamo ad esempio che la costante di connettività di una rete esagonale nell'aereo è .
2+2{\ displaystyle {\ sqrt {2 + {\ sqrt {2}}}}}![{\ sqrt {2 + {\ sqrt {2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d80bc28c75f4671785f2625a0565ce26efcff038)
Teoria ergodica
Risultati simili al lemma subadditivo esistono nella teoria ergodica , come il teorema di Kingman, una generalizzazione del teorema ergodico di Birkhoff . Sia un sistema dinamico che preserva la misura di probabilità . Sia una serie di funzioni misurabili su valori reali. Diciamo che è subadditivo se, per tutti gli interi n ed m strettamente positivi e per quasi tutti gli x in X , abbiamo .
(X,T,μ){\ displaystyle (X, T, \ mu)}
μ{\ displaystyle \ mu}
(fnon)non∈NON∗{\ displaystyle (f_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}
X{\ displaystyle X}
(fnon)non∈NON∗{\ displaystyle (f_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}
fnon+m(X)⩽fnon(X)+fm(TnonX){\ 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)
Teorema ergodico di Kingman -
Sia una sequenza di funzioni subadditive integrabili su . Allora il limite esiste per quasi tutte le x ed è T -invariant.
(fnon)non∈NON∗{\ displaystyle (f_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}
(X,T,μ){\ displaystyle (X, T, \ mu)}
limnon→+∞fnon(X)/non{\ Displaystyle \ lim _ {n \ rightarrow + \ infty} f_ {n} (x) / n}
μ{\ displaystyle \ mu}![\ mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
In particolare, se f è una funzione integrabile su X , allora la sequenza di funzioni definita da:
fnon(X)=∑K=0non-1f(TKX){\ displaystyle f_ {n} (x) = \ sum _ {k = 0} ^ {n-1} f (T ^ {k} x)}
è un subadditivo (oltre che un eccesso di additivo). Troviamo quindi la convergenza quasi certa delle somme di Birkhoff , anche se questo teorema non dà il limite.
Note e riferimenti
-
H. Duminil-Copin e S. Smirnov, La costante connettiva del reticolo a nido d'ape è uguale2+2{\ displaystyle {\ sqrt {2 + {\ sqrt {2}}}}}
, 2010
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">