Classez les états d'une chaîne

Un visiteur arrive sur la page d’accueil d’un site de presse en ligne. Il lit un article, revient à l’accueil, fait une recherche, lit un autre article… puis, un jour, il s’abonne ou il part. Certaines pages seront revisitées indéfiniment, d’autres finiront par ne plus jamais l’être. Peut-on le savoir sans rien simuler, juste en regardant la structure de la chaîne ?

Oui, et c’est tout l’objet de ce chapitre : classer les états. Ce classement est l’étape obligée avant de chercher un comportement à long terme (chapitre 3) ou des probabilités d’absorption (chapitre 4). Nous suivrons le parcours de ce visiteur tout au long du chapitre.

Le fil rouge : un visiteur sur un site de presse

On modélise la navigation par une chaîne de Markov à six états. Chaque pas de temps est un clic.

Depuis \ Vers	Accueil	Recherche	Article	Abonné	Vidéo	Départ
Accueil	0	0,3	0,4	0	0	0,3
Recherche	0,3	0	0,7	0	0	0
Article	0,3	0	0,2	0,1	0	0,4
Abonné	0	0	0	0,5	0,5	0
Vidéo	0	0	0	0,6	0,4	0
Départ	0	0	0	0	0	1

L’état « Abonné » représente l’espace réservé aux abonnés, d’où l’on regarde des vidéos ; une fois abonné, le visiteur ne revient plus aux pages publiques (c’est une simplification). L’état « Départ » signifie qu’il a quitté le site : on y reste pour toujours. Voici le graphe de transition, sans les probabilités :

Les flèches indiquent les transitions possibles (les boucles de Départ, Abonné et Vidéo sont omises pour alléger). Les cadres anticipent sur le classement que vous allez apprendre à faire.

Qui peut atteindre qui : accessibilité et communication

On dit que l’état $j$ est accessible depuis l’état $i$ s’il existe un nombre de pas $n > 0$ tel que $p_{ij}(n) > 0$. Concrètement, cela revient à dire qu’il existe un chemin de $i$ vers $j$ dans le graphe. Les valeurs des probabilités n’importent pas, seule compte leur positivité.

Deux états $i$ et $j$ communiquent si chacun est accessible depuis l’autre. Cette relation est symétrique et transitive ; elle découpe les états en classes : dans une même classe, tous les états communiquent entre eux. Si vous avez suivi un cours de graphes, vous reconnaissez les composantes fortement connexes du graphe de transition.

Dans notre site :

• Accueil, Recherche et Article communiquent (Accueil → Recherche → Article → Accueil) : ils forment une classe.
• Abonné et Vidéo communiquent : deuxième classe.
• Départ forme une classe à lui seul.

Une classe est fermée si on ne peut pas en sortir : aucun arc ne part d’un de ses états vers un état extérieur. Ici, « Abonné, Vidéo » et « Départ » sont fermées, alors que « Accueil, Recherche, Article » ne l’est pas (on peut s’abonner ou partir). Un état qui forme à lui seul une classe fermée, c’est-à-dire tel que $p_{ii} = 1$, est dit absorbant : c’est le cas de Départ.

Enfin, une chaîne est irréductible si elle ne possède qu’une seule classe : tous les états communiquent, et le graphe est fortement connexe. La chaîne du site n’est pas irréductible ; la météo du chapitre 1, elle, l’est.

À retenir

Classer les états commence toujours par le graphe : on cherche les classes (composantes fortement connexes), puis on regarde lesquelles sont fermées. Une chaîne à une seule classe est irréductible.

La période d’un état

Imaginez un robot de livraison qui fait la navette entre deux entrepôts et change d’entrepôt à chaque pas. Parti de l’entrepôt 1, il ne peut y être revenu qu’après 2, 4, 6… pas, jamais après un nombre impair. Ce rythme imposé s’appelle la période.

La période d’un état $i$ est le plus grand commun diviseur des longueurs des chemins qui partent de $i$ et y reviennent :

