Chaînes de Markov - IECL | Institut Élie Cartan de … · Plan 1 Déﬁnitionetexemples 2 PropriétésdeMarkov Tempsd’arrêt PropriétésdeMarkov 3 Classiﬁcationdesétats 4

Chaînes de Markov

Samy Tindel

Université de Lorraine

Master 1 - Nancy

Samy T. (IECL) M1 - Chaînes de Markov Université de Lorraine 1 / 78

Plan

1 Définition et exemples

2 Propriétés de MarkovTemps d’arrêtPropriétés de Markov

3 Classification des états

4 Théorème ergodique

5 Absorption


Plan





5 Absorption


Processus à temps discret

Espace de probabilités: (Ω,F ,P).

Espace d’état: E dénombrable (E = N,Z,Zd etc)

Processus: suite de variables aléatoires Xn; n ≥ 0 à valeurs dans E .

Processus et v.a.: On aPour tout n ≥ 0, Xn : (Ω,F)→ (E ,P(E )) variable aléatoire.X : Ω→ EN variable aléatoire.


Chaîne de Markov

DéfinitionSoit X = Xn; n ≥ 0 processus.

1 X est une chaîne de Markov si

P (Xn+1 = j |X0 = i0, . . . ,Xn = in) = P (Xn+1 = j |Xn = in)

pour tout n ≥ 0, i0, . . . , in, j ∈ E.2 La chaîne de Markov est homogène si on a de plus

P (Xn+1 = j |Xn = i) = P (X1 = j |X0 = i)


FiltrationFiltration naturelle: on pose pour n ≥ 0

Fn = σ(X0, . . . ,Xn).

La filtration (Fn)n≥0 se nomme filtration naturelle associée à X .

Définition alternative de chaîne de Markov: Pout tout n ≥ 0 et j ∈ E ,

P (Xn+1 = j | Fn) = P (Xn+1 = j |Xn)

ou encore, pour une chaîne homogène:

L (Xn+1| Fn) = p(Xn, ·)

au sens des lois conditionnelles régulières.


Marche aléatoireDéfinition: SoientZi ; i ≥ 1 v.a. indépendantes de Rademacher→ P(Zi = −1) = P(Zi = 1) = 1/2On pose X0 = 0, et pour n ≥ 1,

Xn =n∑

i=1Zi .

X est appelée marche aléatoire dans Z.

Propriété: X est une chaîne de Markov et

P (Xn+1 = j |Xn = i) =12δi+1(j) +

12δi−1(j).


Chaîne homogène

PropositionSoit (Xn)n≥0 chaîne de MarkovAlors (Xn)n≥0 homogène ssi il existe p : E × E → [0, 1] telle que

P (Xn+1 = j |X0 = i0, . . . ,Xn = in) = p(in, j)

pour tout n + 2-uplé (i0, . . . , in, j) ∈ E

Enoncé alternatif de la proposition: Soit (Xn)n≥0 chaîne de MarkovAlors (Xn)n≥0 homogène ssi il existe p : E × E → [0, 1] telle que

P (Xn+1 = j | Fn) = p(Xn, j)

pour tout n ≥ 0 et j ∈ E (lien avec les lois conditionnelles régulières).


Notations

Soit X une chaîne de Markov homogène. On note:

Loi initiale: ν0 = L(X0) ou encore ν0(i) = P(X0 = i), i ∈ E

Probabilité de transition: p(i , j) = P(X1 = j |X0 = i), i , j ∈ E

Matrice de transition: p = (p(i , j))i ,j∈E

Loi à l’instant k : νk = L(Xk) ou encore νk(i) = P(Xk = i), i ∈ E


Propriété des matrices de transition

PropositionSoit X chaîne de Markov de matrice de transition p.Alors p vérifie

1 Pour tout i , j ∈ E, on a p(i , j) ∈ [0, 1]

2 Pour tout i ∈ E, on a ∑j∈E p(i , j) = 1.On dit que p est une matrice stochastique.

Démonstration:(1) p(i , j) = P(X1 = j |X0 = i) ∈ [0, 1].(2) ∑j∈E p(i , j) =

∑j∈E P(X1 = j |X0 = i) = 1.


Exemple: marche aléatoire

Rappel: Soit X la marche aléatoire. On a vu: X0 = 0 et

P (Xn+1 = j |Xn = i) =12δi+1(j) +

12δi−1(j).

Donc1 ν0 = δ02 p(i , j) = 1

