Lemme sous-additif

Remarque : si on note ${\displaystyle a}$ cette limite, on a donc ${\displaystyle u_{n}\geqslant na}$ pour tout ${\displaystyle n\geqslant 1}$.

Le lemme sous-additif a de nombreuses variantes. Les plus directes concernent les suites sur-additives et sous- ou sur-multiplicatives. La démonstration des trois résultats suivants se fait en remarquant que ${\displaystyle (-u_{n})}$ (respectivement, ${\displaystyle \ln(u_{n})}$ et ${\displaystyle -\ln(u_{n})}$) sont des suites sous-additives.

D'autres variantes consistent à affaiblir les hypothèses du lemme sous-additif. Par exemple, on peut supposer que la suite ${\displaystyle (u_{n})}$ est à valeurs dans ${\displaystyle \mathbb {R} \cup \{+\infty \}}$, mais ne prend la valeur ${\displaystyle +\infty }$ que pour un nombre fini d'entiers n.

Une conclusion proche reste valable si on affaiblit la condition de sous-additivité :

Il suffit de remarquer que la suite ${\displaystyle (u_{n}+M)}$ est sous-additive et donc que ${\displaystyle \lim _{n\to +\infty }{\frac {u_{n}+M}{n}}}$ existe. On en déduit ${\displaystyle \lim _{n\to +\infty }{\frac {u_{n}+M}{n}}=\lim _{n\to +\infty }{\frac {u_{n}}{n}}}$.

Soit ${\displaystyle (X_{n})_{n\in \mathbb {N} }}$ une suite de variables aléatoires indépendantes identiquement distribuées, à valeurs réelles, intégrables et de moyenne nulle. Soit x un nombre réel positif. Soient n et m deux entiers strictement positifs. On remarque que :

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

Ainsi, la suite ${\displaystyle \left(\ln P\left({\frac {1}{n}}\sum _{k=1}^{n}X_{k}\geqslant x\right)\right)_{n\in \mathbb {N} ^{*}}}$ est sur-multiplicative. Par conséquent, la limite ${\displaystyle \lim _{n\rightarrow +\infty }P\left({\frac {1}{n}}\sum _{k=1}^{n}X_{k}\geqslant x\right)^{\frac {1}{n}}}$ existe, et appartient à ${\displaystyle [0,1]}$. En prenant le logarithme, on peut définir une fonction ${\displaystyle I}$ de ${\displaystyle \mathbb {R} }$ dans ${\displaystyle [0,+\infty ]}$ telle que, pour tout ${\displaystyle 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).}$

Les principes de grandes déviations sont des raffinements de ce résultat : ils permettent entre autres de calculer la fonction de taux ${\displaystyle I}$.

Soit ${\displaystyle d\geq 1}$ un entier. Le réseau ${\displaystyle \mathbb {Z} ^{d}}$ peut être vu comme un graphe, c'est-à-dire que deux points sont reliés si et seulement si ils sont à distance 1 l'un de l'autre. Un chemin de longueur n sur ${\displaystyle \mathbb {Z} ^{d}}$ est une suite de n+1 points de ${\displaystyle \mathbb {Z} ^{d}}$ tel que chaque point est relié au suivant. Par exemple, sur ${\displaystyle \mathbb {Z} ^{2}}$, le triplet ${\displaystyle ((0,1),(1,1),(1,0))}$ est un chemin de longueur 3, mais ${\displaystyle ((0,1),(1,0),(1,1))}$ n'est pas un chemin. Un chemin est dit auto-évitant s'il ne passe pas plusieurs fois en un même sommet du graphe. Soit n un entier strictement positif. Soit ${\displaystyle c_{n}(\mathbb {Z} ^{d})}$ le nombre de chemins auto-évitants partant de l'origine et de longueur n dans ${\displaystyle \mathbb {Z} ^{d}}$. Un chemin auto-évitant de longueur n+m est toujours une concaténation d'un chemin auto-évitant de longueur n et d'un chemin auto-évitant de longueur m. Quitte à translater ces chemins, on peut supposer qu'ils partent de l'origine. Alors ${\displaystyle c_{n+m}(\mathbb {Z} ^{d})\leq c_{n}(\mathbb {Z} ^{d})c_{m}(\mathbb {Z} ^{d})}$ : la suite ${\displaystyle (c_{n}(\mathbb {Z} ^{d}))_{n\in \mathbb {N} ^{*}}}$ est sous-multiplicative. Par le lemme sous-additif, la limite ${\displaystyle \lim _{n\rightarrow +\infty }c_{n}(\mathbb {Z} ^{d})^{1/n}}$ existe ; elle est appelée constante de connectivité du réseau ${\displaystyle \mathbb {Z} ^{d}}$.

Plus généralement, on peut définir de façon identique la constante de connectivité d'un réseau régulier. On sait par exemple que la constante de connectivité d'un réseau hexagonal dans le plan est ${\displaystyle {\sqrt {2+{\sqrt {2}}}}}$[1].

Des résultats semblables au lemme sous-additif existent en théorie ergodique, tels que le théorème de Kingman, une généralisation du théorème ergodique de Birkhoff. Soit ${\displaystyle (X,T,\mu )}$ un système dynamique préservant la mesure de probabilité ${\displaystyle \mu }$. Soit ${\displaystyle (f_{n})_{n\in \mathbb {N} ^{*}}}$ une suite de fonctions mesurables sur ${\displaystyle X}$ à valeurs réelles. On dit que ${\displaystyle (f_{n})_{n\in \mathbb {N} ^{*}}}$ est sous-additive si, pour tous entiers n et m strictement positif et pour presque tout x dans X, on a ${\displaystyle f_{n+m}(x)\leqslant f_{n}(x)+f_{m}(T^{n}x)}$.

En particulier, si f est une fonction intégrable sur X, alors la suite de fonctions définie par :

${\displaystyle f_{n}(x)=\sum _{k=0}^{n-1}f(T^{k}x)}$

est sous-additive (ainsi que sur-additive). On retrouve donc la convergence presque sûre des sommes de Birkhoff, même si ce théorème n'en donne pas la limite.