280
9 Google et l’algorithme PageRank
p(X 1 = A|X 0 = C) =
1
3
, p(X 1 = B|X 0 = C) =
1
3
, p(X 1 = C|X 0 = C) = 0,
p(X 1 = D|X 0 = C) = 0, p(X 1 = E|X 0 = C) =
1
3
,
et
p(X 2 = A|X 0 = C) =
1
6
, p(X 2 = B|X 0 = C) =
4
9
, p(X 2 = C|X 0 = C) =
5
18
,
p(X 2 = D|X 0 = C) =
1
9
, p(X 2 = E|X 0 = C) = 0.
La marche al´ eatoire du promeneur impartial poss` ede la propri´ et´ e-cl´ e d´ efinissant les
chaˆ ınes de Markov. Voici tout d’abord la d´ efinition de ces chaˆ ınes.
D´ efinition 9.1 Soit {X n , n = 0, 1, 2, 3, . . .} un processus al´ eatoire prenant ses valeurs
dans T = {A, B, C, . . .}. On dit que {X n } est une chaˆ ıne de Markov si la probabilit´ e
p(X n = i), i ∈ T , ne d´ epend que de l’´ etat X n−1 ` a l’instant pr´ ec´ edent et non des
valeurs ant´ erieures X n−2 , X n−3 , . . . Nous noterons par N < ∞ le nombre d’´ el´ ements
de l’ensemble T .
Dans l’exemple du promeneur impartial, les variables al´ eatoires sont les positions X n
apr` es le clic n. En refaisant mentalement les ´ etapes du calcul donnant les probabilit´ es
des diff´ erentes valeurs de X 1 et X 2 , nous constatons que, pour obtenir les probabilit´ es
apr` es le premier clic, nous n’avons utilis´ e que le fait que le promeneur commen¸ cait ` a la
page C alors que, pour obtenir celles apr` es le second clic, seules les probabilit´ es p(X 1 =
A), p(X 1 = B), . . . , p(X 1 = E) sont entr´ ees en jeu. Cette possibilit´ e de d´ eterminer la
probabilit´ e de chaque ´ etat apr` es le clic n ` a partir des probabilit´ es apr` es le clic n −
1 est la propri´ et´ e de Markov. Mais tous les processus al´ eatoires ne sont-ils pas des
chaˆ ınes de Markov ? Certainement pas. Nous pouvons changer l´ eg` erement les r` egles de
la marche al´ eatoire du promeneur pour qu’elle perde la propri´ et´ e de Markov. Supposons,
par exemple, que nous voulions empˆ echer le promeneur de retourner imm´ ediatement aux
pages d’o` u il vient. Par exemple, apr` es le premier clic, le promeneur se trouve aux pages
A, B et E avec ´ egales probabilit´ es. Il ne peut pas revenir `
a la page C ` a partir de la page
A, mais il peut le faire `
a partir des pages B et E. Nous pouvons interdire au promeneur
de rebrousser chemin ` a partir de ces pages B et E. Ainsi, pour cette nouvelle marche,
le promeneur n’aurait qu’un choix `
a partir de B (aller ` a A), et il en aurait deux ` a partir
de E (aller ` a une des pages B et D). Cette marche for¸ cant le promeneur ` a ´ eviter, si
possible, les retours imm´ ediats viole la propri´ et´ e de Markov : elle a une m´ emoire. En
effet, pour d´ eterminer les probabilit´ es P (X 2 ), nous devons connaˆ ıtre non seulement les
probabilit´ es apr` es le clic 1, mais aussi la page (ou les pages) o` u le promeneur impartial
se trouvait avant le premier clic. Les r` egles que nous avons utilis´ ees jusqu’` a pr´ esent sont
donc particuli` eres au sens math´ ematique : une chaˆ ıne de Markov n’a pas de m´ emoire.
Elle n’utilise que la situation pr´ esente du promeneur pour d´ eterminer celle ` a l’instant
suivant.
9 Google et l’algorithme PageRank
p(X 1 = A|X 0 = C) =
1
3
, p(X 1 = B|X 0 = C) =
1
3
, p(X 1 = C|X 0 = C) = 0,
p(X 1 = D|X 0 = C) = 0, p(X 1 = E|X 0 = C) =
1
3
,
et
p(X 2 = A|X 0 = C) =
1
6
, p(X 2 = B|X 0 = C) =
4
9
, p(X 2 = C|X 0 = C) =
5
18
,
p(X 2 = D|X 0 = C) =
1
9
, p(X 2 = E|X 0 = C) = 0.
La marche al´ eatoire du promeneur impartial poss` ede la propri´ et´ e-cl´ e d´ efinissant les
chaˆ ınes de Markov. Voici tout d’abord la d´ efinition de ces chaˆ ınes.
D´ efinition 9.1 Soit {X n , n = 0, 1, 2, 3, . . .} un processus al´ eatoire prenant ses valeurs
dans T = {A, B, C, . . .}. On dit que {X n } est une chaˆ ıne de Markov si la probabilit´ e
p(X n = i), i ∈ T , ne d´ epend que de l’´ etat X n−1 ` a l’instant pr´ ec´ edent et non des
valeurs ant´ erieures X n−2 , X n−3 , . . . Nous noterons par N < ∞ le nombre d’´ el´ ements
de l’ensemble T .
Dans l’exemple du promeneur impartial, les variables al´ eatoires sont les positions X n
apr` es le clic n. En refaisant mentalement les ´ etapes du calcul donnant les probabilit´ es
des diff´ erentes valeurs de X 1 et X 2 , nous constatons que, pour obtenir les probabilit´ es
apr` es le premier clic, nous n’avons utilis´ e que le fait que le promeneur commen¸ cait ` a la
page C alors que, pour obtenir celles apr` es le second clic, seules les probabilit´ es p(X 1 =
A), p(X 1 = B), . . . , p(X 1 = E) sont entr´ ees en jeu. Cette possibilit´ e de d´ eterminer la
probabilit´ e de chaque ´ etat apr` es le clic n ` a partir des probabilit´ es apr` es le clic n −
1 est la propri´ et´ e de Markov. Mais tous les processus al´ eatoires ne sont-ils pas des
chaˆ ınes de Markov ? Certainement pas. Nous pouvons changer l´ eg` erement les r` egles de
la marche al´ eatoire du promeneur pour qu’elle perde la propri´ et´ e de Markov. Supposons,
par exemple, que nous voulions empˆ echer le promeneur de retourner imm´ ediatement aux
pages d’o` u il vient. Par exemple, apr` es le premier clic, le promeneur se trouve aux pages
A, B et E avec ´ egales probabilit´ es. Il ne peut pas revenir `
a la page C ` a partir de la page
A, mais il peut le faire `
a partir des pages B et E. Nous pouvons interdire au promeneur
de rebrousser chemin ` a partir de ces pages B et E. Ainsi, pour cette nouvelle marche,
le promeneur n’aurait qu’un choix `
a partir de B (aller ` a A), et il en aurait deux ` a partir
de E (aller ` a une des pages B et D). Cette marche for¸ cant le promeneur ` a ´ eviter, si
possible, les retours imm´ ediats viole la propri´ et´ e de Markov : elle a une m´ emoire. En
effet, pour d´ eterminer les probabilit´ es P (X 2 ), nous devons connaˆ ıtre non seulement les
probabilit´ es apr` es le clic 1, mais aussi la page (ou les pages) o` u le promeneur impartial
se trouvait avant le premier clic. Les r` egles que nous avons utilis´ ees jusqu’` a pr´ esent sont
donc particuli` eres au sens math´ ematique : une chaˆ ıne de Markov n’a pas de m´ emoire.
Elle n’utilise que la situation pr´ esente du promeneur pour d´ eterminer celle ` a l’instant
suivant.