C HAÎNES DE M ARKOV.

Alexandre Popier

ENSAI, Bruz

apopier@[Link]

[Link]

Janvier-Mars 2011

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 1 / 51

P LAN

1 I NTRODUCTION

2 D ÉFINITIONS

3 C LASSIFICATION DES ÉTATS

4 C AS PARTICULIER : ESPACE D ’ ÉTATS E FINI

5 C HAÎNES DE M ARKOV IRRÉDUCTIBLES RÉCURRENTES

6 C HAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET
APÉRIODIQUES

7 C HAÎNES SIMPLEMENT IRRÉDUCTIBLES

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 2 / 51

S UITES RÉCURRENTES ALÉATOIRES .

D ÉFINITION
Une suite récurrente aléatoire sur un espace E est une suite de v.a.
(Xn )n∈N à valeurs dans E définie sur un espace de probabilité (Ω, F, P)
solution d’une équation récurrente de la forme :

Xn+1 = f (θn+1 , Xn )

où
1 θ1 , θ2 , . . . sont des v.a. i.i.d. à valeurs dans Θ ;
2 f : Θ × E → E est une application mesurable ;
3 X0 (la condition initiale) est une v.a. (éventuellement déterministe)
indépendante de la suite (θi )i∈N∗ .

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 3 / 51

BATTRE LES CARTES .

I E : ensemble des permutations (d’un jeu de 52 cartes), de

cardinal 52! ;
I Θ : un sous-ensemble de E ;
I X0 = e : identité (les cartes sont ordonnées), Xn+1 = θn+1 ◦ Xn .
H YPOTHÈSES :
Θ est mélangeant, i.e. engendre E ;
la loi des θi charge tous les éléments de Θ.

T HÉORÈME
La suite (Xn ) est récurrente, satisfait une loi des grands nombres :
n
1X 1
lim 1Xk =x = .
n→+∞ n 52!
k =1

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 4 / 51

BATTRE LES CARTES : COMBIEN DE FOIS ?

T HÉORÈME
La suite (Xn ) est récurrente, satisfait une loi des grands nombres :
n
1X 1
lim 1Xk =x = .
n→+∞ n 52!
k =1

I On a une asymptote de type exponentiel (condition de Doeblin) :

1X 1
P(Xn = x) − ≤ Cρn , avec ρ < 1.
2 52!
x∈E

I Diaconis a montré qu’il suffit de battre le jeu 7 fois !

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 5 / 51

M ARCHES ALÉATOIRES SUR Zd .
I e1 , . . . , ed : base canonique de Rd ;
I E = Zd ;
I Θ = {−e1 , . . . , −ed , e1 , . . . , ed } ; θi de loi uniforme sur Θ ;
I X0 = 0, Xn+1 = Xn + θn+1 : marche aléatoire symétrique sur Zd .

T HÉORÈME (P OLYA , 1921)

Pour d = 1 ou 2, la marche aléatoire (Xn ) est récurrente :

P(∃n > 0, Xn = 0) = 1.
Pour d ≥ 3, elle est transiente : P(∃n > 0, Xn = 0) < 1.

C ONSTANTE DE P OLYA
C’est p(d) = P(T0 < +∞), T0 étant le temps de retour à 0. Alors
p(1) = p(2) = 1, p(3) ≈ 0, 34, p(4) ≈ 0, 19, p(10) ≈ 0, 06.
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 6 / 51
M ARCHE ALÉATOIRE EN DIMENSION 1.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 7 / 51

M ARCHE ALÉATOIRE EN DIMENSION 2.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 8 / 51

C ONVOLUTION DE B ERNOULLI .
I a > 0;
I E = R;
I Θ = {−1, 1} ; θi de loi uniforme sur Θ ;
I X0 = 0, Xn+1 = aXn + θn+1 .

Pour a = 1, marche aléatoire sur Z.

Pour a > 1, P(limn→+∞ Xn ∈ {−∞, +∞}) = 1.
Pour 0 < a < 1 ?

I Xn − an X0 = an−1 θ1 + . . . + θn .
h i
1 1
I Yn = θ1 + aθ2 + . . . + an−1 θn converge vers Y∞ ∈ − 1−a , 1−a .

P ROPOSITION
(Xn ) converge en loi vers Y∞ : lim EΦ(Xn ) = EΦ(Y∞ ).
n→+∞

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 9 / 51

a = 0, 25.

