Aller au contenu
Processus stochastiques · L3

Leçon 1 sur 5

Chaînes de Markov à temps discret

Je sais reconnaître une chaîne de Markov à temps discret, écrire sa matrice de transition et son graphe, et calculer la loi de la chaîne après n étapes avec les puissances de la matrice.

  • 1 h 30
  • 7 exercices corrigés
  • QCM de 6 questions

À la fin de la leçon, vous saurez :

  • Définir un processus stochastique, son espace d'états et ses trajectoires
  • Énoncer la propriété de Markov et reconnaître une chaîne homogène
  • Construire la matrice de transition et le graphe d'une chaîne
  • Calculer la probabilité d'une trajectoire et la loi à l'instant n avec la relation de Chapman-Kolmogorov
  • Étudier complètement une chaîne à deux états

Avant de commencer : Probabilités (probabilités conditionnelles, variables aléatoires discrètes) et algèbre linéaire (produit de matrices).

1Je découvre

Dôni Express est une petite société de livraison à moto installée à Conakry. Ses livreurs travaillent dans trois communes : Kaloum, Dixinn et Ratoma. Chaque course part de la commune où se trouve le livreur et se termine dans une commune, parfois la même.

Pendant trois mois, la responsable des opérations a noté, pour chaque course, la commune de départ et la commune d'arrivée. Elle constate une chose simple : la commune où arrive un livreur dépend de la commune d'où il part, mais pas du chemin qu'il a suivi avant. Un livreur qui part de Kaloum arrive à Dixinn environ une fois sur deux, qu'il soit venu de Ratoma ou de Dixinn le matin.

Elle veut savoir où seront ses livreurs après deux ou trois courses, pour placer ses motos de réserve au bon endroit. Elle n'a pas besoin de connaître chaque client : il lui faut un modèle du hasard qui gouverne les déplacements.

Comment modéliser une suite d'états aléatoires où l'avenir ne dépend que du présent, et comment calculer la loi de l'état après n étapes ?

2Je comprends

1. Processus stochastique : le vocabulaire

Un processus stochastique est une famille de variables aléatoires (Xt)t ∈ T définies sur un même espace probabilisé (Ω, A, mathbbP) et à valeurs dans un ensemble E.

NotionDéfinitionExemple Dôni Express
Ensemble des temps Tdiscret (T = ℕ) ou continu (T = ℝ_+)n = numéro de la course
Espace d'états Eensemble des valeurs possiblesE = {K, D, R}
État à l'instant tla valeur XtX3 = R : après 3 courses, le livreur est à Ratoma
Trajectoirepour ω fixé, la suite t ↦ Xt(ω)K, D, D, R, K, …

Ce cours étudie d'abord le cas le plus simple : temps discret et espace d'états fini ou dénombrable. Les leçons 4 et 5 passeront au temps continu (processus de Poisson, mouvement brownien).

Une suite de variables indépendantes (lancers de dé) est un processus sans mémoire du tout : c'est trop pauvre pour décrire les livreurs. À l'inverse, un processus où l'avenir dépend de tout le passé est trop riche pour être calculé. La chaîne de Markov est le compromis : l'avenir dépend du passé seulement à travers le présent.

2. Définition d'une chaîne de Markov

Soit E fini ou dénombrable. La suite (Xn)n ≥ 0 à valeurs dans E est une chaîne de Markov si, pour tout n et tous états i0, …, in-1, i, j tels que la probabilité conditionnante soit non nulle :

mathbbP(Xn+1 = j | Xn = i, Xn-1 = in-1, …, X0 = i0) = mathbbP(Xn+1 = j | Xn = i).

C'est la propriété de Markov. La chaîne est homogène si cette probabilité ne dépend pas de n ; on la note alors pij. Dans tout le cours, les chaînes sont homogènes.

La matrice de transition est P = (pij)i,j ∈ E. Elle est stochastique :

pij ≥ 0 et Σj ∈ E pij = 1 pour tout i.

La ligne i est la loi de l'état suivant quand on est en i. Attention : ce sont les lignes, pas les colonnes, qui somment à 1.

Pour Dôni Express, avec l'ordre (K, D, R), les relevés donnent :

P = beginpmatrix 0,2 & 0,5 & 0,3
0,3 & 0,3 & 0,4
0,1 & 0,4 & 0,5 endpmatrix.

