292
9 Google et l’algorithme PageRank
` a x
0 > 0 et
j x
0
j = 1. Soit λ
la limite des λ 0 (δ ni ). Puisque la suite δ i est d´ ecroissante
et que λ 0 (δ) est une fonction croissante, λ
≥ λ 0 (0) = λ 0 . Puisque P + δ ni E → P et
que (P + δ ni E)x(δ ni ) = λ 0 (δ ni )x(δ ni ), la limite des deux membres donne P x
0 = λ
x
0
et, selon la d´ efinition de λ 0 , il faut que λ
≤ λ 0 . Ainsi, λ
= λ 0 , ce qui termine la preuve
de a).
b) Soient λ = λ 0 une autre valeur propre de P et z un vecteur propre non nul : P z = λz,
c’est-` a-dire
(P z) i =
1≤j≤n
p ij z j = λz i .
En prenant la norme des deux membres, on a
|λ| |z i | =
1≤j≤n
p ij z j
≤
1≤j≤n
p ij |z j |
et donc,
P |z| ≥ |λ| |z|
o` u |z| = (|z 1 |, |z 2 |, . . . , |z n |). En changeant la normalisation de |z| au besoin, on s’assure
que |z| appartient au simplexe et donc, |λ| ∈ Λ. Ainsi, |λ| ≤ λ 0 par d´ efinition de λ 0 .
Corollaire 9.8 Si P est une matrice de transition d’une chaˆ ıne de Markov, alors
λ 0 = 1.
Preuve Consid´ erons Q = P
t . Alors,
j q ij = 1 pour tout i. Et puisque P > 0, on a
´ egalement Q > 0. La partie a) du th´ eor` eme de Frobenius ´ etablit l’existence de λ 0 et x 0
(o` u x
0 > 0 et
j x
0
j = 1) tels que Qx
0 = λ 0 x
0 . Puisque x
0 > 0, l’´ el´ ement le plus grand
de x
0 , disons x
0
k , est positif, et
λ 0 x
0
k = (Qx
0 ) k =
1≤j≤n
q kj x
0
j ≤
1≤j≤n
q kj x
0
k = x
0
k ,
d’o` u on d´ eduit que λ 0 ≤ 1. La propri´ et´ e 9.2 a ´ etabli que 1 est une valeur propre de P
(et de Q) ; donc λ 0 ≥ 1. Le r´ esultat suit.
La propri´ et´ e 9.3 d´ ecoule clairement du th´ eor` eme de Frobenius et du corollaire 9.8.
9.5 Exercices
1. a) En utilisant la matrice de transition, calculer les probabilit´ es pour le promeneur
impartial d’ˆ etre aux pages A, B, C, D et E de la toile de la figure 9.2 apr` es son
troisi` eme clic. Comparer ces r´ esultats avec le r´ egime stationnaire π pour cette toile.
9 Google et l’algorithme PageRank
` a x
0 > 0 et
j x
0
j = 1. Soit λ
la limite des λ 0 (δ ni ). Puisque la suite δ i est d´ ecroissante
et que λ 0 (δ) est une fonction croissante, λ
≥ λ 0 (0) = λ 0 . Puisque P + δ ni E → P et
que (P + δ ni E)x(δ ni ) = λ 0 (δ ni )x(δ ni ), la limite des deux membres donne P x
0 = λ
x
0
et, selon la d´ efinition de λ 0 , il faut que λ
≤ λ 0 . Ainsi, λ
= λ 0 , ce qui termine la preuve
de a).
b) Soient λ = λ 0 une autre valeur propre de P et z un vecteur propre non nul : P z = λz,
c’est-` a-dire
(P z) i =
1≤j≤n
p ij z j = λz i .
En prenant la norme des deux membres, on a
|λ| |z i | =
1≤j≤n
p ij z j
≤
1≤j≤n
p ij |z j |
et donc,
P |z| ≥ |λ| |z|
o` u |z| = (|z 1 |, |z 2 |, . . . , |z n |). En changeant la normalisation de |z| au besoin, on s’assure
que |z| appartient au simplexe et donc, |λ| ∈ Λ. Ainsi, |λ| ≤ λ 0 par d´ efinition de λ 0 .
Corollaire 9.8 Si P est une matrice de transition d’une chaˆ ıne de Markov, alors
λ 0 = 1.
Preuve Consid´ erons Q = P
t . Alors,
j q ij = 1 pour tout i. Et puisque P > 0, on a
´ egalement Q > 0. La partie a) du th´ eor` eme de Frobenius ´ etablit l’existence de λ 0 et x 0
(o` u x
0 > 0 et
j x
0
j = 1) tels que Qx
0 = λ 0 x
0 . Puisque x
0 > 0, l’´ el´ ement le plus grand
de x
0 , disons x
0
k , est positif, et
λ 0 x
0
k = (Qx
0 ) k =
1≤j≤n
q kj x
0
j ≤
1≤j≤n
q kj x
0
k = x
0
k ,
d’o` u on d´ eduit que λ 0 ≤ 1. La propri´ et´ e 9.2 a ´ etabli que 1 est une valeur propre de P
(et de Q) ; donc λ 0 ≥ 1. Le r´ esultat suit.
La propri´ et´ e 9.3 d´ ecoule clairement du th´ eor` eme de Frobenius et du corollaire 9.8.
9.5 Exercices
1. a) En utilisant la matrice de transition, calculer les probabilit´ es pour le promeneur
impartial d’ˆ etre aux pages A, B, C, D et E de la toile de la figure 9.2 apr` es son
troisi` eme clic. Comparer ces r´ esultats avec le r´ egime stationnaire π pour cette toile.