Université Aix-Marseille 2019-2020

Licence 3 de mathématiques – Modélisation.

Chapitre 2 - Les chaı̂nes de Markov.

1 Exemple introductif
Trois pirates décident de partager leur butin en procédant en plusieurs étapes. Chaque étape, les trois
événements suivants se produisent simultanément :

• Le pirate 1 donne 10% de sa fortune au pirate 2, 40% au pirate 3 et en conserve 50%.

• Le pirate 2 donne 50% de sa fortune au pirate 1, 30% au pirate 3 et en conserve 20%.

• Le pirate 3 donne 20% de sa fortune au pirate 1, 10% au pirate 2 et en conserve 70%.

Ce mode de partage peut être simplement modélisé par un système d’équations, que nous allons
maintenant établir. Pour n ≥ 1, on note respectivement xn−1 , yn−1, zn−1 les fortunes des pirates 1, 2 et 3
avant la n-ème étape, et xn , yn , zn après la n-ème étape. La fortune xn provient de trois origines : tout
d’abord, il y a 50% de la fortune xn−1 du pirate 1 avant partage, puis 50% de la fortune yn−1 du pirate
2 avant partage, et enfin 20% de la fortune zn−1 du pirate 3 avant partage. On a donc l’équation :

xn = 0.5xn−1 + 0.5yn−1 + 0.2zn−1 . (1)

Le même raisonnement permet d’obtenir des formules pour les fortunes des pirates 2 et 3:

yn = 0.1xn−1 + 0.2yn−1 + 0.1zn−1 , (2)

zn = 0.4xn−1 + 0.3yn−1 + 0.7zn−1 . (3)

Le système d’équations (1),(2),(3) peut s’écrire matriciellement. Si on note µn le vecteur-ligne µn =
(xn , yn , zn ), on a µn = µn−1 P , où P est la matrice
   
0.5 0.1 0.4 5 1 4
1 
P =  0.5 0.2 0.3  = 5 2 3 
10
0.2 0.1 0.7 2 1 7

La forme matricielle permet de faire certains calculs très rapidement. Par exemple, si on note
µ0 = (x0 , y0 , z0 ) le vecteur-ligne décrivant les trois fortunes initiales (avant le premier partage), on a
µ1 = µ0 P . Mais on a aussi :
µ2 = µ1 P = (µ0 P )P = µ0 P 2 ,
où P 2 est le carré de P , au sens du produit matriciel. En particulier P 2 est bien une matrice carrée de
taille 3 × 3. On a plus généralement le résultat suivant :

Proposition 1 La fortune µn = (xn , yn , zn ) des trois pirates après la n-ème étape est donnée par
l’équation µn = µ0 P n , où P n désigne la puissance n-ème de P au sens du produit matriciel.

Exercice 1.

1. Vérifier que l’équation matricielle µn = µn−1 P est bien équivalente au système formé des trois
équations (1),(2),(3).
 2. On constate facilement que la somme des coefficients de P sur chaque ligne vaut 1. Montrer que
cette propriété intéressante reste vraie si on modifie les modalités de partage pour chaque pirate
(par exemple si le pirate 1 donne 10% au pirate 2, 50% au pirate 3 et en conserve 40%).

3. Vérifier que la fortune totale xn + yn + zn ne dépend pas de n, c’est-à-dire que xn + yn + zn =

x0 + y0 + z0 .

4. Montrer que 1 est valeur propre de P . Quel est le sous-espace propre associé ?

5. Démontrer la Proposition 1.

6. On suppose que la fortune initiale du pirate 1 est de x0 = 100, tandis que celles des pirates 2 et 3
valent y0 = z0 = 0. À l’aide d’un logiciel, calculer P 1000 . En déduire les fortunes x1000 , y1000 , z1000
de chacun des pirates au bout de 1000 étapes. Que se passe-t-il si on change le nombre d’étapes
en n = 2000? n = 3000? Que se passe-t-il si on change les fortunes initiales en x0 = 20, y0 = 70,
z0 = 10? 

