Un lemme combinatoire et ses applications aux marches aléatoires.

Etant donné $n$ réels $x_1,ldots,x_n$, et deux permutations $sigma$ et $ au$ de ${1,ldots,n}$, on considère les quantités
$$S(sigma,x) = max(0 , x_{sigma(1)} , ldots , x_{sigma(1)} + cdots + x_{sigma(n)})$$
$$T( au,x) = sum_C Big[ sum_{i in C} x_i Big]_+ ,$$
où $C$ parcourt les orbites de $ au$.
On démontre que les ensembles de valeurs $S(sigma,x)$ et $T( au,x)$ où $sigma$ et $ au$ parcourent les permutations de ${1,ldots,n}$ sont les mêmes. Ce lemme combinatoire obtenu par Spitzer en 1956 fournit des identités en loi remarquables entre les variables aléatoires $max(0,S_1,ldots,S_n)$ et $max(0,S_n)$ lorsque $(S_n)_{n ge 0}$ est une marche aléatoire sur ${f R}$.