2δi+1(j) + 12δi−1(j).


Exemple: temps à Nancy

Modèle: on choisit E = 1, . . . , 6 := TM,M,AM,AB,B,TB.

Proba de transition: par observation statistique, on a trouvé

0 1 0 0 0 00.4 0.6 0 0 0 00.3 0 0.4 0.2 0.1 00 0 0 0.3 0.7 00 0 0 0.5 0 0.50 0 0 0.8 0 0.2


Loi de la chaîne et p

PropositionSoit X chaîne de Markov homogène, de loi initiale ν et transition p.

1 Pour n ∈ N et i0, . . . , in ∈ E,

P (X0 = i0, . . . ,Xn = in) = ν(i0) p(i0, i1) · · · p(in−1, in)

2 La loi de X est caractérisée par ν et p.


Démonstration

(1) par récurrence: Cas n = 0 trivial.Si on suppose (1) vrai à l’ordre n, alors

P (X0 = i0, . . . ,Xn = in,Xn+1 = in+1)

= P (Xn+1 = in+1|X0 = i0, . . . ,Xn = in, ) P (X0 = i0, . . . ,Xn = in)

= p(in, in+1)× ν(i0) p(i0, i1) · · · p(in−1, in)

= ν(i0) p(i0, i1) · · · p(in, in+1).

(2): Il faut montrer que les lois fini-dimensionnellesengendrent une loi sur (EN,P(E )⊗N)→ Théorème de Kolmogorov.


Loi de la chaîne et produits de matrice

PropositionSoit X CHMH, de loi initiale ν et transition p. Alors

νn(i) = [ν pn] (i).

Démonstration:

νn(i) = P(Xn = i)=

∑i0,...,in−1∈E

ν(i0) p(i0, i1) · · · p(in−1, i)

= [ν pn] (i).


Exemple: temps à Nancy


Prédiction à J+2:

p2 =

0.4 0.6 0 0 0 00.24 0.76 0 0 0 00.12 0.3 0.16 0.19 0.18 0.050 0 0 0.44 0.21 0.350 0 0 0.55 0.35 0.10 0 0 0.4 0.56 0.04


Exemple: temps à Nancy (2)


Prédiction à J+28:

p28 =

0.29 0.71 0 0 0 00.29 0.71 0 0 0 00.14 0.36 7.2× 10−12 0.23 0.16 0.100 0 0 0.47 0.33 0.200 0 0 0.47 0.33 0.200 0 0 0.47 0.33 0.20


Critère de markovianitéPropositionSoient

Z : Ω→ E variable aléatoire.F ensemble dénombrable.Yn; n ≥ 1 suite i.i.d, avec Y ⊥⊥ Z et Yn ∈ F .f : E × F → E.

On poseX0 = Z , et Xn+1 = f (Xn,Yn+1).

Alors X est une chaîne de Markov homogène telle que

ν0 = L(Z ), et p(i , j) = P (f (i ,Y1) = j) .

Remarque: Il existe une réciproque, mais on ne l’utilisera pas.Samy T. (IECL) M1 - Chaînes de Markov Université de Lorraine 18 / 78

Démonstration

Sous les hypothèses de la proposition:

P (Xn+1 = j |X0 = i0, . . . ,Xn = in)

= P (f (Xn,Yn+1) = j |X0 = i0, . . . ,Xn = in)

= P (f (in,Yn+1) = j |X0 = i0, . . . ,Xn = in)

= P (f (in,Y1) = j)= p(in, j)


Exemple: marche aléatoire

Rappel: On a vu que X est défini parZi ; i ≥ 1 v.a. indépendantes de Rademacher→ P(Zi = −1) = P(Zi = 1) = 1/2On pose X0 = 0, et pour n ≥ 1, Xn =

∑ni=1 Zi .

Application du critère:

Xn+1 = f (Xn,Zn+1), avec f : Z× −1, 1 → Z, (x , z) 7→ x + z

et X CHMH avec ν0 = δ0 et

p(i , j) = P (Z1 = j − i) =12δi+1(j) +

12δi−1(j).


Familles markoviennes de probabilités

Dépendence par rapport à la loi initiale: on note

Pµ (X0 = i0, . . . ,Xn = in) = µ(i0) p(i0, i1) · · · p(in−1, in)

Eµ [ϕ(X0, . . . ,Xn)] =∑

i0,...,in∈Eϕ(i0, . . . , in)µ(i0) p(i0, i1) · · · p(in−1, in)