Les calculs précédents suggèrent que les fortunes (xn , yn , zn ) semblent
converger vers S(ν1 , ν2 , ν3 ), où
S est la fortune totale S = x0 + y0 + z0 et où ν = (ν1 , ν2 , ν3 ) = 13 , 19 , 93 . Ce résultat de convergence
sera démontré rigoureusement à l’aide du théorème de Perron-Frobenius, qui est l’objet du deuxième
paragraphe.
Exercice 2. Étant donnés (x0 , y0, z0 ) tels que x0 + y0 + z0 = 1, on souhaite illustrer la convergence
de (xn , yn , zn ) vers (ν1 , ν2 , ν3 ). Pour cela, on regarde la quantité dn = |xn − ν1 | + |yn − ν2 | + |zn − ν3 |, qui
est positive et d’autant plus proche de 0 que (xn , yn , zn ) est proche de (ν1 , ν2 , ν3 ). Calculer les valeurs
de dn pour 1 ≤ n ≤ 1000, et tracer le graphe de la fonction n 7→ dn . 
On est censé obtenir le graphe suivant (avec n en abscisses et dn en ordonnées) :

On peut obtenir un équivalent dn ∼ 0.3n . La preuve est assez compliquée, mais la présence de la
constante mystérieuse 0.3 s’explique par le fait que c’est la seconde valeur propre de P .
2 Le théorème de Perron-Frobenius
Définition 1 Une matrice P = (pi,j )1≤i,j≤n ∈ Mn (R) est dite stochastique si :

• Ses coefficients sont positifs : ∀1 ≤ i, j ≤ n, pi,j ≥ 0.

Pn
• La somme des coefficients sur chaque ligne vaut 1 : ∀1 ≤ i ≤ n, j=1 pi,j = 1.

On peut remarquer que la matrice P introduite au premier paragraphe est une matrice stochastique.
Un autre fait intéressant que l’on peut remarquer est que les coefficients pi,j d’une matrice stochastique
sont nécessairement dans [0, 1] (exercice : démontrer ce fait).
La terminologie ”matrice stochastique” vient du fait que ces matrices sont très souvent utilisées pour
modéliser certains processus aléatoires, appelés chaı̂nes de Markov. Ce point de vue probabiliste sera
adopté aux paragraphes suivants.
Un intérêt mathématique des matrices stochastiques est que leur spectre (ou plutôt le spectre de leur
matrice transposée) a un comportement bien particulier. Quelques rappels d’algèbre linéaire sont à ce
moment peut-être utiles :

Définition 2 Soit A ∈ Mn (R) une matrice carrée.

• On dit qu’un nombre complexe λ est une valeur propre de A s’il existe un vecteur non nul X ∈ Rn ,
vu comme une matrice-colonne, tel que AX = λX , autrement dit si le sous-espace Eλ = ker(A −
λI) n’est pas réduit au vecteur nul. Dans ce cas, X, resp. Eλ est appelé vecteur propre, resp.
sous-espace propre, de la matrice A associé à la valeur propre λ.

• Une valeur propre λ est dite simple si le sous-espace propre associé Eλ est de dimension 1.

• L’ensemble des valeurs propres de A est appelé spectre de A.

Théorème 1 (Perron-Frobenius) Soit A une matrice telle que sa transposée AT est stochastique.
Alors :

• Le nombre réel 1 est valeur propre de A. De plus, le sous-espace propre E1 associé à 1 est de
dimension 1, autrement dit la valeur propre 1 est simple.
T
• Il existe un unique vecteur propre
Pn X = (x1 , . . . , xn ) associé à la valeur propre 1 vérifiant xi > 0
pour tout 1 ≤ i ≤ n et tel que i=1 xi = 1.

• Soit λ ∈ C une autre valeur propre de A. Alors son module vérifie |λ| < 1.

• La suite des puissances (An )n≥1 converge lorsque n → ∞ vers la matrice dont toutes les colonnes
sont égales à X.

