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\geqslant 1}$ une suite de nombres réels. On dit que $(u_{n})$ est sous-additive si elle vérifie $u_{n+m}\leqslant 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é

Lemme sous-additif — Soit $(u_{n})_{n\geqslant 1}$ une suite sous-additive. Alors la limite quand n tend vers $+\infty$ de la suite $(u_{n}/n)_{n\geqslant 1}$ existe et l'on a

$\lim _{n\rightarrow +\infty }{\dfrac {u_{n}}{n}}=\inf _{n\geqslant 1}{\dfrac {u_{n}}{n}}\in \mathbb {R} \cup \{-\infty \}.$

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

Démonstration — Soient $q\in \mathbb {N} ^{*}$ et n un entier vérifiant $n\geqslant q$. La division euclidienne de $n$ par $q$ donne $n=k_{n}q+r_{n}$ avec $k_{n}\geqslant 1$ et $0\leqslant r_{n}\leqslant q-1$.

Par sous-additivité de $(u_{n})$ on a donc $u_{n}=u_{(k_{n}-1)q+q+r_{n}}\leqslant (k_{n}-1)u_{q}+u_{q+r_{n}}$. En divisant cette inégalité par $n$, on obtient :

${\begin{aligned}{\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{aligned}}$

Puisque $0\leqslant r_{n}\leqslant q-1$ on a $\lim _{n\to +\infty }{\frac {n-r_{n}-q}{n}}=1$.

En prenant la limite supérieure sur $n$ dans le premier membre et le dernier membre de l'inégalité précédente, on obtient

${\begin{aligned}\limsup _{n\to +\infty }{\frac {u_{n}}{n}}\leqslant {\frac {u_{q}}{q}}.\end{aligned}}$

Puisque cette dernière inégalité est vérifiée pour tout entier $q\geqslant 1$, on en déduit :

${\begin{aligned}\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{aligned}}$

Ce qui termine la preuve.

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.

Théorème — Soit $(u_{n})_{n\geqslant 1}$ une suite de nombres réels telle que, pour tous entiers n et m strictement positifs, $u_{n+m}\geqslant u_{n}+u_{m}$. Alors :

$\lim _{n\rightarrow +\infty }{\frac {u_{n}}{n}}=\sup _{n\geqslant 1}{\frac {u_{n}}{n}}\in \mathbb {R} \cup \{+\infty \}.$

Soit $(u_{n})_{n\geqslant 1}$ une suite de nombres réels positifs telle que, pour tous entiers n et m strictement positifs, $u_{n+m}\leqslant u_{n}u_{m}$. Alors :

$\lim _{n\rightarrow +\infty }{u_{n}}^{\frac {1}{n}}=\inf _{n\geq 1}{u_{n}}^{\frac {1}{n}}\in \mathbb {R} _{+}.$

Soit $(u_{n})_{n\geqslant 1}$ une suite de nombres réels positifs telle que, pour tous entiers n et m strictement positifs, $u_{n+m}\geqslant u_{n}u_{m}$. Alors :

$\lim _{n\rightarrow +\infty }{u_{n}}^{\frac {1}{n}}=\sup _{n\geqslant 1}{u_{n}}^{\frac {1}{n}}\in \mathbb {R} _{+}^{*}\cup \{+\infty \}.$

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 $\mathbb {R} \cup \{+\infty \}$, mais ne prend la valeur $+\infty$ que pour un nombre fini d'entiers n.

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

Théorème — Soit $(u_{n})_{n\geqslant 1}$ une suite de nombres réels. Supposons qu'il existe un réel M tel que, pour tous entiers n et m strictement positifs, $u_{n+m}\leqslant u_{n}+u_{m}+M$. Alors $\lim _{n\rightarrow +\infty }u_{n}/n$ existe.

Il suffit de remarquer que la suite $(u_{n}+M)$ est sous-additive et donc que $\lim _{n\to +\infty }{\frac {u_{n}+M}{n}}$ existe. On en déduit $\lim _{n\to +\infty }{\frac {u_{n}+M}{n}}=\lim _{n\to +\infty }{\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\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 $\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 $\lim _{n\rightarrow +\infty }P\left({\frac {1}{n}}\sum _{k=1}^{n}X_{k}\geqslant x\right)^{\frac {1}{n}}$ existe, et appartient à $[0,1]$. En prenant le logarithme, on peut définir une fonction $I$ de $\mathbb {R}$ dans $[0,+\infty ]$ telle que, pour tout $x$,

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

Marche aléatoire auto-évitante

Soit $d\geq 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})\leq 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 $\lim _{n\rightarrow +\infty }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)\leqslant f_{n}(x)+f_{m}(T^{n}x)$.

Théorème ergodique de Kingman —  Soit $(f_{n})_{n\in \mathbb {N} ^{*}}$ une suite de fonctions sous-additives intégrables sur $(X,T,\mu )$. Alors la limite $\lim _{n\rightarrow +\infty }f_{n}(x)/n$ existe pour $\mu$ - presque tout x, et est T-invariante.

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.