Découvrez les chaînes de Markov

À Rennes, on dit volontiers qu’il fait beau plusieurs fois par jour. Plus sérieusement, le temps qu’il fera demain n’est pas prévisible avec certitude, mais il n’est pas non plus tiré au hasard sans règle : après une journée de pluie, une autre journée de pluie est plus probable qu’après une journée de grand soleil. Comment décrire un système qui évolue au hasard, mais avec une mémoire de son état présent ?

C’est exactement ce que fait une chaîne de Markov. Dans ce chapitre, vous allez poser le vocabulaire, écrire votre première matrice de transition et calculer la probabilité qu’il pleuve dans trois jours. Nous suivrons la météo rennaise tout au long du chapitre, et nous la retrouverons au chapitre 3.

Un processus stochastique, c’est une suite de variables aléatoires

Observons le ciel chaque matin à 8 h. Le jour $n$, on note $X_n$ la météo observée, qui prend une valeur parmi trois : soleil, nuages ou pluie. Avant d’observer, $X_n$ est une variable aléatoire. La suite $(X_0, X_1, X_2, \dots)$ est ce qu’on appelle un processus stochastique (stochastic process).

Plus précisément, un processus stochastique est une famille de variables aléatoires $(X_t)_{t \in T}$, où :

• $T$ est l’ensemble des temps. Si $T = \mathbb{N}$ (on observe à des instants $0, 1, 2, \dots$), on parle de processus à temps discret, ou de chaîne. Si $T = \mathbb{R}_+$ (on observe à tout instant), le processus est à temps continu ; ce sera l’objet de la partie 2.
• $E$ est l’espace d’états, l’ensemble des valeurs que peut prendre chaque $X_t$. Dans tout ce cours, $E$ est discret : fini (trois météos) ou infini dénombrable (le nombre de clients dans une file d’attente, qui peut valoir $0, 1, 2, \dots$).

Pour simplifier l’écriture, on numérote les états. Ici : 0 pour soleil, 1 pour nuages, 2 pour pluie. Une trajectoire est une suite de valeurs effectivement prises, par exemple « soleil, soleil, nuages, pluie ».

À retenir

Un processus stochastique est une suite de variables aléatoires indexée par le temps. On le décrit par son ensemble des temps (discret ou continu) et son espace d’états (ici toujours discret).

La propriété de Markov : seul le présent compte

Pour prévoir la météo de demain, faut-il connaître celle de toute la semaine passée ? Dans un modèle de Markov, non : le futur ne dépend du passé qu’à travers l’état présent. Mathématiquement, pour tous états $i_0, \dots, i_n$ :

$$P(X_n = i_n \mid X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_n = i_n \mid X_{n-1} = i_{n-1})$$

La barre verticale se lit « sachant ». À gauche, on conditionne par tout l’historique ; à droite, seulement par le dernier état. La propriété de Markov dit que ces deux probabilités sont égales : une fois l’état présent connu, l’historique n’apporte plus aucune information sur le futur.

On ajoute presque toujours une deuxième hypothèse, l’homogénéité : la probabilité de passer de l’état $i$ à l’état $j$ ne dépend pas de l’instant $n$. On la note simplement

$$p_{ij} = P(X_{n+1} = j \mid X_n = i) \quad \text{pour tout } n.$$

Pour notre météo, cela revient à dire que la règle « après un jour de pluie, il pleut encore avec probabilité 0,5 » vaut en janvier comme en juillet. C’est évidemment une simplification (les saisons existent, même en Bretagne), mais elle rend le modèle calculable. Tout ce cours travaille avec des chaînes homogènes.

Attention

La propriété de Markov n’est pas une propriété du monde, c’est une propriété de votre choix d’états. Si la météo de demain dépend en réalité des deux derniers jours, la suite des météos quotidiennes n’est pas markovienne. Mais la suite des couples (météo d’hier, météo d’aujourd’hui) peut l’être : on enrichit l’état pour qu’il résume tout ce qui compte. L’exercice 3 met en œuvre cette astuce.