La démonstration du théorème de Perron-Frobenius, tel qu’énoncé ci-haut, est assez longue mais
tout à fait accessible, et peut se trouver dans de nombreux ouvrages d’algèbre linéaire du premier cycle.
On peut déjà donner une interprétation probabiliste du théorème de Perron-Frobenius. Pour cela,
on introduit les notions suivantes :

Définition
P 3 Une mesure de probabilité sur {1, . . . , n} est un vecteur-ligne ν = (ν1 , . . . , νn ) tel que
νi ≥ 0 et ni=1 νi = 1.

Proposition 2 Soit P une matrice stochastique de taille n × n et ν une mesure de probabilité sur
{1, . . . , n}. Alors Le produit matriciel νP est un vecteur-ligne qui est aussi une mesure de probabilité
sur {1, . . . , n}.
 On a alors :

Théorème 2 Soit P une matrice stochastique. Alors :

• Il existe une unique mesure de probabilité π telle que πP = π, et on a π(i) > 0 pour tout i ∈
{1, . . . , n}. On dit que π est une mesure de probabilité invariante par P .

• La suite des puissances (P m )m≥1 converge vers la matrice dont toutes les lignes sont égales à π.

• Si µ est une mesure de probabilité sur {1, . . . , n}, alors la suite de mesures de probabilité (µP m )m≥1
converge vers π.

Exercice 3. Utiliser un logiciel de calcul scientifique (Python, Scilab,...) pour obtenir les vecteurs
propres et valeurs propres de la matrice suivante :
 
5 5 2
1 
A= 1 2 1 
10
4 3 7

On est censé trouver les valeurs propres 1, 3/10 et 1/10. La transposée de A est la matrice stochastique
P déjà introduite au premier paragraphe. On vérifiera que toutes les conclusions du théorème 1 sont
satisfaites. Remarque : en Python (avec le module numpy), on obtient les éléments propres d’une
matrice avec les commandes suivantes :

import numpy as np
D,V = [Link](A)


Exercice 4. Démontrer la Proposition 2. Démontrer les deux premiers points du Théorème 2 à
l’aide du Théorème 1, et le troisième point du Théorème 2 à l’aide du deuxième point. 
Exercice 5. On dit qu’une mesure de probabilité π est réversible pour une matrice stochastique P
si on a :
∀1 ≤ i, j ≤ n , π(i)P (i, j) = π(j)P (j, i).
Montrer que si π est réversible pour P , alors c’est (l’unique) mesure de probabilité invariante par P .
Plus compliqué : peut-on trouver une matrice stochastique P pour laquelle il n’y a pas de mesure de
probabilité réversible ? 
3 Un exemple de chaı̂ne de Markov
Un entreprise de location de voitures possède quatre agences dans des villes numérotées de 1 à 4. On
suppose que les clients de cette entreprise peuvent louer une voiture dans une certaine agence et la
redéposer le lendemain dans une autre agence. On note par P (i, j) la probabilité pour qu’une voiture
louée à l’agence i se retrouve le lendemain à l’agence j. La valeur de ces probabilités est supposée connue
de l’entreprise : on peut l’estimer en regardant les habitudes des clients durant les mois précédents.
On peut représenter ces probabilités P (i, j) sous la forme d’une matrice P , qui sera appelée matrice
de transition. Dans notre exemple :
 
5 2 2 1
1 
 1 6 2 1 

P =
10  2 2 4 2 
1 3 2 4

