9.2 Toile et chaˆ ınes de Markov
279
p(C) = 0,
p(D) = 0
indiquent qu’apr` es le premier clic, le promeneur ne pourra pas ˆ etre aux pages C ou D,
car aucun lien n’y m` ene de la page C o` u il ´ etait ` a l’´ etape pr´ ec´ edente. Chacun des trois
chemins est indiqu´ e par un trait auquel nous avons ajout´ e le nombre
1
3 pour indiquer
la probabilit´ e de ce chemin. Et, comme il se doit,
p(A) + p(B) + p(C) + p(D) + p(E) = 1,
c’est-` a-dire : le promeneur se trouve sˆ urement en une des cinq pages de la toile.
Le r´ esultat de ce premier clic ´ etait simple et pr´ evisible. Celui du second clic l’est
moins. La figure 9.3 donne les trajectoires possibles du second pas. Si le promeneur ´ etait
en A apr` es le premier clic, il sera assur´ ement en B apr` es le second. En effet, il n’a qu’un
choix possible `
a partir de A. Puisqu’il ´ etait en A avec une probabilit´ e de
1
3 , ce chemin
contribuera pour
1
3 ` a la probabilit´ e de se retrouver en B apr` es le second clic. Mais la
probabilit´ e p(B) n’est pas
1
3 apr` es ce second clic, car un autre chemin, ind´ ependant au
sens des probabilit´ es, y m` ene. C’est celui qui vient de la page E. Si, apr` es le premier
clic, le promeneur se trouve ` a la page E, il pourra choisir, avec ´ egales probabilit´ es, entre
les trois pages B, C et D. Chacun de ces chemins contribuera pour
1
3 ×
1
3 =
1
9 aux
probabilit´ es p(B), p(C) ou p(D) de se trouver aux pages B, C ou D apr` es le second clic.
Quoique les possibilit´ es soient plus nombreuses et les probabilit´ es qui y sont rattach´ ees,
plus compliqu´ ees, le bilan est relativement simple. Apr` es le second clic, le promeneur se
retrouvera aux pages de la toile avec les probabilit´ es suivantes :
p(A) =
1
6
,
p(B) =
4
9
,
p(C) =
5
18
,
p(D) =
1
9
,
p(E) = 0.
`
A nouveau, il est rassurant de v´ erifier que
p(A) + p(B) + p(C) + p(D) + p(E) =
1
6
+
4
9
+
5
18
+
1
9
+ 0 =
3 + 8 + 5 + 2 + 0
18
= 1.
Ouf ! Les ´ etapes sont claires, et peut-ˆ etre pourrions-nous encore calculer les probabilit´ es pour les quelques prochains clics. Mais il est utile de formaliser le comportement
du promeneur impartial. L’outil naturel est la chaˆ ıne de Markov.
Un processus al´ eatoire {X n , n = 0, 1, 2, 3 . . .} est une famille de variables al´ eatoires
param´ etr´ ees par l’entier n. Nous supposerons que chacune de ces variables X n prend
ses valeurs dans un ensemble T fini. Dans l’exemple du promeneur, T est l’ensemble
des pages de la toile T = {A, B, C, D, E}. Pour chaque minute n ∈ {0, 1, 2, 3, . . .}, la
position du promeneur est X n . Toujours dans ce vocabulaire, nous avons d´ etermin´ e
ci-dessus les probabilit´ es que les variables al´ eatoires X 1 et X 2 prennent une des cinq
valeurs possibles ´ etant donn´ e que le promeneur commence en C. Ceci est exprim´ e par
une probabilit´ e conditionnelle P (I|J) qui est la probabilit´ e que l’´ ev´ enement I se produise
si l’´ ev´ enement J s’est produit. Par exemple, P (X 1 = A|X 0 = C) d´ esigne la probabilit´ e
que le promeneur se trouve `
a la page A apr` es le premier clic (X 1 = A) s’il se trouvait
en C au d´ epart (X 0 = C). Ainsi,
279
p(C) = 0,
p(D) = 0
indiquent qu’apr` es le premier clic, le promeneur ne pourra pas ˆ etre aux pages C ou D,
car aucun lien n’y m` ene de la page C o` u il ´ etait ` a l’´ etape pr´ ec´ edente. Chacun des trois
chemins est indiqu´ e par un trait auquel nous avons ajout´ e le nombre
1
3 pour indiquer
la probabilit´ e de ce chemin. Et, comme il se doit,
p(A) + p(B) + p(C) + p(D) + p(E) = 1,
c’est-` a-dire : le promeneur se trouve sˆ urement en une des cinq pages de la toile.
Le r´ esultat de ce premier clic ´ etait simple et pr´ evisible. Celui du second clic l’est
moins. La figure 9.3 donne les trajectoires possibles du second pas. Si le promeneur ´ etait
en A apr` es le premier clic, il sera assur´ ement en B apr` es le second. En effet, il n’a qu’un
choix possible `
a partir de A. Puisqu’il ´ etait en A avec une probabilit´ e de
1
3 , ce chemin
contribuera pour
1
3 ` a la probabilit´ e de se retrouver en B apr` es le second clic. Mais la
probabilit´ e p(B) n’est pas
1
3 apr` es ce second clic, car un autre chemin, ind´ ependant au
sens des probabilit´ es, y m` ene. C’est celui qui vient de la page E. Si, apr` es le premier
clic, le promeneur se trouve ` a la page E, il pourra choisir, avec ´ egales probabilit´ es, entre
les trois pages B, C et D. Chacun de ces chemins contribuera pour
1
3 ×
1
3 =
1
9 aux
probabilit´ es p(B), p(C) ou p(D) de se trouver aux pages B, C ou D apr` es le second clic.
Quoique les possibilit´ es soient plus nombreuses et les probabilit´ es qui y sont rattach´ ees,
plus compliqu´ ees, le bilan est relativement simple. Apr` es le second clic, le promeneur se
retrouvera aux pages de la toile avec les probabilit´ es suivantes :
p(A) =
1
6
,
p(B) =
4
9
,
p(C) =
5
18
,
p(D) =
1
9
,
p(E) = 0.
`
A nouveau, il est rassurant de v´ erifier que
p(A) + p(B) + p(C) + p(D) + p(E) =
1
6
+
4
9
+
5
18
+
1
9
+ 0 =
3 + 8 + 5 + 2 + 0
18
= 1.
Ouf ! Les ´ etapes sont claires, et peut-ˆ etre pourrions-nous encore calculer les probabilit´ es pour les quelques prochains clics. Mais il est utile de formaliser le comportement
du promeneur impartial. L’outil naturel est la chaˆ ıne de Markov.
Un processus al´ eatoire {X n , n = 0, 1, 2, 3 . . .} est une famille de variables al´ eatoires
param´ etr´ ees par l’entier n. Nous supposerons que chacune de ces variables X n prend
ses valeurs dans un ensemble T fini. Dans l’exemple du promeneur, T est l’ensemble
des pages de la toile T = {A, B, C, D, E}. Pour chaque minute n ∈ {0, 1, 2, 3, . . .}, la
position du promeneur est X n . Toujours dans ce vocabulaire, nous avons d´ etermin´ e
ci-dessus les probabilit´ es que les variables al´ eatoires X 1 et X 2 prennent une des cinq
valeurs possibles ´ etant donn´ e que le promeneur commence en C. Ceci est exprim´ e par
une probabilit´ e conditionnelle P (I|J) qui est la probabilit´ e que l’´ ev´ enement I se produise
si l’´ ev´ enement J s’est produit. Par exemple, P (X 1 = A|X 0 = C) d´ esigne la probabilit´ e
que le promeneur se trouve `
a la page A apr` es le premier clic (X 1 = A) s’il se trouvait
en C au d´ epart (X 0 = C). Ainsi,