La matrice de transition et son graphe

Supposons qu’une longue série d’observations donne les fréquences suivantes (elles sont inventées pour l’exemple) :

Aujourd’hui \ Demain	Soleil	Nuages	Pluie
Soleil	0,6	0,3	0,1
Nuages	0,3	0,4	0,3
Pluie	0,1	0,4	0,5

On range ces probabilités dans la matrice de transition $P = (p_{ij})$ :

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

La ligne $i$ correspond à l’état de départ, la colonne $j$ à l’état d’arrivée. Ainsi $p_{20} = 0{,}1$ est la probabilité qu’il fasse soleil demain sachant qu’il pleut aujourd’hui.

Une matrice de transition est toujours stochastique :

• tous ses coefficients sont positifs ou nuls, $p_{ij} \geq 0$ ;
• chaque ligne somme à 1, $\sum_j p_{ij} = 1$, car depuis l’état $i$, la chaîne va forcément quelque part (éventuellement elle reste en $i$).

On représente aussi la chaîne par son graphe de transition : un sommet par état, un arc de $i$ vers $j$ chaque fois que $p_{ij} > 0$, étiqueté par $p_{ij}$. Les boucles représentent le fait de rester dans le même état.

Le graphe n’apporte aucune information de plus que la matrice, mais il se lit beaucoup mieux. Au chapitre suivant, c’est sur lui que vous classerez les états.

Piège

Ce sont les lignes qui somment à 1, pas les colonnes. Dans notre matrice, la colonne « pluie » somme à $0{,}1 + 0{,}3 + 0{,}5 = 0{,}9$, et c’est normal. Si vous trouvez des colonnes qui somment à 1 et des lignes qui n’y arrivent pas, vous avez sans doute écrit la transposée.

Prévoir la loi à l’instant n

Supposons qu’il fasse soleil ce matin. Quelle est la probabilité de chaque météo dans trois jours ? On range les probabilités d’état à l’instant $n$ dans un vecteur ligne

$$p(n) = \big(p_0(n), p_1(n), p_2(n)\big) \quad \text{avec} \quad p_i(n) = P(X_n = i).$$

C’est lui aussi un vecteur stochastique : ses coefficients sont positifs et somment à 1. La loi initiale est ici $p(0) = (1, 0, 0)$.

Pour passer d’un jour au suivant, on applique la formule des probabilités totales en conditionnant sur l’état de la veille :

$$p_j(n) = \sum_{i} P(X_n = j \mid X_{n-1} = i)\, P(X_{n-1} = i) = \sum_i p_{i}(n-1)\, p_{ij}$$

C’est exactement un produit vecteur ligne par matrice : $p(n) = p(n-1)\,P$. En répétant, on obtient la formule centrale du régime transitoire :

$$p(n) = p(0)\, P^n$$

où $P^n$ est la puissance $n$-ième de la matrice. Le régime transitoire, c’est justement l’étude de $p(n)$ pour un $n$ donné.

Exemple

Partant de $p(0) = (1, 0, 0)$ (soleil aujourd’hui) :

• $p(1) = p(0)\,P$ est simplement la première ligne de $P$ : $(0{,}6 \,;\, 0{,}3 \,;\, 0{,}1)$.
• $p(2) = p(1)\,P$. Pour la pluie : $0{,}6 \times 0{,}1 + 0{,}3 \times 0{,}3 + 0{,}1 \times 0{,}5 = 0{,}06 + 0{,}09 + 0{,}05 = 0{,}2$. En faisant de même pour les deux autres colonnes, $p(2) = (0{,}46 \,;\, 0{,}34 \,;\, 0{,}2)$.
• $p(3) = p(2)\,P = (0{,}398 \,;\, 0{,}354 \,;\, 0{,}248)$.