Par exemple, la probabilité pour qu’une voiture empruntée à l’agence 4 soit restituée à l’agence 2 le
3
lendemain vaut P (4, 2) = 10 .
Exercice 6. Vérifier que la somme des coefficients sur chaque ligne de P vaut 1. Expliquer pourquoi
cette propriété découle du modèle proposé. 
On s’intéresse à l’histoire vécue par une certaine voiture de location, qui se retrouve jour après jour
restituée dans l’une des quatre agences. On fera l’hypothèse que tous les jours elle est effectivement
louée à un client, pour une durée de 24 heures. Pour tout n ≥ 0, on note par Xn le numéro de l’agence
dans laquelle se trouve à voiture au jour n.
Chaque Xn est ainsi une variable aléatoire à valeurs dans l’espace {1, 2, 3, 4}. La famille (Xn )n≥0
n’est pas indépendante : en effet, la valeur de Xn+1 dépend de celle de Xn . Par exemple, la probabilité
6
que la voiture soit à l’agence 2 au jour n + 1 vaut 10 si elle était à l’agence 2 au jour n, mais seulement
2
10
si elle était à l’agence 1 au jour n.
Bien qu’elles ne soient pas indépendantes, les variables aléatoires (Xn ) possèdent une propriété très
intéressante : il suffit de savoir où se situait la voiture au jour n pour connaı̂tre la probabilité que Xn+1
soit égal à une certaine valeur. En d’autres mots, si l’on connaı̂t Xn , la connaissance de Xn−1 , Xn−2 , . . .
n’apporte aucune information supplémentaire permettant de prédire la valeur de Xn+1 . Cette propriété
qui est appelée propriété de Markov et la famille (Xn )n≥0 est appelée chaı̂ne de Markov.
Intuitivement, le comportement des variables aléatoires (Xn ) est intimement lié à la matrice P . Ce
lien s’exprime rigoureusement à l’aide des probabilités conditionnelles via la formule :
∀1 ≤ i, j ≤ 4 , P(Xn+1 = j|Xn = i) = P (i, j).
Cette équation se lit : la probabilité que Xn+1 soit égal à j sachant que Xn est égal à i vaut P (i, j). On
rappelle que les probabilités conditionnelles sont définies par la formule P(A|B) = P(A∩B)P(B)
.
Pour tout n ≥ 0, on note par µn le vecteur-ligne de longueur 4 défini par
µn = (P(Xn = 1), P(Xn = 2), P(Xn = 3), P(Xn = 4)) .
On remarque que le vecteur µn est une mesure de probabilité sur {1, 2, 3, 4}. On fait l’hypothèse que la
voiture, lors de sa mise en service au jour n = 0, se trouvait à l’agence 1. Cela se traduit par l’équation
µ0 = (1, 0, 0, 0).
Nous allons voir que, une fois connus la matrice P et le vecteur µ0 , il est possible de déduire beaucoup
d’informations sur l’histoire de la voiture. Par exemple, où se situe la voiture au temps n = 1 ? Comme
en n = 0, elle est à l’agence 1, on lit sur la première ligne de la matrice P qu’au jour n = 1, elle est à
5 2
l’agence 1 avec probabilité 10 , à l’agence 2 avec probabilité 10 , etc. On remarque alors que :
µ1 = µ0 P.
 Peut-on prédire la position de la voiture au jour 2 ? En d’autres termes, peut-on calculer µ2 ?
Essayons par exemple de calculer la probabilité µ2 (j) = P(X2 = j). Il est simple de lire cette probabilité
sur la matrice P si on connaı̂t X1 , mais la valeur de X1 est elle-même aléatoire... Pour s’en sortir, on va
donc partitionner l’événement X2 = j en quatre sous-événements disjoints :

P(X2 = j) = P(X2 = j ∩ X1 = 1) + P(X2 = j ∩ X1 = 2) + P(X2 = j ∩ X1 = 3) + P(X2 = j ∩ X1 = 4)

X4
= P(X2 = j ∩ X1 = i).
i=1

On revient ensuite à la définition des probabilités conditionnelles, puis à l’équation (3) pour écrire
4
X 4
X
µ2 (j) = P(X2 = j) = P(X1 = i)P(X2 = j|X1 = i) = µ1 (i)P (i, j).
i=1 i=1

On reconnaı̂t dans la dernière partie de l’équation ci-dessus un produit matriciel, ce qui permet de
donner une forme très compacte au résultat : µ2 = µ1 P . Mais comme on a déjà constaté que µ1 = µ0 P ,
on peut écrire que :
µ2 = (µ0 P )P = µ0 P 2 .
En adaptant le raisonnement ci-dessus, on montre par récurrence sur n ≥ 1 la formule très simple
suivante :