Cas de la condition initiale fixe: on note Pδi = Pi . Donc

Pi (X0 = i0, . . . ,Xn = in) = δi(i0) p(i0, i1) · · · p(in−1, in)

Ei [ϕ(X0, . . . ,Xn)] =∑

i1,...,in∈Eϕ(i , i1, . . . , in) p(i , i1) · · · p(in−1, in)


Relation entre familles markoviennesPropositionSoit X chaîne de Markov de transition p.(i) Soit µ ∈M1(E ) telle que µ(i) 6= 0. On a

Pi (X0 = i0, . . . ,Xn = in) = Pµ (X0 = i0, . . . ,Xn = in|X0 = i)Ei [ϕ(X0, . . . ,Xn)] = Eµ [ϕ(X0, . . . ,Xn)|X0 = i ]

(ii) Soit µ ∈M1(E ). Alors

Pµ (X0 = i0, . . . ,Xn = in) =∑i∈E

µ(i) Pi (X0 = i0, . . . ,Xn = in)

Eµ [ϕ(X0, . . . ,Xn)] =∑i∈E

µ(i) Ei [ϕ(X0, . . . ,Xn)]


Démonstration

(i) On part de la définition:

Pµ (X0 = i0, . . . ,Xn = in|X0 = i)

=Pµ (X0 = i0, . . . ,Xn = in,X0 = i)

Pµ (X0 = i)

=µ(i) p(i , i1) · · · p(in−1, in)

µ(i) 1(i0=i)

= p(i , i1) · · · p(in−1, in) 1(i0=i)

= Pi (X0 = i0, . . . ,Xn = in)


Démonstration (2)

(ii) On utilise l’étape précédente:

Pµ (X0 = i0, . . . ,Xn = in)

=∑i∈E

Pµ (X0 = i0, . . . ,Xn = in|X0 = i) µ(i)

=∑i∈E

Pi (X0 = i0, . . . ,Xn = in) µ(i)


Plan





5 Absorption


Plan





5 Absorption


Temps d’arrêt

DéfinitionFiltration: suite de σ-algèbres telles que Fn ⊂ Fn+1.

DéfinitionSoient

T : Ω→ N un temps aléatoire.Fn = σ(X0, . . . ,Xn)

On dit que T est un temps d’arrêt siPour tout n ∈ N, l’ensemble ω; T (ω) = n est Fn-mesurable.


Temps d’arrêt: interprétation

Définition alternative: T est un temps d’arrêt si→ Pour tout n ∈ N, il existe An ∈ E n+1 tel que

ω; T (ω) = n = ω; (X0(ω), . . . ,Xn(ω)) ∈ An

Donc, si on connaît X0, . . . ,Xn, on sait si T = n ou T 6= n.

Définition alternative 2: Dans la définition de temps d’arrêton peut remplacer ω; T (ω) = n parω; T (ω) ≤ nω; T (ω) > n


Propriétés simples des temps d’arrêt

PropositionSoient S et T deux temps d’arrêt. Alors

1 S ∧ T2 S ∨ T

sont des temps d’arrêt.

PropositionSi T est un temps déterministe (T = n presque sûrement)→ alors T est un temps d’arrêt.


Temps de retour et de visiteTemps de premier retour: Soit j ∈ E . On pose

Rj = inf n ≥ 1; Xn = j ,

temps de premier retour de X en j .

Temps de k ième retour: Soit j ∈ E et k ≥ 2. On pose

Rkj = inf

n ≥ Rk−1

j + 1; Xn = j,

temps de k ième retour de X en j .

Temps de visite: Soit C ⊂ E . On pose

TC = inf n ≥ 0; Xn ∈ C ,

temps de 1ère visite en C .Samy T. (IECL) M1 - Chaînes de Markov Université de Lorraine 30 / 78

Retours, visites et temps d’arrêtPropositionSoit

X une chaîne de MarkovFn; n ≥ 0 la filtration naturelle

Alors les temps Rj , Rkj et TC sont des temps d’arrêt.

Démonstration:(i) Pour n ≥ 1, on a

Rj = n = X1 6= j , . . . ,Xn−1 6= j ,Xn = j

(ii) Pour n ≥ 1, on aRk

j = n

=

n−1∑l=1

1j(Xl) = k − 1, Xn = j


Contre-exemple

Dernier temps de passage: Soit i ∈ E et

Si = sup n ≥ 0; Xn = i .