Dans trois jours, il y a donc environ une chance sur quatre qu’il pleuve, alors qu’il fait beau aujourd’hui. Vérifiez à chaque étape que les trois nombres somment bien à 1.

À chaque multiplication par P, la masse d'abord concentrée sur le soleil se répartit : la probabilité de pluie passe de 0 à 0,1, puis 0,2, puis 0,248.

On peut aussi calculer la probabilité d’une trajectoire précise. Par la définition des probabilités conditionnelles puis la propriété de Markov, la probabilité d’observer la suite d’états $i_0, i_1, \dots, i_n$ est un simple produit :

$$P(X_0 = i_0, X_1 = i_1, \dots, X_n = i_n) = p_{i_0}(0)\; p_{i_0 i_1}\; p_{i_1 i_2} \cdots p_{i_{n-1} i_n}$$

La probabilité de la loi initiale, puis celle de chaque transition. Sachant qu’il fait soleil aujourd’hui, la trajectoire « soleil, soleil, nuages, pluie » a pour probabilité $1 \times 0{,}6 \times 0{,}3 \times 0{,}3 = 0{,}054$.

Une trajectoire est un chemin dans le treillis des états : sa probabilité est le produit des probabilités lues sur chaque arc emprunté.

La relation de Chapman-Kolmogorov

On note $p_{ij}(n) = P(X_{m+n} = j \mid X_m = i)$ la probabilité de passer de $i$ à $j$ en exactement $n$ pas (grâce à l’homogénéité, elle ne dépend pas de $m$). Comment la calculer ? En se demandant par où la chaîne passe à mi-parcours. Pour aller de $i$ à $j$ en $n + m$ pas, elle est forcément dans un certain état $k$ après $n$ pas :

$$p_{ij}(n + m) = \sum_{k \in E} p_{ik}(n)\; p_{kj}(m)$$

C’est la relation de Chapman-Kolmogorov : on somme, sur tous les états intermédiaires $k$, la probabilité d’aller de $i$ à $k$ en $n$ pas puis de $k$ à $j$ en $m$ pas. Sous forme matricielle, si $P(n)$ désigne la matrice des $p_{ij}(n)$, elle s’écrit $P(n + m) = P(n)\,P(m)$, et on en déduit par récurrence que

$$P(n) = P^n.$$

Autrement dit, la matrice de transition en $n$ pas est la puissance $n$-ième de la matrice de transition en un pas. Le coefficient $(i, j)$ de $P^2$ est la probabilité d’aller de $i$ à $j$ en deux jours. Pour notre météo :

$$P^2 = \begin{pmatrix} 0{,}46 & 0{,}34 & 0{,}2 \\ 0{,}33 & 0{,}37 & 0{,}3 \\ 0{,}23 & 0{,}39 & 0{,}38 \end{pmatrix}$$

S’il pleut aujourd’hui, il pleuvra encore après-demain avec probabilité 0,38.

Chapman-Kolmogorov en image : on somme sur l'état intermédiaire k les produits des deux étapes. L'épaisseur de chaque chemin suit sa contribution ; le passage par la pluie pèse le plus (0,25 sur 0,38).

À retenir

Tout le régime transitoire tient en deux formules : $p(n) = p(0)\,P^n$ pour la loi à l’instant $n$, et $P(n) = P^n$ pour les transitions en $n$ pas. Le vecteur de probabilités est un vecteur ligne, placé à gauche de la matrice.

Calculer et simuler en Python

Avec NumPy, les calculs précédents tiennent en quelques lignes. La simulation, elle, tire au hasard une trajectoire : à chaque pas, on choisit l’état suivant selon la ligne de $P$ correspondant à l’état présent.

import numpy as np

etats = ["soleil", "nuages", "pluie"]
P = np.array([[0.6, 0.3, 0.1],
              [0.3, 0.4, 0.3],
              [0.1, 0.4, 0.5]])
