P.

Maurer
ENS Rennes

Marche aléatoire simple sur Z, Z2; Z3.

Recasages : 190, 230, 266 .
Référence : J.R Norris, Markov Chains et cours de Thierry Levy, M1 à Sorbonne Université.
C'est un développement joli et original qui se recase bien dans des leçons un peu  galères . Par
contre, il demande de très bien maîtriser la théorie autour des chaînes de Markov, et il est assez
long.
On commence par quelques rappels sur les chaines de Markov et les marches aléatoires. Pour plus
de détails et en particulier les preuves, on pourra consulter le polycopié de Thierry Lévy disponible
à l'adresse :
https://www.lpsm.paris/pageperso/levy/4M011_Poly.pdf

Dans les leçons 190 et 230, ces rappels n'ont pas à figurer dans le plan et sont considérés comme
admis. Il faut bien sûr être capable de donner quelques idées de la construction et des preuves
principales, car il risque d'y avoir quelques questions dessus, le développement étant tout de même
assez difficile.
On se donne E un espace d'états dénombrable, P un noyau de transition sur E et ( ; F ; (Fn)n2N;
(Px)x2E ; (Xn)n2N) une chaîne de Markov homogène, d'espace d'état E et de noyau de transition P .

1 Rappels
Définition 1. Soit x 2 E. On définit le nombre de visites Nx en x et le temps de retour Tx en x par
X
Nx: = 1fXn=xg et Tx := inf fn  1 : Xn = xg:
n2N

Proposition 2. Soit x 2 E. Alors on est dans une et une seule des deux situation suivantes :

 Px(Tx < 1) = 1. Dans ce cas, on dit que l'état x est récurrent, et on a Ex[Nx] = +1.

1
 Px(Tx < 1) < 1. Dans ce cas, on dit que l'état x est transient, et on a Ex[Nx] = .
Px(Tx = 1)

Définition 3. On définit la fonction de Green de la chaîne de Markov par


