9.2 Toile et chaˆ ınes de Markov
281
Les chaˆ ınes de Markov ont le grand avantage que leur ´ etat `
a tout instant n peut ˆ etre
d´ etermin´ e ` a l’aide de l’´ etat initial (p(C) = 1 dans l’exemple de la figure 9.3) et d’une
matrice de transition donn´ ee par
p(X n = i | X n−1 = j) = p ij .
(9.1)
Une matrice P repr´ esente une matrice de transition d’une chaˆ ıne de Markov si et seulement si
p ij ∈ [0, 1] pour tout i, j ∈ T
et
i∈T
p ij = 1 pour tout j ∈ T .
(9.2)
Pour le promeneur sur la toile, les ´ el´ ements p ij , i, j ∈ T , de la matrice P repr´ esentent
donc la probabilit´ e de se retrouver ` a la page i si, au clic pr´ ec´ edent, il ´ etait `
a la page
j ∈ T . Mais la r` egle impartiale que nous nous sommes donn´ ee veut qu’il choisisse avec
´ egales probabilit´ es entre tous les liens que cette page lui donne. Si la page j offre le
choix entre m liens, alors la colonne j de la matrice P contiendra
1
m aux lignes qui
repr´ esentent les pages vers lesquelles j pointent et 0 ailleurs. Il est facile d’´ ecrire la
matrice de transition pour la (minuscule) toile de la figure 9.2. La voici :
P =
A B C D E
⎛
⎜
⎜
⎜
⎜
⎝
0
1
2
1
3
1 0
1 0
1
3
0
1
3
0
1
2
0 0
1
3
0 0 0 0
1
3
0 0
1
3
0 0
⎞
⎟
⎟
⎟
⎟
⎠
A
B
C
D
E
(9.3)
Les ´ el´ ements non nuls d’une colonne indiquent les destinations possibles : de la page
E, le promeneur ne peut aller qu’aux pages B, C et D. Les ´ el´ ements non nuls d’une
ligne donn´ ee indiquent les origines possibles. Par exemple, le fait qu’un seul ´ el´ ement de
la ligne D soit non nul indique qu’on ne peut atteindre cette page qu’en ayant visit´ e la
page E auparavant.
Que veut dire la seconde contrainte de (9.2) ? Pour le comprendre, r´ e´ ecrivons-la ` a
l’aide de la d´ efinition (9.1) :
i∈T
p ij =
i∈T
p(X n = i | X n−1 = j) = 1,
qui se lit comme suit : si ` a l’instant n−1, le syst` eme est dans l’´ etat j, alors la probabilit´ e
qu’il se trouve `
a l’instant n dans un des ´ etats possibles du syst` eme est 1. Ou encore,
dans l’exemple pr´ ec´ edent, le promeneur qui se trouve sur une des pages de la toile ` a
l’instant n − 1 tombera certainement sur une autre page de T apr` es avoir cliqu´ e sur un
lien. C’est donc une ´ equation assez ´ evidente.
Cette formalisation a de grands avantages. Nous pouvons par simples multiplications matricielles reproduire l’exercice laborieux des deux premiers clics. Comme
pr´ ec´ edemment, nous supposerons le promeneur ` a la page C au d´ epart. Ainsi
281
Les chaˆ ınes de Markov ont le grand avantage que leur ´ etat `
a tout instant n peut ˆ etre
d´ etermin´ e ` a l’aide de l’´ etat initial (p(C) = 1 dans l’exemple de la figure 9.3) et d’une
matrice de transition donn´ ee par
p(X n = i | X n−1 = j) = p ij .
(9.1)
Une matrice P repr´ esente une matrice de transition d’une chaˆ ıne de Markov si et seulement si
p ij ∈ [0, 1] pour tout i, j ∈ T
et
i∈T
p ij = 1 pour tout j ∈ T .
(9.2)
Pour le promeneur sur la toile, les ´ el´ ements p ij , i, j ∈ T , de la matrice P repr´ esentent
donc la probabilit´ e de se retrouver ` a la page i si, au clic pr´ ec´ edent, il ´ etait `
a la page
j ∈ T . Mais la r` egle impartiale que nous nous sommes donn´ ee veut qu’il choisisse avec
´ egales probabilit´ es entre tous les liens que cette page lui donne. Si la page j offre le
choix entre m liens, alors la colonne j de la matrice P contiendra
1
m aux lignes qui
repr´ esentent les pages vers lesquelles j pointent et 0 ailleurs. Il est facile d’´ ecrire la
matrice de transition pour la (minuscule) toile de la figure 9.2. La voici :
P =
A B C D E
⎛
⎜
⎜
⎜
⎜
⎝
0
1
2
1
3
1 0
1 0
1
3
0
1
3
0
1
2
0 0
1
3
0 0 0 0
1
3
0 0
1
3
0 0
⎞
⎟
⎟
⎟
⎟
⎠
A
B
C
D
E
(9.3)
Les ´ el´ ements non nuls d’une colonne indiquent les destinations possibles : de la page
E, le promeneur ne peut aller qu’aux pages B, C et D. Les ´ el´ ements non nuls d’une
ligne donn´ ee indiquent les origines possibles. Par exemple, le fait qu’un seul ´ el´ ement de
la ligne D soit non nul indique qu’on ne peut atteindre cette page qu’en ayant visit´ e la
page E auparavant.
Que veut dire la seconde contrainte de (9.2) ? Pour le comprendre, r´ e´ ecrivons-la ` a
l’aide de la d´ efinition (9.1) :
i∈T
p ij =
i∈T
p(X n = i | X n−1 = j) = 1,
qui se lit comme suit : si ` a l’instant n−1, le syst` eme est dans l’´ etat j, alors la probabilit´ e
qu’il se trouve `
a l’instant n dans un des ´ etats possibles du syst` eme est 1. Ou encore,
dans l’exemple pr´ ec´ edent, le promeneur qui se trouve sur une des pages de la toile ` a
l’instant n − 1 tombera certainement sur une autre page de T apr` es avoir cliqu´ e sur un
lien. C’est donc une ´ equation assez ´ evidente.
Cette formalisation a de grands avantages. Nous pouvons par simples multiplications matricielles reproduire l’exercice laborieux des deux premiers clics. Comme
pr´ ec´ edemment, nous supposerons le promeneur ` a la page C au d´ epart. Ainsi