Comportement p.s. de Xn et Yn :

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 10 / 51

a = 0, 25.

Comportement en loi de X100 et Y100 :

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 10 / 51

a = 0, 7.

Comportement p.s. de Xn et Yn :

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 11 / 51

a = 0, 7.

Comportement en loi de X100 et Y100 :

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 11 / 51

C ONVOLUTION DE B ERNOULLI : LOI DE LA LIMITE .
I Fa (t) = νa (] − ∞, t]) = P(Y∞ ≤ t).

P ROPOSITION
n−1
1X
Pour tout I = [α, β] ⊂ R, lim 1Xk ∈I = Fa (β) − Fa (α).
n→+∞ n
k =0

P ROPRIÉTÉS DE Fa
Fa est l’unique solution continue de
    
1 t −1 t +1
∀t ∈ R, G(t) = G +G .
2 a a

Si a < 1/2, νa est continue singulière (1935).

Si a = 1/2, νa est la loi uniforme sur [−2, 2] (1935).
Pour presque tout a > 1/2, νa est à densité (1995).
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 12 / 51
S IMULATIONS DE FRACTALES .
I E = Rd ;
I Θ = {1, . . . , k } ; θi de loi uniforme sur Θ ;
I X0 = 0, Xn+1 = A(θn+1 )Xn + B(θn+1 ).
I A(1), . . . , A(k ) matrices, B(1), . . . , B(k ) vecteurs.

T HÉORÈME
Les conclusions de la convolution de Bernoulli restent les mêmes :
convergence en loi de (Xn ), théorème de convergence presque sûre
des moyennes de Césaro.

S PIRALE
d = k = 2;
   
0, 839 −0, 303 −0, 161 −0, 136
A(1) = , A(2) = ;
0, 383 0, 924 0, 138 −0, 182
   
0, 232 0, 921
B(1) = , B(2) = .
−0, 080 0, 178
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 13 / 51
F RACTAL EN SPIRALE .

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 14 / 51

P LAN

1 I NTRODUCTION

2 D ÉFINITIONS

3 C LASSIFICATION DES ÉTATS

4 C AS PARTICULIER : ESPACE D ’ ÉTATS E FINI

5 C HAÎNES DE M ARKOV IRRÉDUCTIBLES RÉCURRENTES

6 C HAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET
APÉRIODIQUES

7 C HAÎNES SIMPLEMENT IRRÉDUCTIBLES

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 15 / 51

M ATRICES DE TRANSITION .

D ÉFINITION (E SPACE D ’ ÉTATS , MESURE )

DANS TOUT LE COURS, E est un espace dénombrable. Un élément
x ∈ E est un état. Une mesure ν =X (νx , x ∈ E) est un vecteur ligne de
nombres réels positifs ou nuls. Si νx = 1, la mesure est une
x∈E
probabilité ou distribution.

D ÉFINITION (M ATRICE DE TRANSITION )

Une matrice de transition P sur E est une application de E × E dans
[0, 1] telle que X
∀x ∈ E, P(x, y ) = 1.
y ∈E

On dit aussi que la matrice est stochastique.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 16 / 51

C HAÎNE DE M ARKOV

D ÉFINITION (C HAÎNE DE M ARKOV )

Une suite de v.a. (Xn )n∈N à valeurs dans E est appelée chaîne de
Markov si pour tout n ∈ N la loi conditionnelle de Xn+1 sachant
X0 , . . . , Xn est égale à sa loi conditionnelle sachant Xn , i.e. pour tout
y0 , . . . , yn+1 dans E :

P(Xn+1 = yn+1 |X0 = y0 , . . . , Xn = yn ) = P(Xn+1 = yn+1 |Xn = yn ).

I Pn (x, y ) = P(Xn+1 = y |Xn = x).

D ÉFINITION
Si Pn (x, y ) = P(Xn+1 = y |Xn = x) ne dépend pas de n, on parle de
chaîne de Markov homogène. Dans ce cas, la matrice P obtenue est
stochastique.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 17 / 51

D ÉFINITION « ÉQUIVALENTE »

D ÉFINITION (C HAÎNE DE M ARKOV (ν, P))

Une chaîne de Markov, de distribution initiale ν et matrice de transition
P, à valeurs dans E est une suite de v.a. (Xn )n∈N définies sur
(Ω, F, P), telle que :
1 X0 a pour loi ν,
2 et pour n ≥ 0, conditionnellement à Xn = x, la loi de Xn+1 est
donnée par (P(x, y ), y ∈ E) et est indépendante de X0 , . . . , Xn−1 .