Proposition 3 Pour tout n ≥ 1, on a µn = µ0 P n .

Exercice 7. Utiliser la proposition précédente pour calculer à l’aide d’un ordinateur P(X10 = 4),
P(X2019 = 1), etc. 
Exercice 8. Calculer à l’aide d’un ordinateur la mesure de probabilité invariante pour P , que l’on
notera π, de plusieurs façons différentes :

• On pourra résoudre le système πP = π, ou encore π(P − In ) = 0.

• On pourra résoudre le systèle (P T − In )X = 0, puis considérer la transposée X T .

• On pourra demander directement de calculer un vecteur propre associé à la valeur propre 1 pour
PT.

• On pourra calculer P n , lorsque n est très grand, et regarder les lignes de la matrice obtenue, puis
appliquer le dernier point du Théorème 2.

Attention : pour les trois premières méthodes, le vecteur π ou X obtenu n’est défini qu’à une constante
près. Pour
P obtenir une mesure de probabilité, il faut multiplier ce vecteur par une bonne constante afin
d’avoir 4i=1 π(i) = 1. On est censé obtenir :

1
π= (35, 61, 42, 30) = (0.208333, 0.3630952, 0.25, 0.1785714) 
168

Le dernier exercice de ce paragraphe est un peu plus compliqué :

Exercice 9. Il est très intéressant et très instructif de simuler une trajectoire aléatoire, c’est-à-dire
une suite (Xn )0≤n≤N décrivant une histoire possible pour la voiture. Pour cela, il faut tout d’abord
d’écrire un court programme prenant en argument la valeur de Xn ∈ {1, 2, 3, 4} et ressortant un autre
état Xn+1 ∈ {1, 2, 3, 4} choisi selon les probabilités P (i, j). La trajectoire obtenue est donc un N +1-uplet
qui ressemble à (1, 3, 4, 3, 2, 3, 3, 4, 2, 1, 3, 4, 2, 3, 3, . . .).

• Calculer une longue trajectoire (Xn )0≤n≤N , par exemple pour N = 10000.
 • Le long de cette trajectoire, calculer les proportions de 1, 2, 3 et 4 et comparer ces proportions à
la mesure invariante π.

• Constater que le résultat observé à la question précédente reste vrai si on change le point de départ
X0 , ou même si celui-ci est choisi aléatoirement. 

À titre d’exemple, pour une simulation d’une trajectoire de longueur 10000, les proportions obtenues
ont été (0.2112, 0.3636, 0.2457, 0.1785), ce qui ressemble à la valeur théorique de π. Attention, ces valeurs
expérimentales dépendent de la trajectoire aléatoire considérée, il est donc tout à fait normal de trouver
des valeurs légèrement différentes d’une expérience à l’autre...
4 Marche aléatoire sur un graphe
Donnons-nous un certain graphe, c’est-à-dire ici une collection finie de sommets {1, . . . , m} dont certains
sont reliés par des arêtes :

e1 e2

e3 e4 e5