Le graphe de transition a un sommet par état et une flèche i → j étiquetée pij quand pij > 0 :

          0,5               0,4
   ( K ) -----> ( D ) -----> ( R )
   0,2 ↺        0,3 ↺        0,5 ↺
   K → R : 0,3   D → K : 0,3   R → K : 0,1   R → D : 0,4

La chaîne est entièrement déterminée par sa loi initiale µ0(i) = mathbbP(X0 = i) et sa matrice P.

3. Probabilité d'une trajectoire

En appliquant la formule des probabilités composées puis la propriété de Markov :

mathbbP(X0 = i0, X1 = i1, …, Xn = in) = µ0(i0) pi0 i1 pi1 i2 ⋯ pin-1 in.

Exemple

Un livreur commence sa journée à Kaloum (X0 = K avec certitude).

Quelle est la probabilité qu'il fasse le parcours K → D → R → R ?

Étape 1 : on lit les transitions utiles : p(K,D) = 0,5 ; p(D,R) = 0,4 ; p(R,R) = 0,5.

Étape 2 : on multiplie : 1 × 0,5 × 0,4 × 0,5 = 0,1.

Réponse : une chance sur dix.

Si le livreur part de Kaloum avec probabilité 0,5 seulement, on multiplie encore par 0,5 : 0,05.

Réciproquement, toute matrice stochastique P et toute loi µ0 définissent une chaîne de Markov : on peut la construire par la récurrence Xn+1 = f(Xn, Un+1), où les Un sont indépendantes et uniformes sur [0, 1] et où f(i, u) est l'état j tel que Σk < j pik ≤ u < Σk ≤ j pik. C'est exactement ainsi qu'on simule une chaîne sur ordinateur (leçon 5).

4. Transitions en n étapes : Chapman-Kolmogorov

On note p(n)ij = mathbbP(Xm+n = j | Xm = i). En décomposant selon l'état intermédiaire :

p(m+n)ij = Σk ∈ E p(m)ik p(n)kj (relation de Chapman-Kolmogorov).

On en déduit que la matrice des transitions en n étapes est la puissance Pn. Si l'on écrit la loi de Xn comme un vecteur ligne µn :

µn = µ0 Pn, µn+1 = µn P.

Exemple

Calcul de P² pour Dôni Express (ordre K, D, R).

Ligne K : (0,2 ; 0,5 ; 0,3) multipliée par chaque colonne de P.

colonne K : 0,2×0,2 + 0,5×0,3 + 0,3×0,1 = 0,04 + 0,15 + 0,03 = 0,22

colonne D : 0,2×0,5 + 0,5×0,3 + 0,3×0,4 = 0,10 + 0,15 + 0,12 = 0,37

colonne R : 0,2×0,3 + 0,5×0,4 + 0,3×0,5 = 0,06 + 0,20 + 0,15 = 0,41

De même : ligne D = (0,19 ; 0,40 ; 0,41) et ligne R = (0,19 ; 0,37 ; 0,44).

Contrôle : chaque ligne somme à 1 (0,22 + 0,37 + 0,41 = 1).

Un livreur parti de Kaloum est à Ratoma après deux courses avec probabilité 0,41.

Si le matin 50 % des livreurs sont à Kaloum, 30 % à Dixinn, 20 % à Ratoma :

μ1 = μ0 P = (0,21 ; 0,42 ; 0,37) et μ2 = μ1 P = (0,205 ; 0,379 ; 0,416).

On remarque que les trois lignes de P2 se ressemblent déjà, et que celles de P3 sont encore plus proches (environ 0,19 ; 0,38 ; 0,42) : la chaîne « oublie » son point de départ. La leçon 2 expliquera pourquoi.

Méthode

Calculer la loi d'une chaîne après n étapes

  1. Fixer l'ordre des états et écrire P ; vérifier que chaque ligne somme à 1.
  2. Écrire la loi initiale μ0 comme un vecteur ligne.
  3. Calculer μ1 = μ0 P, puis μ2 = μ1 P, etc. (ou P^n puis μ0 P^n).
  4. Pour une probabilité conditionnelle P(Xn = j | X0 = i), lire le coefficient (i, j) de P^n.
  5. Contrôler : chaque μn est une loi (coefficients positifs, somme égale à 1).