$$d_i = \operatorname{pgcd}\lbrace n > 0 : p_{ii}(n) > 0 \rbrace$$

Pour le robot, les retours possibles ont lieu en $\lbrace 2, 4, 6, \dots \rbrace$, donc $d_1 = 2$. Si $d_i = 1$, l’état est apériodique. Deux cas simples à repérer sur le graphe :

• une boucle ($p_{ii} > 0$) donne un retour en 1 pas, donc $d_i = 1$ immédiatement ;
• deux cycles de longueurs premières entre elles (par exemple 2 et 3) passant par $i$ donnent aussi $d_i = 1$.

Dans le site, Article a une boucle ($p = 0{,}2$) : il est apériodique. Et Accueil ? Il n’a pas de boucle, mais on peut y revenir en 2 pas (Accueil → Recherche → Accueil) et en 3 pas (Accueil → Recherche → Article → Accueil). Le pgcd de 2 et 3 vaut 1 : Accueil est apériodique aussi.

Le robot ne peut revenir qu'en un nombre pair de pas (période 2). L'Accueil peut revenir en 2 et en 3 pas, cercles orange, donc à tous les instants à partir de 2 : il est apériodique.

Attention

Les états d’une même classe ont toujours la même période. En revanche, la réciproque est fausse : deux états de même période ne communiquent pas forcément. Abonné et Départ sont tous deux apériodiques, et ils ne communiquent pas du tout.

Récurrent ou transitoire : reviendra-t-on ?

La question la plus importante est la suivante : partant de $i$, est-on sûr d’y revenir un jour ? On note $f_{ii}(n)$ la probabilité que le premier retour en $i$ ait lieu exactement au pas $n$, et

$$f_i = \sum_{n \geq 1} f_{ii}(n)$$

la probabilité de revenir un jour en $i$. L’état $i$ est :

• récurrent si $f_i = 1$ : le retour est certain, et donc l’état sera visité une infinité de fois ;
• transitoire si $f_i < 1$ : il y a une probabilité $1 - f_i > 0$ de ne jamais revenir, et l’état ne sera visité qu’un nombre fini de fois.

Un critère équivalent, souvent plus pratique en théorie, porte sur les probabilités de retour (et non de premier retour) :

$$i \text{ récurrent} \iff \sum_{n \geq 0} p_{ii}(n) = +\infty$$

Cette somme est le nombre moyen de passages en $i$ quand on part de $i$. Pour un état transitoire, elle vaut $1/(1 - f_i)$, un nombre fini.

Exemple

Calculons $f_{\text{Accueil}}$. Depuis l’accueil, le visiteur part avec probabilité 0,3 (pas de retour), va sur Recherche avec probabilité 0,3 ou sur Article avec probabilité 0,4. Notons $h_R$ et $h_T$ les probabilités d’atteindre un jour l’accueil depuis Recherche et depuis Article. En conditionnant sur le clic suivant :

• depuis Article : $h_T = 0{,}3 + 0{,}2\,h_T$ (retour direct, ou on reste sur un article et on recommence), d’où $h_T = 0{,}3 / 0{,}8 = 0{,}375$ ;
• depuis Recherche : $h_R = 0{,}3 + 0{,}7\,h_T = 0{,}3 + 0{,}2625 = 0{,}5625$.

Donc $f_{\text{Accueil}} = 0{,}3 \times 0{,}5625 + 0{,}4 \times 0{,}375 = 0{,}31875 < 1$ : l’accueil est transitoire. En moyenne, un visiteur parti de l’accueil y passe $1 / (1 - 0{,}31875) \approx 1{,}47$ fois en tout.

Le critère de récurrence sur le graphe : pour l'Accueil (transitoire), la somme des p_ii(n) plafonne à 1,47 passages ; pour Abonné (récurrent), elle croît sans limite, d'environ 0,55 passage par clic.

Parmi les états récurrents, on distingue encore selon le temps moyen de retour $\mu_i = \sum_n n\, f_{ii}(n)$ :