C’est un graphe non-orienté (il n’y a pas de flèches sur les arêtes) avec m = 5 sommets et 7 arêtes.
Deux sommets sont dits voisins s’il existe une arête les reliant, et on écrit alors ei ∼ ej . Pour tout
i ∈ {1, . . . , m}, on note di le degré du sommet ei , c’est-à-dire son nombre de voisins. On a ici d1 = 3,
d2 = 3, d3 = 2, d4 = 4 et d5 = 2.
Exercice 10. On peut remarquer que la somme des degrées 5i=1 di vaut 14, ce qui est le double
P
du nombre d’arêtes. Pouvez-vous montrer que cette propriété reste vraie pour tous les graphes ? 
La marche aléatoire sur ce graphe est une suite de variables aléatoires (Xn )n≥0 , à valeurs dans
{1, . . . , m}. Il faut imaginer un promeneur sur le graphe, changeant de sommet entre les temps n et
n + 1. Écrire Xn = ei signifie que le promeneur se situe au sommet i au temps n. La seule règle de la
marche aléatoire est la suivante : si le promeneur est en ei au temps n, il choisit le sommet qu’il visitera
au temps n + 1 uniformément parmi les voisins de ei . Comme le nombre de voisins de ei vaut di , la
probabilité de visiter un voisin particulier de ei à l’étape n + 1 vaut d1i . Ce modèle se traduit en termes
mathématiques par l’équation de transition :
1
∀1 ≤ i ≤ m , ∀j t.q. ei ∼ ej , P(Xn+1 = ej |Xn = ei ) = .
di
Comme vu au paragraphe précédent, ces probabilités peuvent être représentées sous la forme d’une
matrice de transition P . Dans notre exemple, la matrice de transition vaut :
 
0 1/3 1/3 1/3 0
 1/3 0 0 1/3 1/3 
 
P =  1/2 0 0 1/2 0  
 1/4 1/4 1/4 0 1/4 
0 1/2 0 1/2 0
On remarque que la somme des coefficients sur chaque ligne de P vaut bien 1, mais tous les coefficients
ne sont pas strictement positifs... On admettra que, dans ce cas particulier, la conclusion du théorème de
Perron-Frobenius reste vraie. En particulier, il existe une unique mesure de probabilité invariante pour
P , c’est-à-dire une unique mesure de probabilité π sur {1, . . . , m} telle que πP = π. Une propriété très
importante des marches aléatoires est que cette unique mesure invariante a une forme bien particulière :
Exercice 11. Montrer que l’unique mesure de probabilité invariante pour la marche aléatoire donnée
1
en exemple vaut π = 14 (3, 3, 2, 4, 2). On pourra ensuite vérifier que le dernier point du théorème de
Perron-Frobenius est bien satisfait, c’est-à-dire que
 
3 3 2 4 2
 3 3 2 4 2 
n 1 
 3 3 2 4 2 

lim P =
n→∞ 14 
 
3 3 2 4 2 
3 3 2 4 2
Pour un graphe général, écrire la matrice de transition P pour la marche aléatoire et vérifier que l’unique
mesure de probabilité invariante vaut π = P1m (d1 , . . . , dm ). 
i=1

Il est possible de retrouver de façon approchée la valeur des π(i) en observant la marche aléatoire
pendant suffisamment longtemps. Pour cela, on utilise le théorème ergodique, qui a été entrevu lors de
l’exercice 9.

Théorème 3 Soit (Xn )0≤n≤N −1 une longue trajectoire de la marche aléatoire sur le graphe. Pour 1 ≤
i ≤ m, on note N(i) := card{0 ≤ n ≤ N − 1 : Xn = i} le nombre de fois où la chaı̂ne de Markov visite
le sommet ei . On a alors :
N(i) di
lim = π(i) = Pm .
N →∞ N
j=1 dj

Autrement dit, le nombre de visites de l’état i devient de plus en plus proportionnel aux voisins de ei .

Par exemple, l’étude d’une trajectoire de longueur N = 10000 permet d’obtenir les valeurs approchées
suivantes :
 
N(1) N(2) N(3) N(4) N(5) 1
, , , , = (3.002, 3.0184, 1.9614, 4.0376, 1.9824) ≈ π.
N N N N N 14
5 Comment devenir milliardaire avec des chaı̂nes de Markov
Dans ce paragraphe, nous allons décrire un algorithme basé sur une chaı̂ne de Markov, et qui a largement
contribué à la fortune de ses deux créateurs. Cet algorithme s’appelle PageRank et a été mis au point
par Serguei Brin et Larry Page pour leur moteur de recherche Google.
L’algorithme PageRank est basé sur une marche aléatoire sur un graphe, mais cette fois-ci le graphe
est orienté, par exemple :

e1 e2

e3 e4 e5