assert np.allclose(P.sum(axis=1), 1)        # chaque ligne somme à 1

p0 = np.array([1.0, 0.0, 0.0])               # soleil aujourd'hui
p3 = p0 @ np.linalg.matrix_power(P, 3)       # vecteur ligne à gauche
print(p3)                                    # [0.398 0.354 0.248]

# Simulation de 100 000 trajectoires de 3 jours
rng = np.random.default_rng(0)
n_traj, pluie_j3 = 100_000, 0
for _ in range(n_traj):
    x = 0
    for _ in range(3):
        x = rng.choice(3, p=P[x])            # tirage selon la ligne de l'état courant
    pluie_j3 += (x == 2)
print(pluie_j3 / n_traj)                     # proche de 0.248

La simulation ne sert à rien ici, puisque le calcul exact est immédiat. Mais elle devient précieuse dès que le modèle se complique (un espace d’états énorme, des règles difficiles à écrire en matrice). Vérifier un calcul par simulation, et l’inverse, est un bon réflexe que nous garderons tout au long du cours.

La fréquence simulée oscille beaucoup au début puis se resserre autour du calcul exact 0,248 : l'écart typique décroît comme l'inverse de la racine du nombre de trajectoires.

En entretien

« Une chaîne de Markov, c’est un système aléatoire dont le futur ne dépend du passé que par l’état présent. On la décrit par une matrice de transition dont chaque ligne est une loi de probabilité, et la loi à l’instant $n$ s’obtient par $p(0)P^n$. »

En résumé

• Un processus stochastique est une famille $(X_t)_{t \in T}$ de variables aléatoires ; à temps discret, on parle de chaîne.
• Propriété de Markov : sachant l’état présent, le futur est indépendant du passé. Si elle n’est pas vérifiée, on peut enrichir l’état.
• Une chaîne homogène est décrite par sa matrice de transition $P$ : ligne = départ, colonne = arrivée, lignes de somme 1. Le graphe associé a un arc $i \to j$ quand $p_{ij} > 0$.
• La loi à l’instant $n$ est le vecteur ligne $p(n) = p(0)\,P^n$ (régime transitoire).
• La probabilité d’une trajectoire est le produit de la probabilité initiale et des probabilités de transition successives.
• Chapman-Kolmogorov : $p_{ij}(n+m) = \sum_k p_{ik}(n)\,p_{kj}(m)$, soit $P(n) = P^n$.

Exercices

Exercice · Un pas de météo

facile

On reprend la matrice de la météo rennaise. Ce matin, les prévisionnistes hésitent : soleil ou pluie, une chance sur deux chacun, $p(0) = (0{,}5 \,;\, 0 \,;\, 0{,}5)$.

1. Vérifiez que $P$ est bien une matrice stochastique.
2. Calculez $p(1)$.

Voir la solution

1. Tous les coefficients sont positifs, et chaque ligne somme à 1 : $0{,}6 + 0{,}3 + 0{,}1 = 1$, $0{,}3 + 0{,}4 + 0{,}3 = 1$, $0{,}1 + 0{,}4 + 0{,}5 = 1$.

2. $p(1) = p(0)\,P = 0{,}5 \times (\text{ligne soleil}) + 0{,}5 \times (\text{ligne pluie})$ :

   • soleil : $0{,}5 \times 0{,}6 + 0{,}5 \times 0{,}1 = 0{,}35$ ;
   • nuages : $0{,}5 \times 0{,}3 + 0{,}5 \times 0{,}4 = 0{,}35$ ;
   • pluie : $0{,}5 \times 0{,}1 + 0{,}5 \times 0{,}5 = 0{,}3$.

   Donc $p(1) = (0{,}35 \,;\, 0{,}35 \,;\, 0{,}3)$, qui somme bien à 1.

En code

Python

import numpy as np