• récurrent positif si $\mu_i < +\infty$ ;
• récurrent nul si $\mu_i = +\infty$ : on revient à coup sûr, mais en un temps moyen infini. Cela n’arrive que si l’espace d’états est infini (l’exemple type est la marche aléatoire symétrique sur les entiers relatifs).

Un état ergodique est un état récurrent positif et apériodique. C’est la bonne propriété pour le chapitre suivant.

Exemple

Reprenons une machine qui, chaque heure, tombe en panne avec probabilité $a = 0{,}1$ si elle marche, et est réparée avec probabilité $b = 0{,}4$ si elle est en panne. Partant de l’état « marche » (0), on revient en 1 heure si elle ne tombe pas en panne : $f_{00}(1) = 1 - a$. Pour revenir en $n \geq 2$ heures, il faut tomber en panne, rester en panne $n - 2$ heures, puis être réparé : $f_{00}(n) = a(1-b)^{n-2}b$. La somme de la série géométrique donne $f_0 = (1 - a) + a = 1$ : l’état est récurrent. Le temps moyen de retour vaut $\mu_0 = (a+b)/b = 1{,}25$ heure : récurrent positif.

La loi du premier retour de la machine : presque toujours en une heure, sinon une queue géométrique de raison 0,6. Les barres somment à 1 (état récurrent) et leur moyenne vaut 1,25 heure.

Les théorèmes qui évitent les calculs

Calculer des $f_i$ à la main est long. Heureusement, quelques théorèmes permettent presque toujours de conclure directement sur le graphe.

1. Solidarité : des états qui communiquent ont la même nature (tous récurrents positifs, tous récurrents nuls ou tous transitoires) et la même période. On classe donc des classes, pas des états.
2. Une chaîne à espace d’états fini possède au moins un état récurrent (on ne peut pas quitter définitivement tous les états).
3. Une chaîne finie et irréductible a tous ses états récurrents positifs.
4. Dans une chaîne finie, une classe est récurrente si et seulement si elle est fermée. Une classe ouverte est transitoire : à chaque passage, on a une probabilité positive d’en sortir sans jamais revenir.

Appliquons-les au site : « Accueil, Recherche, Article » est ouverte, donc transitoire ; « Abonné, Vidéo » et « Départ » sont fermées, donc récurrentes positives (chaîne finie). Nous retrouvons le résultat de l’exemple sans le moindre calcul, et nous savons en plus que tout visiteur finira abonné ou parti. Lequel des deux, et avec quelle probabilité ? C’est exactement la question du chapitre 4.

Cinq visiteurs simulés : chacun erre quelques clics dans la classe ouverte, puis la quitte pour toujours. Une fois dans Abonné, Vidéo, on y circule indéfiniment ; une fois dans Départ, on ne bouge plus.

Type de classe (chaîne finie)	Nature	Comportement
Ouverte	transitoire	visitée un nombre fini de fois, puis quittée
Fermée, plusieurs états	récurrente positive	visitée indéfiniment une fois atteinte
Fermée, un seul état ($p_{ii} = 1$)	absorbante	on y reste pour toujours

Piège

Le théorème 4 ne vaut que pour un espace d’états fini. Dans une file d’attente, le nombre de clients peut être aussi grand qu’on veut : la chaîne peut être irréductible (donc sans classe ouverte) et pourtant transitoire, si les clients arrivent plus vite qu’ils ne sont servis. Nous le verrons au chapitre 8.

Classer automatiquement en Python

Pour une grande chaîne, on calcule l’accessibilité par une fermeture transitive du graphe, puis on regroupe les états qui communiquent.

import numpy as np

etats = ["Accueil", "Recherche", "Article", "Abonné", "Vidéo", "Départ"]
P = np.array([[0.0, 0.3, 0.4, 0.0, 0.0, 0.3],
              [0.3, 0.0, 0.7, 0.0, 0.0, 0.0],
              [0.3, 0.0, 0.2, 0.1, 0.0, 0.4],
              [0.0, 0.0, 0.0, 0.5, 0.5, 0.0],
              [0.0, 0.0, 0.0, 0.6, 0.4, 0.0],
              [0.0, 0.0, 0.0, 0.0, 0.0, 1.0]])