T RADUCTION MATHÉMATIQUE
Pour tout n ≥ 0 et tout y0 , . . . , yn+1 dans E :
1 P(X0 = y0 ) = ν0 ;
2 P(Xn+1 = yn+1 |X0 = y0 , . . . , Xn = yn ) = P(yn , yn+1 ).

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 18 / 51

E XEMPLE IMPORTANT

P ROPOSITION
Soit
(θn )n∈N une suite de v.a. i.i.d. à valeurs dans Θ,
X0 une v.a. à valeurs dans E, indépendante de la suite (θn )n∈N ,
f : Θ × E → E une fonction mesurable.
Alors la suite (Xn )n∈N de v.a. à valeurs dans E et définie par la relation
de récurrence :
∀n ∈ N, Xn+1 = f (θn+1 , Xn )
est une chaîne de Markov homogène.

C ONSÉQUENCES : tous les suites vues dans la partie 1 sont des

chaînes de Markov.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 19 / 51

É QUATION DE C HAPMAN -KOLMOGOROV

T HÉORÈME
Soit (Xn ) une chaîne de Markov sur E de matrice de transition P, de
distribution initiale ν. Alors

P(X0 = y0 , . . . , Xn = yn ) = ν(y0 )P(y0 , y1 ) . . . P(yn−1 , yn ).

1 Si Xn a pour loi µn , alors : µn+1 = µn P = νP n+1 .

2 Pour tout (x, y ) ∈ E 2 , P(Xn = y |X0 = x) = P n (x, y ).
3 Pour toute fonction h : E → R bornée,

E(h(Xn )|X0 = x) = P n h(x).

R EMARQUE
Les fonctions h : E → R sont représentées par des vecteurs colonnes.
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 20 / 51
M ESURE INVARIANTE , RÉVERSIBLE

D ÉFINITION (M ESURE INVARIANTE )

Une mesure µ sur E est dite invariante si et seulement si c’est un point
fixe de l’équation Chapman-Kolmogorov, i.e. µ = µP.

D ÉFINITION (M ESURE RÉVERSIBLE )

Une mesure µ sur E est dite réversible si et seulement si

∀(x, y ) ∈ E 2 , µ(x)P(x, y ) = µ(y )P(y , x).

P ROPOSITION
Une mesure réversible est invariante.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 21 / 51

C HAÎNE RETOURNÉE .

L EMME
Si (Xn )n∈N est une chaîne de Markov, alors pour tout N ∈ N,
n o
X̂ N = X̂nN = XN−n , 0 ≤ n ≤ N

est une chaîne de Markov, appelée chaîne retournée à partir de

l’instant N.

P ROPOSITION
Soit (Xn )n∈N chaîne de Markov (µ, P) avec µ probabilité réversible.
Alors la chaîne retournée X̂ N = {X̂nN , 0 ≤ n ≤ N} est une chaîne de
Markov (µ, P).

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 22 / 51

P ROPRIÉTÉ DE M ARKOV.

D ÉFINITION
Le processus décalé Xn+ = (Xn+,k )k ∈N est défini par

∀k ≥ 0, Xn+,k = Xn+k .

T HÉORÈME
Soit (Xn ) une chaîne de Markov sur E de matrice de transition P, de
distribution initiale ν. Alors conditionnellement à Xn = x, le processus
Xn+ est une chaîne de Markov de matrice de transition P, de
distribution initiale δx et est indépendant des v.a. X0 , . . . , Xn .

I Phénomène sans mémoire !

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 23 / 51

P ROPRIÉTÉ DE M ARKOV FORTE .
Pour n ≥ 0, Fn : tribu des événements déterminés par X0 , X1 , . . . , Xn
n o
Fn = {ω ∈ Ω; (X0 (ω), . . . , Xn (ω)) ∈ Bn }, Bn ∈ P(E n+1 ) .

D ÉFINITION (T EMPS D ’ ARRÊT )

Une v.a. τ à valeurs dans N ∪ {+∞} est appelée un temps d’arrêt si
pour tout n ∈ N, {τ = n} ∈ Fn .

P ROPRIÉTÉ DE M ARKOV FORTE