Si on considède un sommet ei , par exemple e1 , il faut distinguer deux types d’arêtes : les arêtes
sortantes (e1 → e2 , e1 → e3 , e1 → e4 ), et les arêtes entrantes (e4 → e1 ). Dans ce nouveau cadre, il
convient également de distinguer le degré sortant d+,i ou entrant d−,i d’un sommet ei . On a sur cet
exemple d+,1 = 3 (nombre d’arêtes sortantes) et d−,1 = 1 (nombre d’arêtes rentrantes). Les graphes
non orientés correspondent au cas particulier où toutes les arêtes sont à la fois entrantes et sortantes,
c’est-à-dire lorsqu’il y a une flèche double sur chaque arête.
La marche aléatoire sur le graphe orienté est simple à expliquer : si on a Xn = i, c’est-à-dire si le
promeneur se trouve au sommet ei au temps n, on choisit le sommet Xn+1 en suivant l’une des flèches
débutant en ei , choisie uniformément. Par exemple, si Xn = 2, alors Xn+1 vaudra soit 4, soit 5, avec
probabilité 1/2, mais on ne peut pas avoir Xn+1 = 1. Comme toujours, on représente les probabilités de
transition P (i, j) = P(Xn+1 = ej |Xn = ei ) sous la forme d’une matrice. Dans notre exemple, on a :
 
0 1/3 1/3 1/3 0

 0 0 0 1/2 1/2 

P =
 0 0 0 1 0 
 1 0 0 0 0 
0 1/2 0 1/2 0
Comme pour l’exemple du paragraphe précédent, les coefficients de P ne sont pas tous strictement
positifs, mais on admet que les conclusions du théorème de Perron-Frobenius restent satisfaites. On a
en particulier l’existence d’une unique mesure de probabilité π sur {1, . . . , m} invariante pour P .
Exercice 12. À l’aide d’un logiciel, trouver une valeur approchée de π pour l’exemple de ce para-
graphe. La valeur exacte est :
1
π = (9, 4, 3, 9, 2). 
27
Une propriété importante de la mesure invariante π, qui peut être constatée sur l’exemple, est la
suivante : la valeur de π(i) semble d’autant plus grande que d−,i est grand. Comment avoir une intuition
de ce phénomène ? Par le théorème ergodique (voir Théorème 3), si l’on considère une longue trajectoire
(Xn )n≥0 , une grande valeur pour π(i) signifie que le sommet ei a été visité de nombreuses fois. Et il
semble naturel qu’un sommet est d’autant plus visité s’il y a beaucoup d’arêtes orientées qui pointent
vers lui...
Ce raisonnement non-rigoureux est à considérer avec beaucoup de prudence : en effet, il permet par
exemple d’expliquer la grande valeur de π(4), mais la grande valeur de π(1) ne vient pas du fait que
de nombreuses arêtes pointent vers e1 (il n’y en a qu’une). Cette valeur s’explique par le fait que si le
sommet e4 est visité au temps n, alors le sommet e1 sera automatiquement visité au temps n + 1.
Nous pouvons dès à présent décrire une première version de l’algorithme PageRank. Pour cela, il
faut imaginer le World Wide Web comme un gigantesque graphe orienté, où :

• Les sommets sont les pages web (aux dernières nouvelles, le nombre de pages web, donc le nombre
de sommets du graphe, serait supérieur à 1015 ),

• il y a une arête orientée entre deux pages e1 → e2 s’il existe un lien hypertexte sur la page e1
permettant d’accéder par un clic à la page e2 .