5. La chaîne à deux états, entièrement calculée

Soit E = {1, 2} et P = beginpmatrix 1 - a & a
b & 1 - b endpmatrix
avec 0 < a + b < 2. Les valeurs propres de P sont 1 et λ = 1 - a - b, avec |λ| < 1. Par diagonalisation :

Pn = 1a + bbeginpmatrix b & a
b & a endpmatrix + (1 - a - b)na + bbeginpmatrix a & -a
-b & b endpmatrix.

Quand n → ∞, le second terme tend vers 0 : chaque ligne de Pn tend vers (ba+b, aa+b), quelle que soit la ligne de départ.

Exemple

À Labé, on modélise le temps d'une journée de saison des pluies par Sec (S) ou Pluie (Pl).

Supposons : après un jour sec, pluie avec probabilité a = 0,2 ; après un jour de pluie, sec avec b = 0,4.

Étape 1 : λ = 1 − 0,2 − 0,4 = 0,4 et a + b = 0,6.

Étape 2 : P^n(S, S) = 0,4/0,6 + (0,2/0,6) × 0,4^n = 2/3 + (1/3) × 0,4^n.

Étape 3 : n = 2 donne 2/3 + 0,16/3 = 0,72 ; n = 3 donne 2/3 + 0,064/3 = 0,688.

Étape 4 : à long terme, la probabilité d'un jour sec tend vers 2/3.

6. Reconnaître une chaîne de Markov

ProcessusMarkov ?Pourquoi
Commune d'un livreur après chaque courseoui (modèle)l'arrivée dépend seulement du départ
Sn = ξ1 + … + ξn, ξk i.i.d.ouiSn+1 = Sn + ξn+1, avec ξn+1 indépendant du passé
Mn = max(ξ1, …, ξn), ξk i.i.d.ouiMn+1 = max(Mn, ξn+1)
Stock d'une boutique en fin de semaine, commandes i.i.d.ouistock suivant = fonction du stock et de la demande nouvelle
Temps qu'il fait, si la pluie dépend des deux jours précédentsnon sur {S, Pl}mais oui sur les couples (Xn-1, Xn)

Le dernier cas est important : un processus qui n'est pas markovien peut le devenir si l'on enrichit l'état. Le résultat général est : si Xn+1 = f(Xn, ξn+1) avec (ξn) i.i.d. indépendante de X0, alors (Xn) est une chaîne de Markov.

3Je retiens

Je retiens

Chaîne de Markov : la loi de X(n+1) sachant tout le passé ne dépend que de X(n).

Homogène : p(i,j) = P(X(n+1) = j | X(n) = i) ne dépend pas de n.

P est stochastique : coefficients positifs, chaque LIGNE somme à 1.

Probabilité d'une trajectoire : μ0(i0) × p(i0,i1) × … × p(i(n−1),in).

Chapman-Kolmogorov : transitions en n étapes = P^n.

Loi à l'instant n (vecteur ligne) : μn = μ0 P^n.

Chaîne à deux états : P^n tend vers des lignes égales à (b/(a+b) ; a/(a+b)).

4Erreurs fréquentes

  • Faire sommer les colonnes de P à 1 : ce sont les lignes.
  • Calculer P^n μ0 avec μ0 en colonne : la loi est un vecteur ligne, μn = μ0 P^n.
  • Croire que P²(i,j) = p(i,j)² : il faut sommer sur tous les états intermédiaires.
  • Oublier le facteur μ0(i0) dans la probabilité d'une trajectoire.
  • Confondre « indépendance » et « propriété de Markov » : une chaîne a une mémoire d'un pas.

5Je m’exerce

1Exercice 1

(Questions de cours)

a) Énoncez la propriété de Markov et la définition d'une chaîne homogène.

b) Qu'est-ce qu'une matrice stochastique ?

c) Écrivez la relation de Chapman-Kolmogorov.

Voir le corrigéCacher le corrigé

a) Pour tout n et tous états : mathbbP(Xn+1 = j | Xn = i, Xn-1 = in-1, …, X0 = i0) = mathbbP(Xn+1 = j | Xn = i). La chaîne est homogène si cette probabilité ne dépend pas de n.

b) Une matrice à coefficients positifs ou nuls dont chaque ligne somme à 1.

