26
2 Marches aléatoires
Il est tout à fait remarquable que cette formule ne dépende pas de p. L’ensemble P n,k \P
+
n,k est invariant par la réflexion sur la portion du chemin située
avant le retour à 0. On reconnaît là l’astuce de la preuve du théorème 2.5. Il en
découle que l’ensemble des éléments de P n,k \ P
+
n,k qui commencent par un incrément +1 est en bijection avec l’ensemble des éléments de P n,k \P
+
n,k qui commencent par un incrément −1. Or ce dernier est en bijection avec l’ensemble
des éléments de P n,k qui commencent par un incrément −1, lui même en bijection avec P n−1,k+1 . Cela donne card(P n,k )−card(P
+
n,k ) = 2card(P n−1,k+1 ).
Comme card(P n,k ) =
n
(n+k)/2
, on obtient enfin
card(P
+
n,k ) =
n
(n + k)/2
− 2
n − 1
(n + k)/2
=
k
n
n
(n + k)/2
.
En d’autres termes, card(P
+
n,k ) = (k/n)card(P n,k ).
La formule à base de nombres de Catalan du théorème 2.5 s’écrit
2
2n+2
P(S 1 > 0, . . . , S 2n+1 > 0 | S 0 = 0, S 2n+2 = 0)
= card(P
+
2n+1,1 ) =
1
n + 1
2n
n
.
2.2 Marche aléatoire simple symétrique dans l’espace
La marche aléatoire simple symétrique sur Z
d , d 1, est définie par
X n+1 = X n + ε n+1 = X 0 + ε 1 + · · · + ε n+1
où (ε n ) n1 est une suite de variables aléatoires i.i.d., indépendantes de la
position initiale X 0 , et de loi uniforme sur {±e 1 , . . . , ±e d }, où e 1 , . . . , e d est la
base canonique de R
d . La suite (X n ) n0 est une chaîne de Markov d’espace
d’états Z
d et de noyau de transition
P(x, y) =
1
2d
1 |x−y|1=1
où |x| 1 := |x 1 | + · · ·+ |x d |. On parle également de marche aléatoire symétrique
aux plus proches voisins pour la norme |·| 1 . Les incréments (ε n ) n1 sont de loi
uniforme sur la sphère unité pour la norme |·| 1 . En concevant les incréments
ε 1 , . . . , ε n comme issus de n jets d’un dé équilibré à 2d faces, on voit que
Loi(X n − X 0 ) est l’image de la loi multinomiale
1
2d
δ e1 +
1
2d
δ −e1 + · · · +
1
2d
δ −e d +
1
2d
δ e d
∗n
= Mul
n,
1
2d
, . . . ,
1
2d
par l’application
2 Marches aléatoires
Il est tout à fait remarquable que cette formule ne dépende pas de p. L’ensemble P n,k \P
+
n,k est invariant par la réflexion sur la portion du chemin située
avant le retour à 0. On reconnaît là l’astuce de la preuve du théorème 2.5. Il en
découle que l’ensemble des éléments de P n,k \ P
+
n,k qui commencent par un incrément +1 est en bijection avec l’ensemble des éléments de P n,k \P
+
n,k qui commencent par un incrément −1. Or ce dernier est en bijection avec l’ensemble
des éléments de P n,k qui commencent par un incrément −1, lui même en bijection avec P n−1,k+1 . Cela donne card(P n,k )−card(P
+
n,k ) = 2card(P n−1,k+1 ).
Comme card(P n,k ) =
n
(n+k)/2
, on obtient enfin
card(P
+
n,k ) =
n
(n + k)/2
− 2
n − 1
(n + k)/2
=
k
n
n
(n + k)/2
.
En d’autres termes, card(P
+
n,k ) = (k/n)card(P n,k ).
La formule à base de nombres de Catalan du théorème 2.5 s’écrit
2
2n+2
P(S 1 > 0, . . . , S 2n+1 > 0 | S 0 = 0, S 2n+2 = 0)
= card(P
+
2n+1,1 ) =
1
n + 1
2n
n
.
2.2 Marche aléatoire simple symétrique dans l’espace
La marche aléatoire simple symétrique sur Z
d , d 1, est définie par
X n+1 = X n + ε n+1 = X 0 + ε 1 + · · · + ε n+1
où (ε n ) n1 est une suite de variables aléatoires i.i.d., indépendantes de la
position initiale X 0 , et de loi uniforme sur {±e 1 , . . . , ±e d }, où e 1 , . . . , e d est la
base canonique de R
d . La suite (X n ) n0 est une chaîne de Markov d’espace
d’états Z
d et de noyau de transition
P(x, y) =
1
2d
1 |x−y|1=1
où |x| 1 := |x 1 | + · · ·+ |x d |. On parle également de marche aléatoire symétrique
aux plus proches voisins pour la norme |·| 1 . Les incréments (ε n ) n1 sont de loi
uniforme sur la sphère unité pour la norme |·| 1 . En concevant les incréments
ε 1 , . . . , ε n comme issus de n jets d’un dé équilibré à 2d faces, on voit que
Loi(X n − X 0 ) est l’image de la loi multinomiale
1
2d
δ e1 +
1
2d
δ −e1 + · · · +
1
2d
δ −e d +
1
2d
δ e d
∗n
= Mul
n,
1
2d
, . . . ,
1
2d
par l’application