9.5 Exercices
293
Fig. 9.6. Une toile circulaire (exercices 3 et 4)
b) Quelles sont les probabilit´ es d’ˆ etre aux pages A, B, C, D et E de la mˆ eme figure
apr` es le premier clic si le promeneur est `
a la page E au d´ epart ? Apr` es le second
clic ?
2. a) Soit
P =
1 − a
b
a
1 − b
avec a, b ∈ [0, 1].
Montrer que P est une matrice de transition pour une chaˆ ıne de Markov.
b) Calculer les valeurs propres de P en fonction de (a, b). (Une de ces deux valeurs
propres doit ˆ etre 1 de par la propri´ et´ e 9.2.)
c) Quelles valeurs de la paire (a, b) m` enent `
a une seconde valeur propre λ telle
que |λ| = 1 ? Tracer les toiles qui sont repr´ esent´ ees par les matrices de transition
correspondantes.
3. a) Donner la matrice de transition P associ´ ee ` a la toile illustr´ ee ` a la figure 9.6.
b) Montrer que les trois valeurs propres de P sont de valeur absolue ´ egale `
a 1.
c) Trouver (ou mieux, deviner) l’ordre prescrit par l’algorithme PageRank simplifi´ e.
Note : on remarquera que cette toile ne satisfait pas ` a l’hypoth` ese (i) faite pour
obtenir la propri´ et´ e 9.4.
4. Dans le cas de la toile de la figure 9.6, un promeneur commence `
a la page A ` a
l’instant n = 1. Pouvez-vous donner les probabilit´ es P (X n = A), P (X n = B) et
P (X n = C) pour tout n ?
5. a) Intuitivement, quelle est la paire de pages (A, B) ou (C, D) qui se verra attribuer
le rang le plus ´ elev´ e par l’algorithme PageRank simplifi´ e dans la toile de la figure
9.7 ?
b) Trouver l’ordre prescrit par l’algorithme PageRank simplifi´ e.
c) Trouver le r´ egime stationnaire pour le v´ eritable algorithme PageRank, c’est-` adire pour la matrice P
= (1 − β)E + βP . La matrice E est la matrice 4 × 4 dont
293
Fig. 9.6. Une toile circulaire (exercices 3 et 4)
b) Quelles sont les probabilit´ es d’ˆ etre aux pages A, B, C, D et E de la mˆ eme figure
apr` es le premier clic si le promeneur est `
a la page E au d´ epart ? Apr` es le second
clic ?
2. a) Soit
P =
1 − a
b
a
1 − b
avec a, b ∈ [0, 1].
Montrer que P est une matrice de transition pour une chaˆ ıne de Markov.
b) Calculer les valeurs propres de P en fonction de (a, b). (Une de ces deux valeurs
propres doit ˆ etre 1 de par la propri´ et´ e 9.2.)
c) Quelles valeurs de la paire (a, b) m` enent `
a une seconde valeur propre λ telle
que |λ| = 1 ? Tracer les toiles qui sont repr´ esent´ ees par les matrices de transition
correspondantes.
3. a) Donner la matrice de transition P associ´ ee ` a la toile illustr´ ee ` a la figure 9.6.
b) Montrer que les trois valeurs propres de P sont de valeur absolue ´ egale `
a 1.
c) Trouver (ou mieux, deviner) l’ordre prescrit par l’algorithme PageRank simplifi´ e.
Note : on remarquera que cette toile ne satisfait pas ` a l’hypoth` ese (i) faite pour
obtenir la propri´ et´ e 9.4.
4. Dans le cas de la toile de la figure 9.6, un promeneur commence `
a la page A ` a
l’instant n = 1. Pouvez-vous donner les probabilit´ es P (X n = A), P (X n = B) et
P (X n = C) pour tout n ?
5. a) Intuitivement, quelle est la paire de pages (A, B) ou (C, D) qui se verra attribuer
le rang le plus ´ elev´ e par l’algorithme PageRank simplifi´ e dans la toile de la figure
9.7 ?
b) Trouver l’ordre prescrit par l’algorithme PageRank simplifi´ e.
c) Trouver le r´ egime stationnaire pour le v´ eritable algorithme PageRank, c’est-` adire pour la matrice P
= (1 − β)E + βP . La matrice E est la matrice 4 × 4 dont