n = len(P)
arc = (P > 0).astype(int)

# acces[i, j] = 1 si j est accessible depuis i en au moins un pas
acces = arc.copy()
for _ in range(n):
    acces = ((acces + acces @ arc) > 0).astype(int)
communique = (acces * acces.T) > 0

vus = set()
for i in range(n):
    if i in vus:
        continue
    classe = [j for j in range(n) if communique[i, j]] or [i]
    vus.update(classe)
    dehors = [j for j in range(n) if j not in classe]
    fermee = P[np.ix_(classe, dehors)].sum() == 0
    print([etats[j] for j in classe], "fermée" if fermee else "ouverte")

Le programme affiche les trois classes, la première ouverte et les deux autres fermées. Pour une chaîne finie, cela suffit à dire lesquelles sont récurrentes.

En entretien

« Pour une chaîne finie, je cherche les composantes fortement connexes du graphe de transition : les classes fermées sont récurrentes, les autres transitoires. Si la chaîne n’a qu’une classe et un état apériodique, elle est ergodique et converge vers une loi stationnaire unique. »

En résumé

• $j$ est accessible depuis $i$ s’il existe un chemin de $i$ à $j$ dans le graphe ; $i$ et $j$ communiquent s’ils sont accessibles l’un depuis l’autre.
• Les classes sont les composantes fortement connexes ; une chaîne est irréductible si elle n’en a qu’une. Une classe est fermée si on ne peut pas en sortir ; un état est absorbant si $p_{ii} = 1$.
• Période : $d_i = \operatorname{pgcd}\lbrace n > 0 : p_{ii}(n) > 0 \rbrace$ ; une boucle suffit à rendre un état apériodique.
• Récurrent si le retour est certain ($f_i = 1$), transitoire sinon ; récurrent positif si le temps moyen de retour est fini. Récurrent nul n’arrive qu’en espace infini.
• Les états d’une même classe partagent période et nature. Dans une chaîne finie : classe fermée = récurrente, classe ouverte = transitoire ; finie et irréductible = récurrente positive.
• Ergodique = récurrent positif et apériodique.

Exercices

Exercice · Classer une petite chaîne

facile

Une chaîne à quatre états a pour matrice de transition

$$P = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0{,}5 & 0 & 0{,}5 & 0 \\ 0 & 0 & 0{,}4 & 0{,}6 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

Déterminez ses classes, dites lesquelles sont fermées, donnez la nature et la période de chaque état. La chaîne est-elle irréductible ?

Voir la solution

Les arcs sont $1 \to 2$, $2 \to 1$, $2 \to 3$, $3 \to 3$, $3 \to 4$ et $4 \to 3$.

• $\lbrace 1, 2 \rbrace$ est une classe (1 et 2 communiquent). Elle est ouverte (arc $2 \to 3$) : ses états sont transitoires. Les seuls retours en 1 passent par 2 et prennent 2, 4, 6… pas : la période vaut 2.
• $\lbrace 3, 4 \rbrace$ est une classe fermée (aucun arc vers 1 ou 2) : dans une chaîne finie, ses états sont récurrents positifs. La boucle en 3 donne une période 1, donc 4 est aussi apériodique (même classe). Ces deux états sont ergodiques.

Il y a deux classes : la chaîne n’est pas irréductible.

En code

Python

import numpy as np
from math import gcd
from functools import reduce

P = np.array([[0, 1, 0, 0],
              [0.5, 0, 0.5, 0],
              [0, 0, 0.4, 0.6],
              [0, 0, 1, 0]])
n = len(P)
acces = np.linalg.matrix_power(np.eye(n) + (P > 0), n) > 0   # chemins de longueur <= n
communique = acces & acces.T

