Chaînes de Markov et applications

Introduction

Les chaînes de Markov sont des modèles probabilistes qui décrivent l'évolution d'un système dans le temps. Elles sont étroitement liées aux graphes orientés pondérés et aux matrices stochastiques, offrant de nombreuses applications en sciences, économie et informatique.

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

Chaîne de Markov : Une chaîne de Markov (ou processus markovien) est un processus stochastique à temps discret où l'état futur du système ne dépend que de l'état présent, et non des états passés.

Formellement, pour une suite d'états X_0, X_1, X_2, :

[formule]

C'est la propriété de Markov : "le futur ne dépend que du présent".

Exemple : Un étudiant peut être dans l'un des états : "étudiant" (E), "diplômé" (D), "abandon" (A).

Les probabilités de transition peuvent être :

P(X_{n+1} = D | X_n = E) = 0,7 (probabilité de réussir)
P(X_{n+1} = A | X_n = E) = 0,2 (probabilité d'abandonner)
P(X_{n+1} = E | X_n = E) = 0,1 (probabilité de redoubler)

2. Matrice de transition

Matrice de transition : Soit une chaîne de Markov avec n états possibles {1, 2, , n}.

La matrice de transition P = (p_{i,j}) est la matrice carrée d'ordre n où :

[formule]

est la probabilité de passer de l'état i à l'état j en une étape.

Propriétés de la matrice de transition : Pour une matrice de transition P :

Coefficients positifs : p_{i,j} 0 pour tout i, j
Somme des lignes égale à 1 : {j=1}^{n} p{i,j} = 1 pour tout i

Une matrice vérifiant ces propriétés est appelée matrice stochastique (ou matrice markovienne).

Exemple : Reprenons l'exemple de l'étudiant avec les états E, D, A.

La matrice de transition est :

[formule]

où :

Ligne 1 (état E) : p_{1,1} = 0{,}1, p_{1,2} = 0{,}7, p_{1,3} = 0{,}2
Ligne 2 (état D) : une fois diplômé, on reste diplômé (p_{2,2} = 1)
Ligne 3 (état A) : une fois abandonné, on reste abandonné (p_{3,3} = 1)

3. Distribution de probabilité

Vecteur de probabilité : Un vecteur de probabilité (ou distribution de probabilité) est un vecteur ligne = (_1, _2, , _n) tel que :

_i 0 pour tout i
_{i=1}^{n} _i = 1

Le coefficient _i représente la probabilité d'être dans l'état i.

Évolution de la distribution : Si ^{(n)} est la distribution de probabilité à l'instant n, alors :

[formule]

Autrement dit, la distribution à l'instant n+1 s'obtient en multipliant la distribution à l'instant n par la matrice de transition.

Exemple : Si à l'instant n = 0, on a ^{(0)} = (1, 0, 0) (l'étudiant est dans l'état E avec probabilité 1), alors :

[formule]

À l'instant n = 1, l'étudiant a :

Probabilité 0{,}1 d'être encore étudiant
Probabilité 0{,}7 d'être diplômé
Probabilité 0{,}2 d'avoir abandonné

4. Probabilités de transition en k étapes

Puissances de la matrice de transition : Soit P la matrice de transition d'une chaîne de Markov.

Le coefficient (P^k)_{i,j} de la matrice P^k donne la probabilité de passer de l'état i à l'état j en exactement k étapes :

[formule]

Exemple : Calculons P^2 pour la matrice précédente :

[formule]

(P^2)_{1,2} = 0{,}77 : probabilité qu'un étudiant soit diplômé après 2 étapes
(P^2)_{1,1} = 0{,}01 : probabilité qu'un étudiant soit encore étudiant après 2 étapes

5. Distribution stationnaire

Distribution stationnaire : Une distribution stationnaire (ou distribution invariante) est un vecteur de probabilité tel que :

[formule]

Autrement dit, si la distribution est à un instant donné, elle reste aux instants suivants.

Existence et unicité : Sous certaines conditions (chaîne irréductible et apériodique), il existe une unique distribution stationnaire qui peut être trouvée en résolvant le système :

[formule]

Exemple : Pour la matrice P = pmatrix 0{,}5 & 0{,}5 0{,}3 & 0{,}7 pmatrix, cherchons la distribution stationnaire = (_1, _2).

De = P, on obtient :

_1 = 0{,}5_1 + 0{,}3_2
_2 = 0{,}5_1 + 0{,}7_2
_1 + _2 = 1

En résolvant, on trouve _1 = 3{8} et _2 = 5{8}.

Vérification : P = (3{8}, 5{8})P = (3{8}, 5{8}) =

6. Graphe de transition

Graphe de transition : Le graphe de transition d'une chaîne de Markov est un graphe orienté pondéré où :

Les sommets représentent les états
Il existe un arc de i vers j si p_{i,j} > 0
Le poids de l'arc (i,j) est p_{i,j}

Exemple : Pour la matrice P = pmatrix 0{,}5 & 0{,}5 0{,}3 & 0{,}7 pmatrix, le graphe de transition a :

État 1 État 1 avec poids 0{,}5
État 1 État 2 avec poids 0{,}5
État 2 État 1 avec poids 0{,}3
État 2 État 2 avec poids 0{,}7

7. États absorbants

État absorbant : Un état i est absorbant si p_{i,i} = 1 (et donc p_{i,j} = 0 pour j i).

Une fois atteint, un état absorbant ne peut plus être quitté.

Exemple : Dans l'exemple de l'étudiant, les états D (diplômé) et A (abandon) sont absorbants car :

p_{2,2} = 1 (diplômé reste diplômé)
p_{3,3} = 1 (abandon reste abandon)

8. Temps d'absorption

Temps moyen d'absorption : Pour une chaîne de Markov avec des états absorbants, on peut calculer le temps moyen d'absorption (nombre moyen d'étapes avant d'atteindre un état absorbant) en résolvant un système d'équations linéaires.

9. Applications

Applications des chaînes de Markov :

Modélisation de populations : évolution démographique, épidémies
Fiabilité : systèmes techniques, réseaux informatiques
Finance : modélisation de marchés, risques de crédit
Informatique : algorithmes de PageRank, modèles de cache
Biologie : évolution génétique, modèles d'ADN
Linguistique : modèles de langage, prédiction de texte

10. Chaîne de Markov et matrices

Lien avec les matrices : Les chaînes de Markov peuvent être entièrement décrites par :

La matrice de transition P (matrice stochastique)
Le vecteur de probabilité initial ^{(0)}

L'évolution est donnée par : ^{(n)} = ^{(0)} P^n

Méthode de calcul : Pour calculer la distribution après n étapes :

Partir de la distribution initiale ^{(0)}
Calculer ^{(n)} = ^{(0)} P^n
Interpréter les résultats

Pour trouver la distribution stationnaire :

Résoudre le système = P avec _i = 1
Vérifier l'unicité et la stabilité

À retenir

Résumé :

Chaîne de Markov : processus où le futur ne dépend que du présent
Matrice de transition P : p_{i,j} = P(X_{n+1} = j | X_n = i), matrice stochastique
Évolution : ^{(n+1)} = ^{(n)} P et ^{(n)} = ^{(0)} P^n
Probabilités en k étapes : (P^k){i,j} = P(X{n+k} = j | X_n = i)
Distribution stationnaire : tel que = P
États absorbants : états i avec p_{i,i} = 1

Méthode pratique : Pour analyser une chaîne de Markov :

Construire la matrice de transition P
Vérifier que P est stochastique (somme des lignes = 1)
Calculer P^n pour les probabilités à long terme
Résoudre = P pour la distribution stationnaire

Les chaînes de Markov, combinées avec les matrices, offrent un cadre puissant pour modéliser et analyser l'évolution de systèmes complexes dans de nombreux domaines.