# Météo rennaise : soleil, nuages, pluie
P = np.array([[0.6, 0.3, 0.1],
              [0.3, 0.4, 0.3],
              [0.1, 0.4, 0.5]])
print((P >= 0).all(), P.sum(axis=1))    # True [1. 1. 1.]

p0 = np.array([0.5, 0.0, 0.5])          # soleil ou pluie, une chance sur deux
p1 = p0 @ P                             # vecteur ligne à gauche
print(p1, p1.sum())                     # [0.35 0.35 0.3 ] 1.0

R

# Météo rennaise : soleil, nuages, pluie
P <- matrix(c(0.6, 0.3, 0.1,
              0.3, 0.4, 0.3,
              0.1, 0.4, 0.5), nrow = 3, byrow = TRUE)
all(P >= 0); rowSums(P)                 # TRUE ; 1 1 1

p0 <- c(0.5, 0, 0.5)                    # soleil ou pluie, une chance sur deux
p1 <- p0 %*% P                          # vecteur ligne à gauche
p1; sum(p1)                             # 0.35 0.35 0.3 ; 1

Exercice · Trajectoires et transitions en deux pas

moyen

Il pleut aujourd’hui.

1. Quelle est la probabilité d’observer exactement « pluie, nuages, soleil » aujourd’hui, demain et après-demain ?
2. Calculez, à l’aide de Chapman-Kolmogorov, la probabilité qu’il fasse soleil après-demain. Retrouvez-la dans la matrice $P^2$.
3. Pourquoi la réponse à la question 2 est-elle plus grande que celle de la question 1 ?

Voir la solution

1. La loi initiale met toute la masse sur « pluie ». La probabilité est $1 \times p_{21} \times p_{10} = 0{,}4 \times 0{,}3 = 0{,}12$.
2. On somme sur la météo de demain $k$ : $p_{20}(2) = p_{20}\,p_{00} + p_{21}\,p_{10} + p_{22}\,p_{20} = 0{,}1 \times 0{,}6 + 0{,}4 \times 0{,}3 + 0{,}5 \times 0{,}1 = 0{,}06 + 0{,}12 + 0{,}05 = 0{,}23$. C’est bien le coefficient (ligne pluie, colonne soleil) de $P^2$.
3. La question 2 regroupe toutes les trajectoires qui finissent au soleil après-demain (en passant par le soleil, les nuages ou la pluie demain), alors que la question 1 n’en compte qu’une. La trajectoire par les nuages représente $0{,}12$ sur les $0{,}23$.

En code

Python

import numpy as np

P = np.array([[0.6, 0.3, 0.1],
              [0.3, 0.4, 0.3],
              [0.1, 0.4, 0.5]])
SOLEIL, NUAGES, PLUIE = 0, 1, 2

# 1) Trajectoire pluie -> nuages -> soleil (il pleut aujourd'hui avec certitude)
print(P[PLUIE, NUAGES] * P[NUAGES, SOLEIL])          # 0.12

# 2) Chapman-Kolmogorov : somme sur la météo de demain k
termes = P[PLUIE, :] * P[:, SOLEIL]
print(termes, termes.sum())                          # [0.06 0.12 0.05] 0.23
print(np.linalg.matrix_power(P, 2)[PLUIE, SOLEIL])   # 0.23, coefficient de P^2

R

P <- matrix(c(0.6, 0.3, 0.1,
              0.3, 0.4, 0.3,
              0.1, 0.4, 0.5), nrow = 3, byrow = TRUE)
soleil <- 1; nuages <- 2; pluie <- 3

# 1) Trajectoire pluie -> nuages -> soleil
P[pluie, nuages] * P[nuages, soleil]    # 0.12

# 2) Chapman-Kolmogorov : somme sur la météo de demain
termes <- P[pluie, ] * P[, soleil]
termes; sum(termes)                     # 0.06 0.12 0.05 ; 0.23
(P %*% P)[pluie, soleil]                # 0.23, coefficient de P^2