Alors

Si = 10 = X10 = i ∩ Xn 6= i ; pour tout n ≥ 11

Ceci dépend aussi du futur après n = 10, i.e

Si = 10 6∈ F10.

Donc Si n’est pas un temps d’arrêt.


Plan





5 Absorption


Processus Before et After

Temps de séparation: On considère τ ∈ N.

Processus Before: Soit Bτ = Bτn ; n ≥ 0 défini par

Bτn = Xn∧τ = Xn 1(n≤τ) + Xτ 1(n>τ).

Processus After: Soit Aτ = Aτn; n ≥ 0 défini par

Aτn = Xτ+n.


Ensembles cylindriques

DéfinitionSoit A ⊂ EN. On dit que A est cylindriques’il existe k ≥ 0 et 0 ≤ n0 < n1 < · · · < nk tels que

A =x ∈ EN; xn0 = i0, . . . , xnk = ik

, pour i0, . . . , ik ∈ E ,

ou plus généralement

A =x ∈ EN; xn0 ∈ E0, . . . , xnk ∈ Ek

, pour E0, . . . ,Ek ⊂ E .


Propriété de MarkovPropositionSoit

X chaîne de Markov homogène (loi initiale ν0, transition p).τ ∈ N.

Alors

(i) Aτ chaîne de Markov homogène (loi initiale L(Xτ ), transition p).

(ii) Aτ ⊥⊥ Bτ conditionnellement à Xτ , i.e.Pour tous A,B cylindriques et i ∈ E on a

P (Aτ ∈ A, Bτ ∈ B|Xτ = i)= P (Aτ ∈ A|Xτ = i) P (Bτ ∈ B|Xτ = i)


DémonstrationPoint (i):

P(Aτn+1 = j |Aτ0 = i0, . . . ,Aτn = in

)= P (Xτ+n+1 = j |Xτ = i0, . . . ,Xτ+n = in)

= P (Xτ+n+1 = j |Xτ+n = in) (1)= P

(Aτn+1 = j |Aτn = in

)= p(in, j)

Démonstration de (1): On a

P (Xτ+n+1 = j |Xτ = i0, . . . ,Xτ+n = in)

=P (Xτ = i0, . . . ,Xτ+n = in,Xτ+n+1 = j)

P (Xτ = i0, . . . ,Xτ+n = in):=

ND


Démonstration (2)Calcul de N :

N =∑

`0,...,`τ−1∈EP(X0 = `0, . . . ,Xτ−1 = `τ−1,

Xτ = i0, . . . ,Xτ+n = in,Xτ+n+1 = j)=

∑`0,...,`τ−1∈E

P (X0 = `0, . . . ,Xτ−1 = `τ−1,Xτ = i0, . . . ,Xτ+n = in)

× P (Xτ+n+1 = j |Xτ+n = in)

= P (Xτ = i0, . . . ,Xτ+n = in) P (Xτ+n+1 = j |Xτ+n = in)

= D × P (Xτ = i0, . . . ,Xτ+n = in)

Conclusion:

P (Xτ+n+1 = j |Xτ = i0, . . . ,Xτ+n = in) =ND

= P (Xτ+n+1 = j |Xτ+n = in) .


Démonstration plus élégante de (i)Rappel: Soit (Xn)n≥0 chaîne de MarkovAlors (Xn)n≥0 homogène ssi il existe p : E × E → [0, 1] telle que

P (Xn+1 = j | Fn) = p(Xn, j)

pour tout n ≥ 0 et j ∈ E .

Application:

P(Aτn+1 = j | FAτ

n

)= P (Xτ+n+1 = j |Xτ , . . . ,Xτ+n)

= E P (Xτ+n+1 = j | Fτ+n) |Xτ , . . . ,Xτ+n= E [p(Xτ+n, j)|Xτ , . . . ,Xτ+n]

= p(Xτ+n, j) = p(Aτn, j),

ce qui montre que Aτ est une chaîne homogène de transition p.


Propriété de Markov forteThéorèmeSoit

X chaîne de Markov homogène (loi initiale ν0, transition p).T temps d’arrêt fini.XT (ω)(ω) =

∑∞n=0 Xn(ω) 1(T (ω)=n).

Alors(i) AT chaîne de Markov homogène, (loi initiale L(XT ), transition p).(ii) AT ⊥⊥ BT conditionnellement à XT , i.e.Pour tous A,B cylindriques et i ∈ E on a