for i in range(n):
    classe = np.flatnonzero(communique[i])
    fermee = P[np.ix_(classe, np.setdiff1d(range(n), classe))].sum() == 0
    retours = [k for k in range(1, 30) if np.linalg.matrix_power(P, k)[i, i] > 0]
    print(i + 1, "classe", classe + 1, "fermée" if fermee else "ouverte",
          "période", reduce(gcd, retours))
# 1 classe [1 2] ouverte période 2
# 2 classe [1 2] ouverte période 2
# 3 classe [3 4] fermée période 1
# 4 classe [3 4] fermée période 1

R

P <- matrix(c(0,   1, 0,   0,
              0.5, 0, 0.5, 0,
              0,   0, 0.4, 0.6,
              0,   0, 1,   0), nrow = 4, byrow = TRUE)
n <- nrow(P)
puissance <- function(M, k) Reduce(`%*%`, replicate(k, M, simplify = FALSE))
pgcd <- function(a, b) if (b == 0) a else pgcd(b, a %% b)

acces <- puissance(diag(n) + (P > 0), n) > 0   # chemins de longueur <= n
communique <- acces & t(acces)
for (i in 1:n) {
  classe <- which(communique[i, ])
  fermee <- sum(P[classe, -classe]) == 0
  retours <- Filter(function(k) puissance(P, k)[i, i] > 0, 1:29)
  cat(i, "classe", classe, if (fermee) "fermée" else "ouverte",
      "période", Reduce(pgcd, retours), "\n")
}
## 1 classe 1 2 ouverte période 2
## 2 classe 1 2 ouverte période 2
## 3 classe 3 4 fermée période 1
## 4 classe 3 4 fermée période 1

Exercice · Casser une période

moyen

Un robot surveille les quatre coins d’un entrepôt carré. À chaque pas, il va vers l’un des deux coins voisins, avec probabilité 1/2 chacun.

1. La chaîne est-elle irréductible ? Quelle est la période de chaque coin ?
2. On modifie le robot : à chaque pas, il reste sur place avec probabilité 0,1 et va vers chacun de ses voisins avec probabilité 0,45. Que devient la période ?

Voir la solution

1. Depuis un coin, on atteint tous les autres en longeant les côtés : la chaîne est irréductible. Numérotons les coins de 1 à 4 dans l’ordre du tour. À chaque pas, la parité du numéro change. On ne peut donc revenir au coin de départ qu’en un nombre pair de pas, et un retour en 2 pas est possible (aller-retour) : la période vaut 2 pour tous les coins (ils sont dans la même classe).
2. Chaque coin a maintenant une boucle de probabilité 0,1 : un retour en 1 pas est possible, la période vaut 1. La chaîne devient irréductible, finie et apériodique, donc ergodique. Cette astuce (ajouter un peu de « paresse ») est couramment utilisée pour supprimer une périodicité gênante.

En code

Python

import numpy as np
from math import gcd
from functools import reduce

def periode(P, i, k_max=30):
    """pgcd des longueurs k telles qu'un retour en i en k pas soit possible."""
    retours = [k for k in range(1, k_max) if np.linalg.matrix_power(P, k)[i, i] > 1e-12]
    return reduce(gcd, retours)

def robot(reste):
    """Tour de 4 coins : on reste avec proba `reste`, sinon voisin gauche ou droit."""
    P = np.zeros((4, 4))
    for i in range(4):
        P[i, i] = reste
        P[i, (i + 1) % 4] = P[i, (i - 1) % 4] = (1 - reste) / 2
    return P

print([periode(robot(0.0), i) for i in range(4)])   # [2, 2, 2, 2] robot d'origine
print([periode(robot(0.1), i) for i in range(4)])   # [1, 1, 1, 1] robot « paresseux »

R

pgcd <- function(a, b) if (b == 0) a else pgcd(b, a %% b)
puissance <- function(M, k) Reduce(`%*%`, replicate(k, M, simplify = FALSE))