Soit (Xn ) une chaîne de Markov (ν, P) et τ un temps d’arrêt. Alors
conditionnellement en {τ < +∞} ∩ {Xτ = x}, le processus (Xτ +n )n∈N
est une chaîne de Markov (δx , P) indépendante de Fτ : pour tout
A ∈ Fτ , m > 0, x1 , . . . , xm dans E :

P(A ∩ {Xτ +1 = x1 , . . . , Xτ +m = xm }|Xτ = x, τ < ∞)

= P(A|Xτ = x, τ < ∞) × Px (X1 = x1 , . . . , Xm = xm ).
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 24 / 51
N OTATIONS POUR LA SUITE DU COURS .

I E : espace fini ou dénombrable ;

I P : matrice de transition ;
I Pν loi sachant que X0 suit la loi ν ;
I Eν : espérance sous Pν ;
I Px loi sachant que X0 = x, i.e. ν = δx
I Ex : espérance sous Px ;
I Π(E) : ensemble des probabilités sur E.

L EMME
( )
X
Π(E) = µ ∈ RE , µ(x) ≥ 0, µ(x) = 1 .
x∈E

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 25 / 51

P LAN

1 I NTRODUCTION

2 D ÉFINITIONS

3 C LASSIFICATION DES ÉTATS

4 C AS PARTICULIER : ESPACE D ’ ÉTATS E FINI

5 C HAÎNES DE M ARKOV IRRÉDUCTIBLES RÉCURRENTES

6 C HAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET
APÉRIODIQUES

7 C HAÎNES SIMPLEMENT IRRÉDUCTIBLES

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 26 / 51

É TATS RÉCURRENTS ET TRANSITOIRES .
T EMPS DE RETOUR : Tx = inf{n ≥ 1, Xn = x}.

D ÉFINITION
L’état x ∈ E est récurrent si Px (Tx < +∞) = 1, et est transitoire si
Px (Tx < +∞) < 1.
X
N OMBRE DE RETOURS : Nx = 1Xn =x .
n≥1

P ROPOSITION
1 Si x est récurrent, Px (Nx = +∞) = 1.
2 Si x est transitoire,

Px (Nx = k ) = (1 − Πx )Πkx , pour k ≥ 0,

avec Πx = Px (Tx < +∞).

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 27 / 51

É TATS RÉCURRENTS ET TRANSITOIRES .
X
N OMBRE DE RETOURS : Nx = 1Xn =x .
n≥1

P ROPOSITION
1 Si x est récurrent, Px (Nx = +∞) = 1.
2 Si x est transitoire,

Px (Nx = k ) = (1 − Πx )Πkx , pour k ≥ 0,

avec Πx = Px (Tx < +∞).

C OROLLAIRE
L’état x ∈ E est récurrent si et seulement si
+∞
X
(P n )(x, x) = +∞.
n=0

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 27 / 51

C LASSE D ’ ÉQUIVALENCE .

D ÉFINITION
L’état y ∈ E est accessible à partir de x ∈ E (noté x → y ) s’il
existe n ∈ N tel que Px (Xn = y ) > 0.
Les états x et y communiquent (noté x ↔ y ) si x → y et y → x.

C LASSES D ’ ÉQUIVALENCE : ↔ est une relation d’équivalence qui crée

une partition de E en classes d’équivalence modulo ↔.

T HÉORÈME
Soit C ⊂ E une classe d’équivalence modulo ↔. Alors tous les états
de C sont soit récurrents, soit transitoires.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 28 / 51

C LASSES FERMÉES .

D ÉFINITION
Une classe C ⊂ E est dite fermée si pour tous x et y dans E :

x ∈ C et x → y ⇒ y ∈ C.

P ROPOSITION
La restriction de la chaîne de Markov à une classe fermée C est une
chaîne de Markov d’espace d’états C.

Si C = {x0 } est fermée, on dit que x0 est un état absorbant.

T HÉORÈME
Toute classe récurrente est fermée.
Toute classe fermée et finie est récurrente.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 29 / 51

I RRÉDUCTIBILITÉ .

D ÉFINITION
Une chaîne de Markov (ν, P) est
I irréductible si E est constitué d’une seule classe d’équivalence ;
I irréductible récurrente si elle est irréductible et si tous les états
sont récurrents.
I irréductible transiente si elle est irréductible et si tous les états
sont transitoires.

P ROPOSITION
Une chaîne de Markov irréductible sur un espace E fini est irréductible
récurrente.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 30 / 51