c) p(m+n)ij = Σk p(m)ik p(n)kj, soit Pm+n = Pm Pn.

2Exercice 2

Les matrices suivantes sont-elles des matrices de transition ? Justifiez.

A = beginpmatrix 0,5 & 0,5
0,7 & 0,3 endpmatrix
 ; B = beginpmatrix 0,6 & 0,3
0,4 & 0,7 endpmatrix
 ; C = beginpmatrix 1 & 0 & 0
0,2 & 0 & 0,8
0 & 1,1 & -0,1 endpmatrix
.

Voir le corrigéCacher le corrigé

A : oui, coefficients positifs et lignes de somme 1 (0,5 + 0,5 et 0,7 + 0,3).

B : non, la première ligne somme à 0,9 et la seconde à 1,1 (ce sont les colonnes qui somment à 1).

C : non, la troisième ligne contient 1,1 et -0,1 ; une probabilité est entre 0 et 1, même si la ligne somme à 1.

3Exercice 3

Pour la chaîne de Dôni Express, avec X0 = D, calculez :

a) mathbbP(X1 = K, X2 = K, X3 = R) ;

b) mathbbP(X2 = R | X0 = D) ;

c) mathbbP(X1 = R, X2 = R).

Voir le corrigéCacher le corrigé

a) pDK pKK pKR = 0,3 × 0,2 × 0,3 = 0,018.

b) C'est le coefficient (D, R) de P2 : 0,3 × 0,3 + 0,3 × 0,4 + 0,4 × 0,5 = 0,09 + 0,12 + 0,20 = 0,41.

c) pDR pRR = 0,4 × 0,5 = 0,2.

4Exercice 4

On lance un dé équilibré à répétition et on note Mn le plus grand résultat obtenu lors des n premiers lancers.

a) Montrez que (Mn)n ≥ 1 est une chaîne de Markov et donnez sa matrice de transition.

b) Calculez mathbbP(M2 = 6 | M1 = 4) et mathbbP(M3 = 4 | M1 = 4).

Voir le corrigéCacher le corrigé

a) Si ξn+1 est le (n+1)-ième lancer, Mn+1 = max(Mn, ξn+1) avec ξn+1 indépendant de (M1, …, Mn) : c'est une chaîne de Markov (forme Xn+1 = f(Xn, ξn+1)). Depuis l'état i : on reste en i si le lancer est ≤ i, d'où pii = i/6 ; on va en j > i si le lancer vaut j, d'où pij = 1/6 ; pij = 0 si j < i. Contrôle : i/6 + (6 - i)/6 = 1.

b) mathbbP(M2 = 6 | M1 = 4) = p46 = 1/6. mathbbP(M3 = 4 | M1 = 4) = p442 = (4/6)2 = 4/9, car on ne peut pas redescendre : il faut rester deux fois en 4.

5Exercice 5

À Labé, on reprend la chaîne Sec / Pluie de la sous-partie 5 (a = 0,2, b = 0,4).

a) Il pleut lundi. Quelle est la probabilité qu'il pleuve mercredi ?

b) Donnez la formule de mathbbP(Xn = Pl | X0 = Pl) et sa limite.

Voir le corrigéCacher le corrigé

a) De lundi à mercredi : deux étapes. P2 = beginpmatrix 0,72 & 0,28
0,56 & 0,44 endpmatrix
 ; la probabilité cherchée est 0,6 × 0,6 + 0,4 × 0,2 = 0,36 + 0,08 = 0,44.

b) Avec la formule générale : mathbbP(Xn = Pl | X0 = Pl) = aa+b + ba+bλn = 13 + 23(0,4)n. Pour n = 2 : 1/3 + 0,32/3 = 0,44, ce qui confirme a). La limite est 1/3.

6Exercice 6

On suppose que la pluie d'un jour dépend des deux jours précédents. Expliquez pourquoi (Xn) n'est pas une chaîne de Markov sur {S, Pl} et comment construire une chaîne de Markov à partir de (Xn). Quel est son espace d'états ?

Voir le corrigéCacher le corrigé