P(AT ∈ A, BT ∈ B|XT = i

)= P

(AT ∈ A|XT = i

)P(BT ∈ B|XT = i

)


Démonstration

Stratégie: on va montrer que

P(AT

0 = i0, . . . ,ATn = in

)= P(XT = i0) p(i0, i1) · · · p(in−1, in)

Préliminaires: On a1 P

(AT

0 = i0, . . . ,ATn

)=∑∞

k=0 P(T = k ,AT

0 = i0, . . . ,ATn = in

)2 T = k = (X0, . . . ,Xk) ∈ Dk.


Démonstration (2)Calcul:

P(AT

0 = i0, . . . ,ATn = in

)=∞∑

k=0P(

(X0, . . . ,Xk) ∈ Dk , AT0 = i0, . . . ,AT

n = in)

=∞∑

k=0P ((X0, . . . ,Xk) ∈ Dk , Xk = i0, . . . ,Xk+n = in)

=∞∑

k=0P ((X0, . . . ,Xk) ∈ Dk , Xk = i0)

× P (Xk+1 = i0, . . . ,Xk+n = in| (X0, . . . ,Xk) ∈ Dk , Xk = i0)

=∞∑

k=0P ((X0, . . . ,Xk) ∈ Dk , Xk = i0) p(i0, i1) · · · p(in−1, in)

= P(XT = i0) p(i0, i1) · · · p(in−1, in)


Cas particuliers d’application

PropositionSoit X chaîne de Markov homogène (loi initiale ν0, transition p).

1 Si T est un temps d’arrêt fini p.s.

P (XT+n = j |XT = i0, . . . ,XT+n−1 = in−1) = p(in−1, j)E [ϕ(XT+n)|XT = i ] = Ei [ϕ(Xn)]

2 Si T = Ti, Ri ou Rki , on a XT = i et

I AT est une chaîne de Markov (loi initiale δi , transition p).I AT ⊥⊥ BT .


Contre-exempleContexte: On considère

Xn =∑n

i=1 Yi avec Yi i.i.d et Yi ∼ B(1/2)→ X chaine de Markov de transition

p(i , j) =12 1(j=i) +

12 1(j=i+1).

Le temps aléatoire T = supn ≥ 0;Xn = 0→ T <∞ p.s. et XT = 0.

Conclusion: Alors

P (XT+1 = 1|XT = 0) = 1 6= p(0, 1) = P0(X1 = 1).

La condition T temps d’arrêt est donc nécessaire.


Loi de la chaîne Before

ThéorèmeSoient

X chaîne de Markov homogène (loi initiale ν0, transition p).C ⊂ E et TC = infn ≥ 0; Xn ∈ C

Alors1 BTC chaîne de Markov homogène (loi initiale ν0, transition q)2 On a

q(i , j) = p(i , j) 1Cc (i) + δi(j)1C (i).

Matriciellement:Q =

(P P0 Id

)


Plan





5 Absorption


Accessibilité

Rappel: pour une chaîne de Markov homogène X , on a vu que

Pν (Xn = j) =∑i∈E

ν(i)pn(i , j).

Accessibilité:On dit que j accessible depuis i si

Il existe n ≥ 0 tel que Pi (Xn = j) = pn(i , j) > 0.

Notation: i → j .


Communication

Communication:Si i → j et j → i , on dira que i et j communiquent.Notation: i ↔ j .

Remarques:1 Les définitions i → j et i ↔ j ne dépendent pas de ν.2 Pour tout i ∈ E , on a i ↔ i car p0(i , i) = 1.3 Si i → j et j → k , alors i → k .


Graphe associé à une chaîne de Markov

DéfinitionSoit X chaîne de Markov homogène (loi initiale ν0, transition p).On note G(X ) le graphe défini parG(X ) est un graphe orienté.Les sommets de G(X ) sont les points de E .Les arêtes de G(X ) sont définies par l’ensemble

V ≡ (i , j); i 6= j , p(i , j) > 0 .


Exemple

Définition de la chaîne: Prenons E = 1, 2, 3, 4, 5 et

p =

1/3 0 2/3 0 01/4 1/2 1/4 0 01/2 0 1/2 0 00 0 0 0 10 0 0 2/3 1/3

Graphe associé: au tableau.


Graphe et accessibilité

PropositionSoit X chaîne de Markov homogène (loi initiale ν0, transition p).Alors

i → j ssi i = j ou il existe un chemin orienté de i à j dans G(X ).