E  E ! R [ f+1g
G: :
(x; y) 7! Ex[Ny]

Proposition 4. Soit x; y 2 E. Alors

X
 On a G(x; y) = P n(x; y).
n2N

 L'état x est récurrent si et seulement si G(x; x) = +1.

 Si x =
/ y, on a G(x; y) = Px(Ty < 1) G(y; y).

 On a G(x; x) = 1 + Px(Tx < 1) G(x; x).

1
  On a G(x; y)  G(y; y).

Proposition 5. Soit x; y 2 E. Les assertions suivantes sont équivalentes.

1. G(x; y) > 0,

2. Px(Ty < 1) > 0,

3. 9n  0 P n(x; y) > 0,

4. Px(Ny  1)>0.

Définition 6. On dit que x mène à y, et on note x ! y, si G(x; y) > 0. La relation  est réflexive
et transitive sur E  E.

Proposition 7. Soit x; y 2 E: On suppose que x ! y et que x est récurrent. Alors y ! x et y est

récurrent.

Définition 8. On dit que la chaîne de Markov ( ; F ; (Fn)n2N; (Px)x2E ; (Xn)n2N), ou plus géné-
ralement que le noyau de transition P est irréductible, si pour tout x; y 2 E, on a x ! y.

Remarque 9. Si une chaîne de Markov est irréductible, il suffit d'exhiber un état récurrent pour
conclure que tous ses états sont récurrents. On dit d'une chaîne dont tous les états sont récurrents
qu'elle est récurrente.

Définition 10. On définit la marche aléatoire simple sur Z comme la chaîne de Markov d'espace
1 1
d'état Z, de noyau de transition p donné par p(x; x + 1) = , p(x; x ¡ 1) = pour tout x 2 Z.
2 2
On la définit également comme la suite de variables aléatoires Xn = 1 +


+ n, où les variables
1 1
i sont indépendantes et de loi de Rademacher : P(i = 1) = et P(i = ¡1) = :
2 2

1/2 1/2

¡2 ¡1 0 1 2

Définition 11. On définit la marche aléatoire simple sur  Z comme la chaîne de Markov d'espace
2

1/4 si ji ¡ j j = 1
d'état Z2 , de noyau de transition p donné par p(i; j) = .
0 sinon

2
 n n
!
X X
On la définit également comme la suite de variables aléatoires Xn = n; n , où pour
k=1 k=1
n 2 N, le couple (n; n) de variable aléatoires a pour loi
1
P((n; n) = (1; 0)) = P((n; n) = (¡1; 0)) = P((n; n) = (0; 1)) = P((n; n) = (0; ¡1)) = ;
4
les couples (n; n) étant indépendants entre eux.

Définition 12. On définit la marche aléatoire simple sur Z3 comme la chaîne de Markov d'espace
d'état E = Z3 et de noyau de transition P donné par

1/6 si ji ¡ j j = 1
P (i; j) = :
0 sinon

2 Le développement
Théorème 13. La marche aléatoire simple sur Z et sur Z2 est irréductible et récurrente. Sur Z3 ,
elle est irréductible et transiente.

Démonstration.

Etape 1 : la marche aléatoire sur Z.

Vérifions rapidement l'irréductibilité. On se donne x; y 2 Z. Si x = y, on écrit
1
P 2(x; x)  P (x; x + 1) P (x + 1; x) = > 0:
4
Si x =
/ y, on peut supposer par symétrie que x < y. En notant n = y ¡ x, il vient

1
P n(x; y)  P (x; x + 1)


P (y ¡ 1; y) = > 0:
2n
On en déduit (proposition 5) que pour tout x; y 2 E, on a x ! y. Donc la chaîne est irréductible.
Pour montrer qu'elle est récurrente, il suffit donc de montrer que l'état 0 est récurrent. On écrit
X
G(0; 0) = P n(0; 0):
n2N

Observons  déjàque si n est impair, on a P (0; 0)= 0, et

 si n = 2m pour m 2 N, alors P (0;
n 2m

1 2m 2m
0) = 2m . En effet, partant de zéro, il y a possibilités pour revenir à zéro en 2m
2 m m
étapes (on choisit par exemple les m étapes où on se déplace vers la droite, et les m restantes sont
alors nécessairement vers la gauche pour revenir à zéro). Comme chaque étape a une probabilité
1
, on en déduit le résultat.1
2
 
2m
1. Plus formellement, on peut montrer que Card(F) = , où
m

F := f(x1; : : : ; x2m) 2 Z2m : x1 = x2m = 0 et 8i 2 J1; 2m ¡ 1K jxi+1 ¡ xij = 1g:

On pose C = fA  f1; : : : ; 2mg : Card(A) = mg et D = f(1; : : : ; 2m) 2 f¡1; 1g2m : 1 +


+ 2m = 0g. Alors les
applications ' et suivantes sont bien définies, et bijectives :
8
> (
<C ! D 
D ! F
': 1 si i 2 A et : :
>
: A 7! i = ¡1 si i 2 (1; : : : ; 2m) 7! (1 +


+ i)1i2m
/A
 
2m
On en déduit que Card(F) = Card(C), et Card(C) = par définition du coefficient binomial.
m

3
On a ainsi
X X  
1 2m
G(0; 0) = P 2m(0; 0) = :
22m m
m2N m2N

p  m
m
On applique alors la formule de Stirling : m!  2m au terme général de la série
n!+1 e
précédente. Il vient :
  p
1 2m 1 (2m)! 1 22m m2m e¡2m 2  2m 1
= 2m

 p :
22m m 2 (m!)2 n!+1 22m m2m e¡2m 2m n!+1 m

X 1
Le critère de Riemann affirme que la série p diverge, donc le théorème d'équivalence des
m2N
m
séries à termes positifs donne
X
G(0; 0) = P 2m(0; 0) = +1:
m2N

Etape 2 : la marche aléatoire sur Z2.

Pour n  1, on pose n+ = n + n et n¡ = n ¡ n: Alors les variables n+ et n¡ sont indépendantes
et de loi de Rademacher. En effet, on a :

1
 P(n+ = 1) = P(n+ = ¡1) = P(n¡ = 1) = P(n¡ = ¡1) = .
2

 P((n+; n¡) = (1; 1)) = P((n+; n¡) = (1; ¡1)) = P((n+; n¡) = (¡1; 1)) = P((n+; n¡) = (¡1;
1
¡1)) = .
4

On en déduit qu'en posant Xn+ = 1+ +


+ n+ et Xn¡ = 1¡ +


+ n¡, les suites (Xn+)n et (Xn¡)n
sont des marches aléatoires sur Z indépendantes.2
1 1
Par ailleurs, comme n = (n+ + n¡) et n = (n+ ¡ n¡), on a Xn = (0; 0) si et seulement si
2 2
(Xn+; Xn¡) = (0; 0). On en déduit, en utilisant l'indépendance de Xn+ et Xn¡, que

P 2n(0; 0) = P(0;0)(Xn = (0; 0)) = P(0;0)((Xn+; Xn¡) = (0; 0)) = P0(Xn+ = 0)  P0(Xn¡ = 0):

Finalement, comme (Xn+)n et (Xn¡)n sont des marches aléatoires sur Z,

1 1 1
P0(Xn+ = 0)  P0(Xn¡ = 0)  p p = ;
n!+1 n n n

P 1 P
et la série n
diverge, donc P 2n(0; 0) diverge, donc la marche (Xn)n2N est récurrente.

Etape 3 : la marche aléatoire sur Z3.

Partant de zéro, pour revenir en zéro en 2m étapes, il faut faire i pas vers le haut, i pas vers le
bas, j pas vers l'est, j pas vers l'ouest, k pas vers le nord, k pas vers le sud, où i + j + k = m.
p
2
2. Ce joli argument se comprend très bien sur un dessin : à une constante près, les marches (Xn+) et (Xn¡) sont
2
en fait les projections sur les diagonales de la marche (Xn) sur Z . Le dessin est fait à la fin du développement.
2

4
En comptant les manière de faire ces pas, on en déduit que

1 X (2m)!
P 2m(0; 0) =

62m i! 2 j! 2 k! 2
i; j ;k 0
i+ j+k=m

On obtient alors
  X  2
2m 1 m 1
P 2m
(0; 0) =


m 22m i; j ; k 32m
i;j ;k 0
i+ j +k=m
  X  2
2m 1 1 m 1
=
2m
m

m 2 3 i; j ; k 3 i+ j +k
i; j ;k 0
i+ j+k=m

 
m def m!
où := est un coefficient trinomial. Si m = 3` avec k 2 N, on a
i; j ; k i! j!k!
     
m 3` 3`
=  :
i; j ; k i; j ; k `; `; `
On en déduit que
    X  
2m 3` 11 m 1
P (0; 0) 
6`


2m
3`
:
m `; `; ` 2 3 i; j ; k 3i+j +k
i; j;k 0
i+ j+k=m

La formule du trinome (multinome) de Newton donne

X    3
m 1 1 1 1
= + + = 1:
i; j ; k 3i+ j +k 3 3 3
i;j ;k 0
i+ j +k=m

Ainsi, il vient
   
6` 3` 1 1
P (0; 0)
6`




3` `; `; ` 26` 33`
C
 pour un certain C > 0;
n!+1 m3/2

où la dernière ligne s'obtient en utilisant la formule de Stirling.3

 2  4
1 1
Par ailleurs, on a les inégalités P 6`(0; 0)  P 6`¡2(0; 0) et P 6`(0; 0)  P 6`¡4(0; 0), donc
6 6
il existe C 0 > 0 tel que
C
P 2m(0; 0)  :
m3/2
X 1
Comme la série converge, on en déduit que G(0; 0) < 1, donc la chaîne est transiente. 
m2N
m3/2

3. C'est plutôt facile à obtenir (il suffit d'écrire Stirling et de tout simplifier), mais le développement est déjà trop
long pour se permettre d'écrire tout le calcul.

5
3 Marche aléatoire sur Z2 : l'argument géométrique

Xn+

+
X11

(0; 0) +
X19
Xn ¡
X19
X11

¡
X19 X11
Xn¡

p p
2 + 2 ¡
Sur le dessin, ce que l'on a appelé etXn+ Xn¡
est en fait Xn et Xn si on veut garder la
2 2
même définition que dans la démonstration, où on ne s'est pas embêté avec les constantes.
Si vous présentez ce développement, je vous conseille de faire le dessin sur l'annexe de votre plan
et de dire au jury de le regarder quand vous faites la démonstration sur Z2, pour gagner un peu
de temps.
Une autre possibilité est de ne faire que le dessin au tableau et pas la démonstration formelle, mais
il faudra pouvoir répondre précisément à la question  Pourquoi (Xn+) et (Xn¡) sont des marches
aléatoires sur Z indépendantes ? , et il vaut mieux y avoir un peu réfléchi avant, sinon ça peut
mal se passer...
Pour finir, garder en tête que pour d > 3, la marche aléatoire simple sur Zd est toujours transiente.
On peut le montrer de la même manière que pour d = 3 avec la formule du multinôme, mais ça
devient assez moche à écrire.