I RRÉDUCTIBILITÉ .
D ÉFINITION
Une chaîne de Markov (ν, P) est irréductible si, pour tout couple
(x, y ) ∈ E 2 , il existe
un entier k = k (x, y )
et une suite finie x = x0 , x1 , . . . , xk −1 , xk = y
tels que P(xi , xi+1 ) > 0 pour i = 0, . . . , k − 1.

C’est-à-dire : P(Xk = y |X0 = x) = P k (x, y ) > 0.

T HÉORÈME
Si (Xn )n∈N est irréductible,
1 les fonctions P-invariantes (i.e. Pf = f ) sont les fonctions
constantes.
2 P admet au plus une probabilité invariante π. De plus π(x) > 0
pour tout x ∈ E.
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 31 / 51
C LASSIFICATION .
1 x 6→ x : x transitoire.

2 Les états x t.q. x → x peuvent être classés en classes

d’équivalence irréductibles par la relation ↔ :
I classes irréductibles non fermées : transitoires ;
I classes irréductibles fermées : récurrentes ou transitoires.

3 À partir d’un état récurrent,

I la chaîne restreinte à la classe d’équivalence de cet état est
irréductible.
I Chaque état de cette classe est visité une infinité de fois.

4 À partir d’un état transitoire,

I soit la chaîne finit par atteindre une des classes récurrentes ;
I soit elle part à l’infini après être passée un nombre fini de fois par
les états de la classe transitoire.
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 32 / 51
P LAN

1 I NTRODUCTION

2 D ÉFINITIONS

3 C LASSIFICATION DES ÉTATS

4 C AS PARTICULIER : ESPACE D ’ ÉTATS E FINI

5 C HAÎNES DE M ARKOV IRRÉDUCTIBLES RÉCURRENTES

6 C HAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET
APÉRIODIQUES

7 C HAÎNES SIMPLEMENT IRRÉDUCTIBLES

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 33 / 51

E XISTENCE D ’ UNE MESURE INVARIANTE .

DANS CE PARAGRAPHE ,
I E : espace fini de cardinal d, donc en bijection avec {1, . . . , d} ;
I P : matrice de transition de taille d × d ;
I Π(E) : ensemble des probabilités sur E.

T HÉORÈME
L’ensemble des probabilités invariantes pour P est un sous-ensemble
non vide, compact et convexe de Π(E).

R EMARQUE
Pas d’unicité en général !

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 34 / 51

T HÉORÈME ERGODIQUE .
T HÉORÈME
Supposons (Xn )n∈N irréductible de probabilité invariante π. Alors
1 presque sûrement
n−1
1X
lim 1Xk =x = π(x).
n→+∞ n
k =0

2 Pour tout x ∈ E,
1
π(x) = > 0,
Ex (Tx )
avec Tx = inf{k ≥ 1, Xk = x} instant de premier retour en x.

C OROLLAIRE
Si la chaîne est irréductible, alors elle visite infiniment souvent tous les
points de l’espace d’états E.
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 35 / 51
C HAÎNE FORTEMENT IRRÉDUCTIBLE .

P ROPOSITION
Supposons la chaîne irréductible de probabilité invariante π. Alors pour
toute probabilité ν sur E,
n−1
X n−1
X
k
lim νP = π, ou encore lim Pν (Xk = x) = π(x).
n→+∞ n→+∞
k =0 k =0

D ÉFINITION
Une chaîne de Markov (ν, P) est fortement irréductible s’il existe un
entier k tel que
∀(x, y ) ∈ E 2 , P k (x, y ) > 0.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 36 / 51

C HAÎNE FORTEMENT IRRÉDUCTIBLE .

T HÉORÈME
Supposons (Xn )n∈N fortement irréductible de probabilité invariante π.
Soit k l’entier de la définition précédente et
X 
k
α = α(P) = inf P (x, y ) > 0.
x∈E
y ∈E

Alors pour toute probabilité ν sur E et tout n ∈ N,

sup |Pν (Xn ∈ A) − π(A)| ≤ (1 − α)[n/k ] ,

A⊂E

avec [a] la partie entière de a. Ainsi lim νP n = π.

n→+∞

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 36 / 51

A PÉRIODICITÉ (1).
D ÉFINITION
Soit x ∈ E et R(x) = {n ∈ N∗ , P n (x, x) > 0}. La période p(x) de x est
le plus grand commun diviseur de R(x).