Démonstration: Si i 6= j on a(i → j) ⇔ Il existe n ≥ 1 tel que pn(i , j) > 0⇔ Il existe n ≥ 1 tel que ∑i1,...,in−1∈E p(i , i1) · · · p(in−1, j) > 0⇔ Il existe n ≥ 1 et i1, . . . , in−1 ∈ E tels que p(i , i1) · · · p(in−1, j) > 0⇔ Il existe un chemin orienté de i à j dans G(X )


Classes

PropositionSoit X chaîne de Markov homogène (loi initiale ν0, transition p).Alors

1 La relation ↔ est une relation d’équivalence.2 Notons C1, . . . ,Cl les classes d’équivalence dans E pour ↔.

Alors → est une relation d’ordre partiel entre classesi.e. C1 → C2 et C2 → C3 =⇒ C1 → C3.

3 C1 → C2 ssi il existe i ∈ C1 et j ∈ C2 tels que i → j .


Exemple

Définition de la chaîne: Prenons E = 1, 2, 3, 4, 5 et

p =

1/3 0 2/3 0 01/4 1/2 1/4 0 01/2 0 1/2 0 00 0 0 0 10 0 0 2/3 1/3

Classes associés:C1 = 1, 3, C2 = 2 et C3 = 4, 5.On a C2 → C1


Classe minimaleDéfinitionUne classe d’équivalence C est minimale si:

Pour tout i ∈ C et j 6∈ C , on a i 6→ j .

Exemple:Sur l’exemple précédent, on a C1,C3 minimales, et C2 non minimale.

Critères de minimalité:(i) S’il existe une unique classe C , elle est minimale.(ii) Il existe une unique classe minimale C⇔ Il existe une classe C telle que pour tout i ∈ E , on a i → C .

Application: Marche aléatoire.


Etats récurrents et transitoires

DéfinitionSoient

X chaîne de Markov homogène (loi initiale ν0, transition p).Un élément i ∈ E

Alors1 On dit que i est récurrent si Pi (Ri <∞) = 12 On dit que i est transitoire si Pi (Ri <∞) < 1

Interprétation:Si i est récurrent, en partant de i on est sûr d’y revenir.


Nombre de passagesPropositionSoient

X chaîne de Markov homogène (loi initiale ν0, transition p).Un élément i ∈ E et

N(i) =∞∑

k=0δi(Xk),

i.e. N(i) est le nombre de passages de X par i .Alors

1 L’état i est récurrent ⇔ N(i) =∞, Pi -presque sûrement.2 L’état i est transitoire ⇔ N(i) <∞, Pi -presque sûrement.

Démonstration: Application de Markov fort.Samy T. (IECL) M1 - Chaînes de Markov Université de Lorraine 56 / 78

Récurrence et classesThéorèmeSoient

X chaîne de Markov homogène (loi initiale ν0, transition p).C une classe pour la relation ↔.

Alors1 Tous les états de C sont de la même nature (récurrent ou

transitoire).2 S’il existe i ∈ C tel que Ei [Ri ] <∞→ pour tout j ∈ C on a Ej [Rj ] <∞

3 S’il existe i ∈ C tel que Ei [Ri ] <∞→ pour tous j , k ∈ C on a Ej [Rk ] <∞

Démonstration: Application de Markov fort.


Critères de récurrence

ThéorèmeSoient

X chaîne de Markov homogène (loi initiale ν0, transition p).C une classe pour la relation ↔.

Alors1 Si C n’est pas minimale, elle est transitoire.2 Si C est minimale et |E | <∞, alors

I C est récurrenteI C est récurrente positive: pour tout i ∈ C, Ei [Ri ] <∞.


Exemple

Définition de la chaîne: Prenons E = 1, 2, 3, 4, 5 (donc |E | <∞)et

p =

1/3 0 2/3 0 01/4 1/2 1/4 0 01/2 0 1/2 0 00 0 0 0 10 0 0 2/3 1/3

Classes associés:C1 = 1, 3, C2 = 2 et C3 = 4, 5.→ C1,C3 minimales, et C2 non minimale.

Conclusion: C1,C3 récurrentes positives, C2 transitoire.


Plan





5 Absorption


Hypothèses du théorème ergodique

On suppose:X chaîne de Markov (loi initiale ν, transition p) telle que(a) Il existe une classe minimale unique C .(b) On a TC <∞, Pν presque sûrement.(c) Pour tout i ∈ C , on a Ei [Ri ] <∞.