Le but de l’algorithme PageRank est de donner une ”note” à chacune de ses pages, en grande partie
pour savoir dans quel ordre afficher les résultats dans le moteur de recherche. C’est cette note est
appelée PageRank. Un critère pour évaluer la qualité d’une page web serait de compter le nombre de
liens pointant vers celle-ci. Cela reviendrait à donner la note d−,i à la page ei . Le problème est qu’il
est très difficile de connaı̂tre d−,i : étant donnée une page, on ne sait pas combien de liens pointent vers
celle-ci. En revanche, il est beaucoup plus facile de connaı̂tre d+,i : il suffit de compter le nombre de
liens sur la page ei .
La grande idée derrière l’algorithme PageRank est donc de noter la page ei par π(i), où π est
l’unique mesure de probabilité invariante pour la marche aléatoire sur le graphe orienté que nous venons
de construire. On peut estimer π en utilisant le théorème ergodique.
On peut résumer l’algorithme de la façon suivante :

• On démarre l’algorithme sur n’importe quelle page web X0 = ei .

• On choisit la page suivante X1 en cliquant sur un lien de la page X0 choisi au hasard, uniformément
parmi tous les liens de la page.

• On clique sur un lien aléatoire de X1 pour aller sur une nouvelle page X2 , etc.

• À tout moment, on garde en mémoire le nombre N d’itérations effectuées par l’algorithme, et,
pour chaque page ei , le nombre Ni de fois où celle-ci a été visitée.
Ni
• Si N est suffisamment grand, le quotient N
est une bonne approximation du PageRank π(i) de la
page ei .

Le principe peut donc se résumer en une ligne : un robot visite le web aléatoirement, et une page
est d’autant plus importante qu’elle a été visitée souvent.
Au-delà des critiques que l’on peut faire sur la pertinence du choix fait par Brin et Page pour noter
les pages web, on s’aperçoit vite d’un défaut purement technique dans la méthode présentée ci-dessus :
le robot visitant le web peut se retrouver ”bloqué” sur une page si celle-ci ne contient aucun lien. Un
autre problème est que la matrice de transition de cette marche aléatoire a énormément de coefficients
nuls, et on ne peut pas être sûrs que le théorème de Perron-Frobenius soit toujours applicable...
Une astuce élégante pour contourner ces problèmes consiste à modifier l’algorithme de la façon
suivante :

• Entre l’étape n et l’étape n + 1, on tire un nombre Zn ∈ {0, 1}, avec P(Zn = 0) = 1 − α et

P(Zn = 1) = α. La valeur de α est fixée à l’avance. La valeur choisie par Google serait α = 0.15.

• Si Zn = 0, on clique sur un lien de la page Xn pour accéder à la page Xn+1 , exactement comme
dans la première version de l’algorithme.

• Si Zn = 1, on choisit Xn+1 uniformément parmi toutes les pages web.

 On peut essayer de comprendre cet algorithme modifié en se posant la question suivante : si on a
Xn = ei , quelle est la probabilité Q(i, j) d’avoir Xn+1 = ej ? L’événement (Xn = ei ) ∩ (Xn+1 = ej ) se
partitionne en deux, selon la valeur de Zn , et on peut écrire :

P((Xn = ei ) ∩ (Xn+1 = ej )) = P(Xn = ei , Xn+1 = ej , Zn = 0) + P(Xn = ei , Xn+1 = ej , Zn = 1))

= P(Xn = ei , Xn+1 = ej |Zn = 0)P(Zn = 0)
+P(Xn = ei , Xn+1 = ej |Zn = 1)P(Zn = 1)
1
= P (i, j)(1 − α)P(Xn = ei ) + α.
m
Ici m représente le nombre de sommets du graphe et P la matrice de transition pour la marche aléatoire
sur le graphe.
Exercice 13.

1. Montrer que la suite (Xn )n≥0 est encore une chaı̂ne de Markov, de matrice de transition Q donnée
par
α
Q = (1 − α)P + U,
m
où U est la matrice de taille m × m dont tous les coefficients valent 1.

2. Pourquoi le théorème de Perron-Frobenius peut-il s’appliquer à la matrice Q ?

3. Dans le cas de l’exemple introduit en début de paragraphe, calculer la mesure de probabilité

invariante par Q pour différentes valeurs de α. Peut-on toujours remarquer que cette mesure de
probabilité donne plus d’importance aux sommets qui sont pointés par beaucoup d’arêtes ?