periode <- function(P, i, k_max = 29) {
  retours <- Filter(function(k) puissance(P, k)[i, i] > 1e-12, 1:k_max)
  Reduce(pgcd, retours)
}
robot <- function(reste) {              # tour de 4 coins
  P <- diag(reste, 4)
  for (i in 1:4) {
    P[i, i %% 4 + 1] <- (1 - reste) / 2           # voisin suivant
    P[i, (i - 2) %% 4 + 1] <- (1 - reste) / 2     # voisin précédent
  }
  P
}
sapply(1:4, function(i) periode(robot(0), i))     # 2 2 2 2 : robot d'origine
sapply(1:4, function(i) periode(robot(0.1), i))   # 1 1 1 1 : robot « paresseux »

Exercice · Probabilité de retour sur un article

difficile

Dans la chaîne du site, calculez la probabilité $f_{\text{Article}}$ qu’un visiteur qui lit un article lise à nouveau un article plus tard. Déduisez-en le nombre moyen de pages « Article » vues par un visiteur qui arrive sur un article (celui-ci compris).

Voir la solution

Notons $g_A$ et $g_R$ les probabilités d’atteindre un jour Article depuis Accueil et depuis Recherche. En conditionnant sur le premier clic :

• $g_A = 0{,}4 + 0{,}3\,g_R$ (on va directement sur un article, ou on passe par Recherche ; partir donne 0) ;
• $g_R = 0{,}7 + 0{,}3\,g_A$.

En substituant, $g_A = 0{,}4 + 0{,}21 + 0{,}09\,g_A$, soit $g_A = 0{,}61 / 0{,}91 \approx 0{,}670$.

Depuis Article, on revient sur un article au pas suivant avec probabilité 0,2 (boucle), ou on passe par l’accueil (0,3) puis on atteint un article avec probabilité $g_A$ ; s’abonner ou partir empêche tout retour. Donc

$$f_{\text{Article}} = 0{,}2 + 0{,}3 \times 0{,}670 \approx 0{,}401.$$

L’état est transitoire, et le nombre moyen de passages vaut $1 / (1 - 0{,}401) \approx 1{,}67$ pages « Article ». Nous retrouverons exactement cette valeur au chapitre 4 avec la matrice fondamentale.

En code

Python

import numpy as np

# Inconnues g_A, g_R : probabilités d'atteindre Article depuis Accueil et Recherche
#   g_A = 0.4 + 0.3 g_R    et    g_R = 0.7 + 0.3 g_A
M = np.array([[1.0, -0.3],
              [-0.3, 1.0]])
g_A, g_R = np.linalg.solve(M, [0.4, 0.7])
f_article = 0.2 + 0.3 * g_A                 # boucle, ou passage par l'accueil
print(round(g_A, 3), round(f_article, 3), round(1 / (1 - f_article), 3))
# 0.67 0.401 1.67

# Vérification par la matrice fondamentale (états transitoires Accueil, Recherche, Article)
Q = np.array([[0.0, 0.3, 0.4], [0.3, 0.0, 0.7], [0.3, 0.0, 0.2]])
print(np.linalg.inv(np.eye(3) - Q)[2, 2])   # 1.6697

R

# g_A = 0.4 + 0.3 g_R  et  g_R = 0.7 + 0.3 g_A
M <- matrix(c(1, -0.3,
              -0.3, 1), nrow = 2, byrow = TRUE)
g <- solve(M, c(0.4, 0.7))
f_article <- 0.2 + 0.3 * g[1]           # boucle, ou passage par l'accueil
round(c(g_A = g[1], f = f_article, visites = 1 / (1 - f_article)), 3)
## g_A 0.670   f 0.401   visites 1.670

# Vérification par la matrice fondamentale
Q <- matrix(c(0, 0.3, 0.4,
              0.3, 0, 0.7,
              0.3, 0, 0.2), nrow = 3, byrow = TRUE)
solve(diag(3) - Q)[3, 3]                # 1.6697