Remarque: Si |E | <∞→ (b) et (c) sont toujours vérifiées.


Théorème limiteThéorèmeSous les hypothèses (a)-(b)-(c), on a

1 Il existe une solution unique de l’équation matricielle dans R1,|E |

→ π = π p et 〈π, 1〉 = 1, ou encore

π(j) =∑i∈E

π(i) p(i , j),∑j∈E

π(j) = 1. (2)

2 Pour toute fonction f : E → R bornée on a

limn→∞

1n

n∑k=1

f (Xk) =∑i∈E

f (i)π(i), Pν − p.s.

3 π(i) = 0 si i 6∈ C et pour i ∈ C on a π(i) = 1Ei [Ri ]

.


Explications

Point 3: Si on prend f (j) = δi(j), alors le point 2 donne

Proportion du temps passé en i =Nn(i)n −→ π(i).

Intuitivement, proportion du temps passé en i→ Inversement proportionnelle au temps de retour Ri en i .→ π(i) = 1

Ei [Ri ].

Point 2: On s’attend à 1n∑n

k=1 f (Xk) −→ ∑i∈E f (i)π(i), car

1n

n∑k=1

f (Xk) =∑i∈E

f (i)Nn(i)n .


Explications (2)

Vocabulaire:Si π est solution de (2),

π se nomme mesure de probabilités invariante pour p.Si L(X0) = π, alors L(Xn) = π pour tout n ≥ 1.

Point 1: Notons νk(i) = Pν(Xk = i). AlorsEν [Nn(i)] =

∑nk=1 νk(i).

1n∑n

k=1 νk(i) −→ π(i) par convergence dominée.Donc νn −→ π au sens de Cesaro. Donc

[νn+1 = νnp]n→∞−→ [π = πp] .


ExempleDéfinition de la chaîne: Prenons E = 1, 2, 3, 4 (donc |E | <∞) et

p =

1/4 1/4 1/4 1/40 0 1 00 1/2 0 1/20 0 1 0

Classes associés:C1 = 1, C2 = 2, 3, 4→ C1 non minimale et C2 minimale.

Conclusion: C2 récurrente positive, C1 transitoire.

Mesure invariante:en résolvant le système π = π p et 〈π, 1〉 = 1, on trouve

π = (0, 1/4, 1/2, 1/4) .

De plus, le théorème ergodique s’applique.Samy T. (IECL) M1 - Chaînes de Markov Université de Lorraine 65 / 78

Exemple (2)Remarque:• En général, il est plus facile de résoudre le systèmeπ = π p et 〈π, 1〉 = 1 que de calculer Ei [Ri ].• Ici, ce calcul est cependant possible.

Analyse directe: On trouve• E1[R1] =∞ car 1 est transitoire.• E3[R3] = 2 car R3 = 2, P3-p.s.• Pour calculer E2[R2]:

E2[1(R2>2k+2)

]= E2

[1(R2>2k) 1(R2>2k+2)

]= E2

1(R2>2k) EX2k

[1(R2(A2k)>2)

]= E2

1(R2>2k) E4

[1(R2(A2k)>2)

]= E2

[1(R2>2k) p(4, 3) p(3, 4)

]=

12E2

[1(R2>2k)

]On en déduit P2(R2 > 2k) = 1/2k et E2[R2] = 4 = E4[R4].


Convergence en loi

ThéorèmeSoit X chaîne de Markov (loi initiale ν, transition p) telle que(a) |E | <∞.(b) Il existe une classe minimale unique C.(c) Une des deux hypothèses est vérifiée:

1 p(i , i) > 0 pour tout i ∈ C.2 Il existe n ≥ 1 tel que pn(i , j) > 0 pour tout i , j ∈ E.

Alors

Xn(d)−→ π, i.e. lim

n→∞νn(i) = π(i), pour tout i ∈ E .


Plan





5 Absorption


Définition, Hypothèse, Notation

DéfinitionSoit X chaîne de Markov (loi initiale ν, transition p).

On dit que i ∈ E est absorbant si p(i , i) = 1On dit que X est absorbante si ses classes minimales sont dessingletons.

Hypothèse de travail: |E | <∞ et X absorbante.

Notation: On décompose E = T ∪ A avec

T = Eléments transitoires , A = Eléments absorbants .


Exemple

Définition de la chaîne: Prenons E = 1, 2, 3, 4 (donc |E | <∞) et