P ROPOSITION
Supposons la chaîne irréductible. Alors tous les points de E ont la
même période.

D ÉFINITION
Cette période commune est la période de la chaîne ; chaîne qui est
apériodique si cette période vaut 1.

C OROLLAIRE
Supposons P irréductible. S’il existe x ∈ E tel que P(x, x) > 0, alors P
est apériodique.
A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 37 / 51
A PÉRIODICITÉ (2).

D ÉFINITION
Un état est apériodique s’il existe un entier N tel que P n (x, x) > 0 pour
tout n ≥ N.

T HÉORÈME
1 Si une chaîne est irréductible et apériodique, tous les états sont
apériodiques. Et alors la chaîne est fortement irréductible.
2 Réciproquement une chaîne fortement irréductible est irréductible
et apériodique.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 38 / 51

P LAN

1 I NTRODUCTION

2 D ÉFINITIONS

3 C LASSIFICATION DES ÉTATS

4 C AS PARTICULIER : ESPACE D ’ ÉTATS E FINI

5 C HAÎNES DE M ARKOV IRRÉDUCTIBLES RÉCURRENTES

6 C HAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET
APÉRIODIQUES

7 C HAÎNES SIMPLEMENT IRRÉDUCTIBLES

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 39 / 51

M ESURES INVARIANTES .

ATTENTION :
A partir d’ici, E n’est plus supposé fini.

D ÉFINITION
Une mesure π est strictement positive si π(x) > 0 pour tout x ∈ E.

T HÉORÈME
Soit (Xn )n∈N une chaîne de Markov de matrice de transition P,
irréductible récurrente. Alors il existe une mesure π strictement
positive invariante, unique à constante multiplicative près.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 40 / 51

PARMI LES ÉTATS RÉCURRENTS ...

x récurrent si Px (Tx < +∞) = 1.

m(x) = Ex (Tx ).

D ÉFINITION
Un état x est récurrent positif si m(x) < +∞, et récurrent nul sinon.

T HÉORÈME
Supposons la chaîne irréductible.
I Un état x est récurrent positif,
I si et seulement si tous les états sont récurrents positifs,
I si et seulement s’il existe une unique probabilité invariante.
Dans ce cas elle est donnée par π = (π(x) = 1/m(x), x ∈ E).

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 41 / 51

D ICHOTOMIE .

Pour une chaîne irréductible et récurrente

I soit elle est récurrente positive s’il existe une probabilité invariante,
I soit elle est récurrente nulle
X si toute mesure invariante est de
masse totale infinie, i.e. πx = +∞.
x∈E
C ONSÉQUENCE : si E est fini, il n’existe pas d’état récurrent nul, tout
état récurrent est récurrent positif.
C OROLLAIRE
Soit (Xn )n∈N une chaîne de Markov irréductible, récurrente positive.
Pour x ∈ E, Tx = inf{n ≥ 1, Xn = x}. Alors pour tout y ∈ E,

Ey (Tx ) < +∞.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 42 / 51

T HÉORÈME ERGODIQUE .

G ÉNÉRALISATION de la loi des grands nombres :

T HÉORÈME
Soit (Xn )n∈N une chaîne irréductible et récurrente positive. Si
f : E → R est une fonction bornée, alors
n−1
!
1X X
P lim f (Xk ) = π(x)f (x) = 1.
n→+∞ n
k =0 x∈E

π = (π(x), x ∈ E) est l’unique probabilité invariante.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 43 / 51

T HÉORÈME CENTRAL LIMITE .

T HÉORÈME
Soient
(Xn )n∈N chaîne irréductible de matrice de transition P,
π l’unique probablité invariante,
X
f : E → R avec πf = πx fx = 0.
x∈E
n−1
1 X
Alors il existe σf ≥ 0 tel que la suite √ f (Xk ) converge en loi vers
n k =0
σf Z , avec Z ∼ N (0, 1).

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 44 / 51

T HÉORÈME CENTRAL LIMITE .

C ALCUL DE σf : pour i ∈ E,
+∞
X
(Qf )x = Ex (f (Xn )).
n=0

Alors (I − P)Qf = f et
X X
σf2 = πx ((Qf )x )2 − πx (PQf )2x
x∈E x∈E
X X
= 2 πx (Qf )x fx − πx fx2 .
x∈E x∈E

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 44 / 51

