Lemme sous-additif

En analyse réelle, le lemme sous-additif, aussi appelé lemme de Fekete, donne une condition suffisante sur une suite $(u_n)$ à valeurs réelles pour que la limite de $u_n/n$ existe. Il permet de montrer très simplement l'existence de telles limites, et donc de montrer que certaines suites ont asymptotiquement un comportement linéaire ou exponentiel.

Sous-additivité

Soit $(u_n{)}_{n⩾1}$ une suite de nombres réels. On dit que $(u_n)$ est sous-additive si elle vérifie $u_{n+m}⩽u_n+u_m$ pour tous entiers strictement positifs m, n.

On définit de manière analogue les suites sur-additives, sous-multiplicatives et sur-multiplicatives.

Lemme sous-additif

Énoncé

Modèle:ThéorèmeRemarque : si on note $a$ cette limite, on a donc $u_n⩾na$ pour tout $n⩾1$.Modèle:Démonstration

Variantes

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 $(-u_n)$ (respectivement, $\ln (u_n)$ et $-\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 $(u_n)$ est à valeurs dans $ℝ\cup \{+\mathrm{\infty }\}$, mais ne prend la valeur $+\mathrm{\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 $(u_n+M)$ est sous-additive et donc que $\underset{n\to +\mathrm{\infty }}{\lim }\frac{u_n+M}{n}$ existe. On en déduit $\underset{n\to +\mathrm{\infty }}{\lim }\frac{u_n+M}{n}=\underset{n\to +\mathrm{\infty }}{\lim }\frac{u_n}{n}$.

Applications

Le lemme sous-additif a de nombreuses applications, que ce soit en probabilités, en théorie des nombres, ou en combinatoire.

Grandes déviations

Soit $(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 :

$P(\frac{1}{n+m}\sum _{k=1}^{n+m}{X}_k⩾x)⩾P(\frac{1}{n}\sum _{k=1}^n{X}_k⩾x)P(\frac{1}{m}\sum _{k=n+1}^{n+m}{X}_k⩾x)=P(\frac{1}{n}\sum _{k=1}^n{X}_k⩾x)P(\frac{1}{m}\sum _{k=1}^m{X}_k⩾x).$

Ainsi, la suite ${(\ln P(\frac{1}{n}\sum _{k=1}^n{X}_k⩾x))}_{n\in {\mathbb{N}}^{*}}$ est sur-multiplicative. Par conséquent, la limite $\underset{n\to +\mathrm{\infty }}{\lim }P{(\frac{1}{n}\sum _{k=1}^n{X}_k⩾x)}^{\frac{1}{n}}$ existe, et appartient à $[0,1]$. En prenant le logarithme, on peut définir une fonction $I$ de $ℝ$ dans $[0,+\mathrm{\infty }]$ telle que, pour tout $x$,

$\underset{n\to +\mathrm{\infty }}{\lim }\frac{1}{n}\ln P(\frac{1}{n}\sum _{k=1}^n{X}_k⩾x)=-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 $I$.

Marche aléatoire auto-évitante

Modèle:Article détaillé Soit $d\ge 1$ un entier. Le réseau ${\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 ${\mathbb{Z}}^d$ est une suite de n+1 points de ${\mathbb{Z}}^d$ tel que chaque point est relié au suivant. Par exemple, sur ${\mathbb{Z}}^2$, le triplet $((0,1),(1,1),(1,0))$ est un chemin de longueur 3, mais $((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 $c_n({\mathbb{Z}}^d)$ le nombre de chemins auto-évitants partant de l'origine et de longueur n dans ${\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 $c_{n+m}({\mathbb{Z}}^d)\le c_n({\mathbb{Z}}^d)c_m({\mathbb{Z}}^d)$ : la suite $(c_n({\mathbb{Z}}^d){)}_{n\in {\mathbb{N}}^{*}}$ est sous-multiplicative. Par le lemme sous-additif, la limite $\underset{n\to +\mathrm{\infty }}{\lim }{c}_n({\mathbb{Z}}^d{)}^{1/n}$ existe ; elle est appelée constante de connectivité du réseau ${\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 $\sqrt{2+\sqrt{2}}$.

Théorie ergodique

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 $(X,T,\mu )$ un système dynamique préservant la mesure de probabilité $\mu$. Soit $(f_n{)}_{n\in {\mathbb{N}}^{*}}$ une suite de fonctions mesurables sur $X$ à valeurs réelles. On dit que $(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 $f_{n+m}(x)⩽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 :

$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.