p =

1 0 0 01/2 0 1/2 00 1/2 0 1/20 0 0 1

Classes associés:C1 = 1, C2 = 2, 3, C3 = 4→ C1,C3 minimales et C2 non minimale.→ X est absorbante.


Loi à l’instant n

PropositionSoit X chaîne absorbante avec |E | <∞.On décompose p sur E = T ∪ A en

p =

(Q R0 Id

)

Alors pour n ≥ 1 on a

pn =

(Qn Rn0 Id

), avec Rn =

n−1∑j=0

Qj

R


Limite de p

ThéorèmeSoit X chaîne absorbante avec |E | <∞. Alors

1 On a limn→∞Qn = 0 .2 limn→∞ Rn = A avec A stochastique.3 Id− Q inversible et on pose M = (Id− Q)−1.4 On a A = M R.

Résumé:

p∞ =

(0 A0 Id

), avec A = (Id− Q)−1 R := M R


DémonstrationPoint 1: Soit ‖ · ‖ la norme sur les matrices de RT×T définie par

‖B‖ = supi∈T

supj∈T|B(i , j)|

Comme T → A, on peut montrer (un peu délicat) que

‖Qn‖ ≤ cβn, avec 0 < β < 1

En particulier, limn→∞Qn = 0.

Autres points: En fait, Qn → 0 exponentiellement. Donc:∑∞j=0 Qj converge vers (Id− Q)−1 := M.

(∑∞

j=0 Qj)R converge vers M R := A.Comme pn est stochastique, A est stochastique.


Temps d’absorption

ThéorèmeSoient

X chaîne absorbante avec |E | <∞.A, M et R définies au théorème précédent.TA = infn ≥ 0; Xn ∈ A = temps d’absorption.N(j) = limn→∞ Nn(j) = nombre de passages en j (pour j ∈ T).

Alors1 TA <∞ presque sûrement.2 A(i , j) = Pi(XTA = j) pour i ∈ T et j ∈ A.3 M(i , j) = Ei [N(j)] pour i , j ∈ T.4 Ei [TA] =

∑j∈T M(i , j).


DémonstrationPoints 1 et 2: Pour i ∈ T et j ∈ A, on a

pn(i , j) = Pi (Xn = j) = Pi (TA ≤ n, XTA = j)

En passant à la limite n→∞,

A(i , j) = Pi (TA <∞, XTA = j)

De plus, A est stochastique. Donc

1 =∑j∈A

Pi (TA <∞, XTA = j) = Pi (TA <∞)

etA(i , j) = Pi (TA <∞, XTA = j) = Pi (XTA = j)


Démonstration (2)

Point 3: On a, pour i , j ∈ T

M(i , j) =∞∑

n=0Qn(i , j) =

∞∑n=0

pn(i , j)

=∞∑

n=0Ei [δj(Xn)] = Ei

[ ∞∑n=0

δj(Xn)

]= Ei [N(j)]

Point 4: On a, pour i ∈ T ,

Ei [TA] = Ei

[ ∞∑n=0

1T (Xn)

]= Ei

∞∑n=0

∑j∈T

δj(Xn)

=∑j∈T

M(i , j).


ExempleDéfinition de la chaîne: Prenons E = 1, 2, 3, 4 (donc |E | <∞) et

p =

1 0 0 01/2 0 1/2 00 1/2 0 1/20 0 0 1

Décomposition en T ∪ A:On a T = 2, 3, A = 1, 4 et selon cette décomposition,

p =

0 1/2 1/2 01/2 0 0 1/20 0 1 00 0 0 1


Exemple (2)Matrices Q,R : On trouve

Q =

(0 1/21/2 0

), Id− Q =

(1 −1/2−1/2 1

), R =

(1/2 00 1/2

)

Matrices M,A: On a donc

M = [Id− Q]−1 =43

(1 1/21/2 1

), A =

M2 =

23

(1 1/21/2 1

).

Lecture en termes de probabilités: On obtient par exemple

P2 (XTA = 1) = A(2, 1) =23 , P2 (XTA = 4) = A(2, 4) =

13

E2[TA] = M(2, 2) + M(2, 3) = 2


Documents

Chaînes de Markov - IECL | Institut Élie Cartan de … · Plan 1 Déﬁnitionetexemples 2 PropriétésdeMarkov Tempsd’arrêt PropriétésdeMarkov 3 Classiﬁcationdesétats 4