Cheat-Sheet / Chaı̂nes de Markov

DJEBRI

18/12/2023

1 Inverser une Matrice

Pour inverser une matrice A, utilisez la formule suivante:
1
A−1 = · adj(A)
det(A)
où det(A) est le déterminant de A et adj(A) est la matrice adjointe de A.

1.1 Exemple avec une Matrice 2x2

Considérons la matrice A suivante :
 
a b
A=
c d
Le déterminant de A est donné par :

det(A) = ad − bc
La matrice adjointe de A est :
 
d −b
adj(A) =
−c a

2 Diagonaliser une Matrice

Pour diagonaliser une matrice M , il suffit de trouver les valeurs propres (λi ) et
les vecteurs propres correspondants (vi ). Ensuite, il faut former la matrice de
passage P avec les vecteurs propres comme colonnes:
P = [v1 , v2 , . . . , vn ]
La matrice diagonale D d’une matrice M est donnée par:
D = P −1 M P
donc, on peut écrire M de la manière suivante:
M = P DP −1

1
3 Calcul des puissances infinies
Voici un exemple d’une matrice de transition M de taille 2x2 :
 
0.85 0.15
M=
0.35 0.65

a) Calcul des valeurs propres :

Les valeurs propres λ sont les solutions de l’équation caractéristique

det(M − λI) = 0

où I est la matrice identité.

On calcule le déterminant de la matrice M , afin de trouver l’équation per-

mettant de tirer les valeurs propres:
 
0.85 − λ 0.15
det = (0.85−λ)(0.65−λ)−(0.15)(0.35) = λ2 −1.5λ+0.5 = 0
0.35 0.65 − λ

Les solutions de l’équation λ2 − 1.5λ + 0.5 = 0 sont λ1 = 1 et λ2 = 0.5.

b) Calcul des vecteurs propres :

Pour chaque valeur propre λi , on injecte sa valeur dans le système d’équations
(M − λI)v = 0 afin de trouver le vecteur propre correspondant vλi .

Pour λ = 1:     
−0.15 0.15
x 0
=
0.35 −0.35
y 0
 
1
Ce système a une solution non-triviale1 v1 = .
1
De même, pour λ = 0.5, le vecteur propre est obtenu en résolvant le système
correspondant.
    
0.35 0.15 x 0
=
0.35 0.15 y 0
 
−3
Ce système a une solution non-triviale v2 = .
7

1 Cette solution n’est pas unique, mais on utilise celle qui permet de simplifier les calculs

par la suite. Ici, le système donne x = y, donc tout vecteur satisfaisant cette conditions sont
considérés comme vecteurs propres.

2
 c) La matrice de passage P se compose des vecteurs propres (comme colonnes)2 :
 
1 −3
P =
1 7

d) Écriture diagonale :
   −1
1 −3 1 0 1 −3
M = P DP −1 =
1 7 0 0.5 1 7

e) Calcul des Puissances Infinies de M:

M ∞ = P D∞ P −1
où D∞ est une matrice diagonale avec les valeurs propres élevées à la puis-
sance infinie.

M ∞ = (P DP −1 )∞ = P DP −1 P DP −1 ...P DP −1 = P DD..DDP −1 = P D∞ P −1
 
∞ 1 0
Comme nous l’avons calculé précédemment, D = .
0 0
La matrice P est :
 
1 −3
P =
1 7
La matrice P −1 est :
 
0.7 0.3
P −1 =
−0.1 0.1
Calculons P D∞ P −1 :

        
∞ −1 1 −3 1 0 0.7 0.3 1 0 0.7 0.3 0.7 0.3
PD P = = =
1 7 0 0 −0.1 0.1 1 0 −0.1 0.1 0.7 0.3
 
0.7 0.3
Finalement, la matrice M à la puissance infinie est .
0.7 0.3

2 Il faut respecter l’ordre des valeurs propres avec leurs vecteurs propres.

3
4 État initial et transitions
• Une chaı̂ne de Markov à temps discret est un système stochastique à états,
pouvant se trouver dans l’un de ses état à un instant donné (n).
• Le vecteur de probabilité [P (n)] représente les probabilités que le système
soit dans l’un des états après n transitions (i.e., à l’instant n).
• Le vecteur de probabilité [P (0)] représente les probabilités que le système
soit initialement dans l’un des états.
• Faire une transition de l’instant n à l’instant n + 1, revient à choisir un
chemin (une transition) à prendre à partir de l’état actuel de la chaı̂ne.
Dans un calcul générique, ceci revient à calculer les probabilité après une
transition: le produit
[P (n + 1)] = [P (n)]M
récursivement:
[P (x)] = [P (x − 1)]M 1 = [P (x − 2)]M 2 = ... = [P (0)]M x

5 Réductibilité et Régime Permanent

