4.5 Arbres aléatoires
65
un exemple d’association. On peut établir par récurrence qu’on a toujours
s 2n+1 = −1 et min(s 1 , . . . , s 2n ) 0. Grâce à la convention de numérotation,
l’arbre se reconstruit aisément à partir du morceau de trajectoire (s i ) 1i2n .
On vérifie que cette construction définit une bijection entre l’ensemble T n et
1
2
4
5
3
n
Sn
1
2
3
4
5
-1
0
1
2
Fig. 4.2. Élément de T2 et trajectoire de la marche aléatoire associé.
l’ensemble P n des trajectoires de longueur 2n de la marche aléatoire simple
sur Z, valant 0 au temps 0 et au temps 2n, et restant positives ou nulles entre
ces deux temps. Il s’agit d’un cas particulier de la bijection de la preuve du
théorème 3.17. Comme cette bijection est explicite et calculable, la simulation
de la loi uniforme sur T n se déduit de la simulation de la loi uniforme sur P n ,
pour laquelle on peut procéder comme suit.
Théorème 4.7 (Algorithme de Arnold-Sleep). Soit s = (s i ) 0i2n le chemin
aléatoire à valeurs dans P n dont la loi est donnée par s 0 = s 2n = 0 et pour
tout 0 k 2n − 1,
P(s k+1 − s k = −1 | s 0 , . . . , s k ) = 1 − P(s k+1 − s k = 1 | s 0 , . . . , s k )
=
s k (2n + k + s k + 2)
2(2n − k)(s k + 1)
.
Alors s suit la loi uniforme sur P n , et donc l’arbre binaire associé suit la loi
uniforme sur T n .
Démonstration. Construisons progressivement un chemin (s i ) 1i2n de loi
uniforme sur P n . Supposons que s 0 , . . . , s 2n−k sont déjà construits. Le nombre
de manières de prolonger ce début de trajectoire en un élément de P n ne dépend que de k et r = s 2n−k , et nous le notons N (r, k). Le nombre de manières
de le faire en commençant par un incrément +1 vaut N (r + 1, k − 1), tandis
que le nombre de manières de le faire en commençant par un incrément −1
vaut N (r − 1, k − 1). On a donc N (r, k) = N (r + 1, k − 1) + N (r − 1, k − 1), et
65
un exemple d’association. On peut établir par récurrence qu’on a toujours
s 2n+1 = −1 et min(s 1 , . . . , s 2n ) 0. Grâce à la convention de numérotation,
l’arbre se reconstruit aisément à partir du morceau de trajectoire (s i ) 1i2n .
On vérifie que cette construction définit une bijection entre l’ensemble T n et
1
2
4
5
3
n
Sn
1
2
3
4
5
-1
0
1
2
Fig. 4.2. Élément de T2 et trajectoire de la marche aléatoire associé.
l’ensemble P n des trajectoires de longueur 2n de la marche aléatoire simple
sur Z, valant 0 au temps 0 et au temps 2n, et restant positives ou nulles entre
ces deux temps. Il s’agit d’un cas particulier de la bijection de la preuve du
théorème 3.17. Comme cette bijection est explicite et calculable, la simulation
de la loi uniforme sur T n se déduit de la simulation de la loi uniforme sur P n ,
pour laquelle on peut procéder comme suit.
Théorème 4.7 (Algorithme de Arnold-Sleep). Soit s = (s i ) 0i2n le chemin
aléatoire à valeurs dans P n dont la loi est donnée par s 0 = s 2n = 0 et pour
tout 0 k 2n − 1,
P(s k+1 − s k = −1 | s 0 , . . . , s k ) = 1 − P(s k+1 − s k = 1 | s 0 , . . . , s k )
=
s k (2n + k + s k + 2)
2(2n − k)(s k + 1)
.
Alors s suit la loi uniforme sur P n , et donc l’arbre binaire associé suit la loi
uniforme sur T n .
Démonstration. Construisons progressivement un chemin (s i ) 1i2n de loi
uniforme sur P n . Supposons que s 0 , . . . , s 2n−k sont déjà construits. Le nombre
de manières de prolonger ce début de trajectoire en un élément de P n ne dépend que de k et r = s 2n−k , et nous le notons N (r, k). Le nombre de manières
de le faire en commençant par un incrément +1 vaut N (r + 1, k − 1), tandis
que le nombre de manières de le faire en commençant par un incrément −1
vaut N (r − 1, k − 1). On a donc N (r, k) = N (r + 1, k − 1) + N (r − 1, k − 1), et