284
9 Google et l’algorithme PageRank
Propri´ et´ e 9.4 1. Si la matrice de transition P d’une chaˆ ıne de Markov r´ epond aux
trois hypoth` eses ci-dessus, alors il existe un unique vecteur π dont les composantes
π i = P (X n = i), i ∈ T , satisfont ` a
π i ≥ 0,
π i =
j∈T
p ij π j
et
i∈T
π i = 1.
On appellera ce vecteur π le r´ egime stationnaire de la chaˆ ıne de Markov.
2. Quel que soit le point de d´ epart p
0
i = P (X 0 = i), i ∈ T , tel que
i p
0
i = 1, la
distribution des probabilit´ es P (X n = i), i ∈ T , convergera vers ce r´ egime stationnaire π
lorsque n → ∞.
Preuve L’´ enonc´ e 1 ne fait que r´ ep´ eter qu’il n’y a qu’un vecteur propre associ´ e ` a la
valeur propre 1 et dont la somme des composantes est 1. En effet, l’´ equation d´ efinissant
le r´ egime stationnaire est simplement : π = P π, c’est-` a-dire l’´ equation pour un vecteur
propre de la matrice P de valeur propre 1. Selon la propri´ et´ e 9.3, π peut ˆ etre choisi tel
que toutes ses composantes soient positives ou nulles. Puisqu’un vecteur propre n’est
pas nul, la somme des composantes est donc positive. En divisant au besoin le vecteur
propre par la somme de ses composantes, nous pouvons choisir π tel que
i π i = 1.
Pour d´ emontrer l’´ enonc´ e 2, nous ´ ecrirons le vecteur donnant les probabilit´ es qui
caract´ erisent l’´ etat initial du promeneur p
0 = (p
0
1 , p
0
2 , . . . , p
0
N ) dans la base des vecteurs
propres de P . Ordonnons les valeurs propres de P comme suit : 1 = λ 1 > |λ 2 | ≥ |λ 3 | ≥
· · · ≥ |λ N |. Nous savons de par les hypoth` eses (i) et (ii), que la premi` ere in´ egalit´ e
est stricte (c’est-` a-dire que la norme de λ 1 est strictement plus grande que celle de
λ 2 ) et de par l’hypoth` ese (iii), qu’il y a suffisamment de vecteurs propres lin´ eairement
ind´ ependants pour former une base de l’espace de dimension N o` u agit P . (Pour cela, il
faut compter les valeurs propres avec leur multiplicit´ e.) Soit v i un vecteur propre associ´ e
` a la valeur propre λ i . On peut aussi supposer que v 1 est ´ egal au r´ egime stationnaire π.
L’ensemble {v i , i ∈ T } est donc une base, et il est possible d’´ ecrire
p
0 =
N
i=1
a i v i ,
o` u les a j sont les coefficients de p
0 dans cette base.
Montrons maintenant que le coefficient a 1 est toujours 1. Pour cela, nous utiliserons
le vecteur u
t = (1, 1, . . . , 1) que nous avons introduit lors de l’´ etude de la propri´ et´ e 9.2.
Ce vecteur satisfait ` a u
t P = u
t . Si v i est un vecteur propre de P de valeur propre λ i
(c’est-` a-dire P v i = λ i v i ), alors le produit matriciel u
t P v i peut ˆ etre simplifi´ e de deux
fa¸ cons. La premi` ere donne
u
t P v i = (u
t P )v i = u
t v i
et la seconde,
u
t P v i = u
t (P v i ) = λ i u
t v i .
9 Google et l’algorithme PageRank
Propri´ et´ e 9.4 1. Si la matrice de transition P d’une chaˆ ıne de Markov r´ epond aux
trois hypoth` eses ci-dessus, alors il existe un unique vecteur π dont les composantes
π i = P (X n = i), i ∈ T , satisfont ` a
π i ≥ 0,
π i =
j∈T
p ij π j
et
i∈T
π i = 1.
On appellera ce vecteur π le r´ egime stationnaire de la chaˆ ıne de Markov.
2. Quel que soit le point de d´ epart p
0
i = P (X 0 = i), i ∈ T , tel que
i p
0
i = 1, la
distribution des probabilit´ es P (X n = i), i ∈ T , convergera vers ce r´ egime stationnaire π
lorsque n → ∞.
Preuve L’´ enonc´ e 1 ne fait que r´ ep´ eter qu’il n’y a qu’un vecteur propre associ´ e ` a la
valeur propre 1 et dont la somme des composantes est 1. En effet, l’´ equation d´ efinissant
le r´ egime stationnaire est simplement : π = P π, c’est-` a-dire l’´ equation pour un vecteur
propre de la matrice P de valeur propre 1. Selon la propri´ et´ e 9.3, π peut ˆ etre choisi tel
que toutes ses composantes soient positives ou nulles. Puisqu’un vecteur propre n’est
pas nul, la somme des composantes est donc positive. En divisant au besoin le vecteur
propre par la somme de ses composantes, nous pouvons choisir π tel que
i π i = 1.
Pour d´ emontrer l’´ enonc´ e 2, nous ´ ecrirons le vecteur donnant les probabilit´ es qui
caract´ erisent l’´ etat initial du promeneur p
0 = (p
0
1 , p
0
2 , . . . , p
0
N ) dans la base des vecteurs
propres de P . Ordonnons les valeurs propres de P comme suit : 1 = λ 1 > |λ 2 | ≥ |λ 3 | ≥
· · · ≥ |λ N |. Nous savons de par les hypoth` eses (i) et (ii), que la premi` ere in´ egalit´ e
est stricte (c’est-` a-dire que la norme de λ 1 est strictement plus grande que celle de
λ 2 ) et de par l’hypoth` ese (iii), qu’il y a suffisamment de vecteurs propres lin´ eairement
ind´ ependants pour former une base de l’espace de dimension N o` u agit P . (Pour cela, il
faut compter les valeurs propres avec leur multiplicit´ e.) Soit v i un vecteur propre associ´ e
` a la valeur propre λ i . On peut aussi supposer que v 1 est ´ egal au r´ egime stationnaire π.
L’ensemble {v i , i ∈ T } est donc une base, et il est possible d’´ ecrire
p
0 =
N
i=1
a i v i ,
o` u les a j sont les coefficients de p
0 dans cette base.
Montrons maintenant que le coefficient a 1 est toujours 1. Pour cela, nous utiliserons
le vecteur u
t = (1, 1, . . . , 1) que nous avons introduit lors de l’´ etude de la propri´ et´ e 9.2.
Ce vecteur satisfait ` a u
t P = u
t . Si v i est un vecteur propre de P de valeur propre λ i
(c’est-` a-dire P v i = λ i v i ), alors le produit matriciel u
t P v i peut ˆ etre simplifi´ e de deux
fa¸ cons. La premi` ere donne
u
t P v i = (u
t P )v i = u
t v i
et la seconde,
u
t P v i = u
t (P v i ) = λ i u
t v i .