• Une chaı̂ne de Markov est réductible si elle possède au moins une
classe transitoire, c’est-à-dire qu’il existe des états entre lesquels il n’y
a pas de communication. (e.g., on ne peut pas sortir d’une classe finale
vers une classe transitoire, ou d’une classe finale à une autre classe finale).
• Une chaı̂ne de Markov est irréductible si elle est non-réductible. On dit
que la chaı̂ne est donc ergodique (on peut atteindre n’importe quel état
à partir de n’importe quel état: tous les états peuvent communiquer entre
eux).
• Les états d’une chaı̂ne irréductible sont divisés en classes finales (d’où il
n’est pas possible de sortir) et classes transitoires (d’où il est possible
de sortir).
• Le régime permanent d’une chaı̂ne de Markov est atteint lorsque la
probabilité de se trouver dans un état particulier ne change pas avec le
temps. Donc, à un n très élevé (proche de l’infini):
[P (∞)] = [P (0)]M ∞ et [P (∞)] = [P (∞)]M

• Le régime permanent s’instaure dans les chaı̂nes irréductibles apériodiques.

• Dans le cas de chaı̂nes réductibles, on parle de la probabilité d’absorption
par une classe finale3 .
3 Car à l’infini, on peut se retrouver dans la classe finale pendant une infinité de temps. S’il

y’a plusieurs classes finales, on ne sait pas dans quelle classe on va retrouver le système.

4
 • Dans le cas de chaı̂nes irréductibles périodiques, on parle du calcul de
périodicité dans l’infini (Comme la suite d’états se répète, on parle de la
portion de temps ou le système peut se trouver dans un état particulier)4 .

6 Matrices T , R, Q, N et t̄
Pour une chaı̂ne de Markov avec une ou plusieurs classes finales :
• La matrice T est la sous-matrice de M correspondant aux transitions entre
les états transitoires.

• La matrice R contient les probabilités de transition des états transitoires

vers les états finaux.
• La matrice Q comporte le calcul des probabilités d’absorption par les
classes finales en démarrant de n’importe quel état.
• La matrice N comporte le temps moyen de séjour entre un état i et un
état j dans sa composante (i, j).
• La matrice t̄ comporte le temps moyen de séjour en démarrant d’un état
transitoire i avant d’être absorbé.
• on peut obtenir les éléments du t̄ en calculant, indépendemment, les durées
moyennes de séjour avant absorption par chaque classe finale, puis calculer
une moyenne pondérée avec les lignes de la matrice Q.
Pour calculer Q et N :
Q = (I − T )−1 R
N = (I − T )−1
t̄ = (I − T )−1 U
Où I est la matrice identité appropriée et U est le vecteur colonne unitaire5 .

4 Si à l’infini, le système fait l’enchaı̂nement abacabacabac.., on constate que abac est une

période, et on retrouve le système dans a deux fois plus que dans b et c.

5 U est un vecteur unitaire car il correspond aux pas unitaires dans le cas discret. Or, dans

le cas continue, on utilise les temps moyen de séjour dans chaque état

5
7 Distributions de probabilité
Soit X une variable aléatoire suivant une distribution de probabilité.

7.1 Fonction de densité

Pour les distributions continues, la fonction f (x) donne la densité de probabilité
en tout point.
dF (x)
f (x) =
dx
où F (x) est la fonction de répartition.

7.2 Moments
Moment d’ordre 1 (espérance) :
Z ∞
E(X) = µ = xf (x)dx
−∞

Moment d’ordre 2 (variance) :

V ar(X) = E[(X − µ)2 ] = σ 2

8 Chaı̂nes de Markov continues

Soit X(t) une chaı̂ne de Markov continue, à valeurs dans R, de générateur G.

8.1 Matrice génératrice

 
−q1 q12 ··· q1n
 q21 −q2 ··· q2n 
G= . (1)
 
.. .. .. 
 .. . . . 
qn1 qn2 ··· −qn
où qij ≥ 0 pour i ̸= j.

8.2 Saut markovien

• Le temps avant transition hors de l’état i (i.e., le temps de séjour dans
l’état i) suit une loi exponentielle de paramètre qi 6 .
• Le prochain état est choisi selon les probabilités de transitions parmi les
différents états positives du générateur (i.e., les transitions seront pondérés
qij
avec des probabilité ).
qi
6 i.e., le temps est aléatoire, mais il y’a des temps qui ont plus de probabilité de s’afficher

par rapport aux autres. On peut savoir quel temps est plus probable qu’un autre grâce à
la fonction de densité de la distribution de probabilité choisie, qui est dans ce cas ”la loi
exponentielle”

6
8.3 Valeurs diagonales
Les valeurs diagonales −qi de la matrice génératrice G représentent le taux de
sortie de l’état i:
n
X
qi = qij (2)
j=1,j̸=i

Ce taux caractérise la loi exponentielle régissant le temps avant transition

hors de l’état i.

8.4 Distribution exponentielle

La distribution exponentielle modélise le temps passé dans un état.
Si X ∼ EXP (λ) alors:

Moyenne:
1
E(X) = (3)
λ
Variance:
1
V ar(X) = (4)
λ2
Dans notre cas λ = qi est le taux de sortie de l’état, donné par la diagonale
de G.
Ces mesures décrivent complètement le comportement du temps de séjour
dans un état de la chaı̂ne de Markov.

7
Figure 1: Fonction de densité - Loi Exponentielle

Figure 2: Fonction de densité - Loi Exponentielle