La loi de Xn+1 sachant le passé dépend de Xn et de Xn-1 : connaître seulement Xn ne suffit pas, la propriété de Markov est fausse en général. On pose Yn = (Xn-1, Xn). Alors Yn+1 = (Xn, Xn+1) ne dépend que de Yn : (Yn) est une chaîne de Markov sur {(S,S), (S,Pl), (Pl,S), (Pl,Pl)}, soit 4 états. Depuis (x, y), on ne peut aller que vers un état de la forme (y, z).

7Exercice 7

(Type examen) Une coopérative de crédit agricole de Faranah classe chaque mois ses emprunteurs en trois états : À jour (A), En retard (R), Défaut (D). Un emprunteur en défaut y reste. Supposons les transitions mensuelles : depuis A, A avec 0,9 et R avec 0,1 ; depuis R, A avec 0,5, R avec 0,3 et D avec 0,2.

a) Écrivez la matrice P et dessinez le graphe.

b) Calculez P2.

c) Un emprunteur est à jour aujourd'hui. Quelle est la probabilité qu'il soit en défaut dans deux mois ?

d) Aujourd'hui, 80 % des emprunteurs sont à jour et 20 % en retard. Donnez la répartition attendue dans un mois.

e) Calculez la probabilité de la trajectoire A, A, R, D sur trois mois, sachant que l'emprunteur est à jour aujourd'hui.

Voir le corrigéCacher le corrigé

a) Ordre (A, R, D) : P = beginpmatrix 0,9 & 0,1 & 0
0,5 & 0,3 & 0,2
0 & 0 & 1 endpmatrix
. Graphe : boucle 0,9 sur A ; A → R (0,1) ; R → A (0,5) ; boucle 0,3 sur R ; R → D (0,2) ; boucle 1 sur D.

b) Ligne A : (0,81 + 0,05 ; 0,09 + 0,03 ; 0,02) = (0,86 ; 0,12 ; 0,02). Ligne R : (0,45 + 0,15 ; 0,05 + 0,09 ; 0,06 + 0,2) = (0,60 ; 0,14 ; 0,26). Ligne D : (0 ; 0 ; 1). Chaque ligne somme à 1.

c) Coefficient (A, D) de P2 : 0,02 (il faut passer par R puis aller en D : 0,1 × 0,2).

d) µ1 = (0,8 ; 0,2 ; 0) P = (0,72 + 0,10 ; 0,08 + 0,06 ; 0,04) = (0,82 ; 0,14 ; 0,04) : 82 % à jour, 14 % en retard, 4 % en défaut.

e) pAA pAR pRD = 0,9 × 0,1 × 0,2 = 0,018.

Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.

6Je vérifie

Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.

1Dans une matrice de transition, quelle somme vaut toujours 1 ?
Voir la réponse

Réponse A : la somme de chaque ligne. La ligne i est la loi de l'état suivant quand on est en i.

2La loi de Xn s'obtient par :
Voir la réponse

Réponse B : µ0 Pn avec µ0 en ligne. La loi est un vecteur ligne multiplié à droite par les puissances de P.

3Pour Dôni Express, mathbbP(X2 = R | X0 = K) vaut :
Voir la réponse

Réponse C : 0,41. Coefficient (K, R) de P² : 0,06 + 0,20 + 0,15 = 0,41.

4La relation de Chapman-Kolmogorov s'écrit :
Voir la réponse

Réponse A : Pm+n = Pm Pn. On décompose selon l'état occupé à l'instant intermédiaire.

5Si Xn+1 = f(Xn, ξn+1) avec (ξn) i.i.d. indépendante de X0, alors :
Voir la réponse

Réponse B : (Xn) est une chaîne de Markov. Le nouvel état ne dépend que de l'état présent et d'un aléa neuf.

6Pour une chaîne à deux états avec a = 0,2 et b = 0,4, la limite de Pn(1, 1) est :
Voir la réponse

Réponse B : 2/3. b / (a + b) = 0,4 / 0,6 = 2/3.

Karamö, votre enseignant

Il a lu cette leçon. Posez-lui votre question : il vous répond ici.

Connectez-vous pour poser vos questions à Karamö.

Vous avez fini la leçon ?

Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.

Karamö
Un point pas clair ? Dites à Karamö ce qui vous bloque dans cette leçon : il vous l’explique autrement, pas à pas, sans faire le travail à votre place. Demander à Karamö
Signaler une erreur dans cette leçon

Toutes les leçons de Processus stochastiques

Pose ta question à Karamö