Exercice · Rendre markovien un processus à mémoire

difficile

Un modèle plus fin de la météo ne distingue que deux états, sec (S) et pluvieux (P), mais tient compte des deux derniers jours : s’il a plu hier et aujourd’hui, il pleut demain avec probabilité 0,7 ; s’il a plu un seul des deux jours, avec probabilité 0,5 ; s’il a fait sec les deux jours, avec probabilité 0,2.

1. La suite $(X_n)$ des météos quotidiennes est-elle une chaîne de Markov ?
2. Construisez une chaîne de Markov en prenant pour état le couple $Y_n = (X_{n-1}, X_n)$. Combien a-t-elle d’états ? Écrivez sa matrice de transition.

Voir la solution

1. Non : la loi de $X_{n+1}$ dépend de $X_n$ et de $X_{n-1}$. Savoir qu’il pleut aujourd’hui ne suffit pas, il faut savoir s’il a plu hier.
2. L’état $Y_n = (X_{n-1}, X_n)$ prend 4 valeurs : SS, SP, PS, PP. Depuis l’état $(x, y)$, la chaîne ne peut aller que vers $(y, z)$ : le second élément du couple devient le premier. Avec l’ordre SS, SP, PS, PP :

$$Q = \begin{pmatrix} 0{,}8 & 0{,}2 & 0 & 0 \\ 0 & 0 & 0{,}5 & 0{,}5 \\ 0{,}5 & 0{,}5 & 0 & 0 \\ 0 & 0 & 0{,}3 & 0{,}7 \end{pmatrix}$$

Par exemple, depuis SP (sec hier, pluie aujourd’hui), il a plu un seul des deux jours, donc demain il pleut avec probabilité 0,5 (on va en PP) ou il fait sec (on va en PS). Chaque ligne somme à 1, et la loi du futur ne dépend que du couple présent : $(Y_n)$ est markovienne. C’est la technique générale pour traiter une mémoire d’ordre 2, au prix d’un espace d’états plus grand.

En code

Python

import numpy as np

# Probabilité de pluie demain selon le nombre de jours de pluie parmi (hier, aujourd'hui)
p_pluie = {0: 0.2, 1: 0.5, 2: 0.7}
couples = ["SS", "SP", "PS", "PP"]              # (hier, aujourd'hui)

Q = np.zeros((4, 4))
for i, (hier, auj) in enumerate(couples):
    p = p_pluie[(hier == "P") + (auj == "P")]
    Q[i, couples.index(auj + "P")] = p          # le couple glisse : (auj, demain)
    Q[i, couples.index(auj + "S")] = 1 - p
print(Q)
# [[0.8 0.2 0.  0. ]
#  [0.  0.  0.5 0.5]
#  [0.5 0.5 0.  0. ]
#  [0.  0.  0.3 0.7]]
print(Q.sum(axis=1))                            # [1. 1. 1. 1.]

R

# Probabilité de pluie demain selon le nombre de jours de pluie parmi (hier, aujourd'hui)
p_pluie <- c(0.2, 0.5, 0.7)             # 0, 1 ou 2 jours de pluie
couples <- c("SS", "SP", "PS", "PP")    # (hier, aujourd'hui)

Q <- matrix(0, 4, 4, dimnames = list(couples, couples))
for (co in couples) {
  hier <- substr(co, 1, 1); auj <- substr(co, 2, 2)
  p <- p_pluie[(hier == "P") + (auj == "P") + 1]
  Q[co, paste0(auj, "P")] <- p          # le couple glisse : (auj, demain)
  Q[co, paste0(auj, "S")] <- 1 - p
}
Q
##     SS  SP  PS  PP
## SS 0.8 0.2 0.0 0.0
## SP 0.0 0.0 0.5 0.5
## PS 0.5 0.5 0.0 0.0
## PP 0.0 0.0 0.3 0.7
rowSums(Q)                              # 1 1 1 1