P LAN

1 I NTRODUCTION

2 D ÉFINITIONS

3 C LASSIFICATION DES ÉTATS

4 C AS PARTICULIER : ESPACE D ’ ÉTATS E FINI

5 C HAÎNES DE M ARKOV IRRÉDUCTIBLES RÉCURRENTES

6 C HAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET
APÉRIODIQUES

7 C HAÎNES SIMPLEMENT IRRÉDUCTIBLES

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 45 / 51

A PÉRIODICITÉ .
D ÉFINITION
Un état x est apériodique s’il existe N ∈ N tel que (P n )(x, x) > 0 pour
tout n ≥ N.

L EMME
Si P est irréductible et s’il existe un état apériodique x, alors pour tout
(y , z) ∈ E 2 , il existe M ∈ N tel que (P n )(y , z) > 0 pour n ≥ M. En
particulier tous les états sont apériodiques.

T HÉORÈME
Soient P une matrice irréductible, récurrente positive et apériodique et
π l’unique probabilité invariante. Soit (Xn )n∈N une chaîne de Markov
(ν, P). Alors pour tout x ∈ E,

lim P(Xn = x) = πx ⇔ lim (νP n )x = πx .

n→+∞ n→+∞

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 46 / 51

V ITESSE DE CONVERGENCE .
Pour tout (x, y ) ∈ E 2 , lim (P n )(x, y ) = πy .
n→+∞
C ONDITION DE D OEBLIN : il existe une mesure non nulle µ sur E et
n0 ∈ N tels que :

∀(x, y ) ∈ E 2 , (P n0 )(x, y ) ≥ µy .
X
N OTATION : β = µx .
x∈E
I Si E est fini :
L EMME
Soit P irréductible et apériodique. La condition de Doeblin est
satisfaite.
I Quand E est infini, en général pour tout n ∈ N et tout y ∈ E,
inf (P n )(x, y ) = 0.
x∈E

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 47 / 51

C ONVERGENCE EXPONENTIELLE .

T HÉORÈME
Supposons P irréductible et vérifiant la condition de Doeblin. Alors P
est récurrente positive et apériodique, et si π désigne sa probabilité
invariante, pour tout i ∈ E et n ∈ N :
X
|(P n )(x, y ) − πy | ≤ 2(1 − β)[n/n0 ] .
y ∈E

Pour α ∈ R, [α] est la partie entière de α.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 48 / 51

P LAN

1 I NTRODUCTION

2 D ÉFINITIONS

3 C LASSIFICATION DES ÉTATS

4 C AS PARTICULIER : ESPACE D ’ ÉTATS E FINI

5 C HAÎNES DE M ARKOV IRRÉDUCTIBLES RÉCURRENTES

6 C HAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET
APÉRIODIQUES

7 C HAÎNES SIMPLEMENT IRRÉDUCTIBLES

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 49 / 51

PARTITION DE E .
Ici la chaîne peut être périodique ou transiente ou récurrente nulle.

T HÉORÈME
Soit P irréductible. Il existe un entier d ≥ 1 et une partition

E = C0 ∪ C1 ∪ . . . ∪ Cd−1

tels que (en posant Cnd+r = Cr ) :

n > 0 seulement si x ∈ C et y ∈ C
Pxy r r +n pour un certain r ;
(nd)
Pxy > 0 pour tout n suffisamment grand, et tout x et y dans Cr
pour tout r .

D ÉFINITION
L’entier d s’appelle la période. Pour tout x ∈ E, d est le plus grand
diviseur commun de l’ensemble {n ≥ 0, Pxx n > 0}.

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 50 / 51

C OMPORTEMENT EN TEMPS LONG .

T HÉORÈME
Soit P irréductible de période d et E = C0 ∪ C1 ∪ . . . ∪ Cd−1
X la partition
du théorème précédent. Soit ν une probabilité sur E t.q. ν(x) = 1.
x∈C0
Soit X la chaîne de Markov (ν, P). Alors pour r = 0, 1, . . . , d − 1 et
pour y ∈ Cr , on a :

d
P(Xnd+r = y ) −→ ,
n→+∞ my

où my est le temps de retour moyen en y . En particulier pour x ∈ C0 et

y ∈ Cr , on a
(nd+r ) d
Pxy −→ .
n→+∞ my

A. Popier (ENSAI) Chaînes de Markov. Janvier-Mars 2011 51 / 51