Chaine de Markov [PDF]

Zitiervorschau

Pr. Chaabane Djamal

C haîne de M arkov

M&R

Chaînes de Markov

L icence - Recherche Opérationnelle

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Département de Recherche Opérationnelle USTHB- /Faculté des Mathématique

Le Plan du cours Pr. Chaabane Djamal

1 Chaînes de Markov

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov 2 Illustrations

Illustration 1

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

3 Classification des états

Passage par un état fixe 4 Etude asymptotique 5 Résultats dŠalgèbre linéaire pour les chaînes de Markov

Plan Pr. Chaabane Djamal

1 Chaînes de Markov

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov 2 Illustrations

Illustration 1

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

3 Classification des états

Passage par un état fixe 4 Etude asymptotique 5 Résultats dŠalgèbre linéaire pour les chaînes de Markov

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I On considère un espace de probabilité (Ω, A , P).

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I On considère un espace de probabilité (Ω, A , P). I X1 , · · · , Xn une suite de variables aléatoires de valeurs dans un ensemble E; n ∈ N.

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I On considère un espace de probabilité (Ω, A , P). I X1 , · · · , Xn une suite de variables aléatoires de valeurs dans un ensemble E; n ∈ N. I Quand Xn prend la valeur i,

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I On considère un espace de probabilité (Ω, A , P). I X1 , · · · , Xn une suite de variables aléatoires de valeurs dans un ensemble E; n ∈ N. I Quand Xn prend la valeur i, on dit que le système est à l’état i à l’instant n,

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I On considère un espace de probabilité (Ω, A , P). I X1 , · · · , Xn une suite de variables aléatoires de valeurs dans un ensemble E; n ∈ N. I Quand Xn prend la valeur i, on dit que le système est à l’état i à l’instant n, on écrit ∀ω ∈ Ω; Xn (ω) = i

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I On considère un espace de probabilité (Ω, A , P). I X1 , · · · , Xn une suite de variables aléatoires de valeurs dans un ensemble E; n ∈ N. I Quand Xn prend la valeur i, on dit que le système est à l’état i à l’instant n, on écrit ∀ω ∈ Ω; Xn (ω) = i et l’ensemble des valeurs de Xn ; ∀n ∈ N est appelé ensemble des états .

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov

I On considère un espace de probabilité (Ω, A , P). I X1 , · · · , Xn une suite de variables aléatoires de valeurs dans un ensemble E; n ∈ N. I Quand Xn prend la valeur i, on dit que le système est à l’état i à l’instant n, on écrit ∀ω ∈ Ω; Xn (ω) = i et l’ensemble des valeurs de Xn ; ∀n ∈ N est appelé ensemble des états .

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Définition

Le processus stochastique X = {Xn ; , n ∈ N} est une chaîne de Markov si

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov

I On considère un espace de probabilité (Ω, A , P). I X1 , · · · , Xn une suite de variables aléatoires de valeurs dans un ensemble E; n ∈ N. I Quand Xn prend la valeur i, on dit que le système est à l’état i à l’instant n, on écrit ∀ω ∈ Ω; Xn (ω) = i et l’ensemble des valeurs de Xn ; ∀n ∈ N est appelé ensemble des états .

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Définition

Le processus stochastique X = {Xn ; , n ∈ N} est une chaîne de Markov si

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (Xn+1 = j | X0 , X1 , · · · , Xn ) = P (Xn+1 = j | Xn ) ∀j ∈ E ∀n ∈ N

C aînes de M arkov

Pr. Chaabane Djamal

N otation

P (Xn+1 = j | Xn = i) = Pi,j

∀i, j ∈ E

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Ces probabilités constituent matrice de probabilités de transition .

une

matrice

dite

C aînes de M arkov

Pr. Chaabane Djamal

N otation

P (Xn+1 = j | Xn = i) = Pi,j

∀i, j ∈ E

M&R

Chaînes de Markov

Ces probabilités constituent matrice de probabilités de transition .

une

matrice

dite

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations

Probabilités de transition

Considérons un ensembles des états E = {0, 1, 2, · · · , }. On écrit

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

   P =  

 p00 p01 p02 · · ·   p10 p11 p12 · · ·  .. .. .. . .  . . . .

Plan Pr. Chaabane Djamal

1 Chaînes de Markov

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov 2 Illustrations

Illustration 1

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

3 Classification des états

Passage par un état fixe 4 Etude asymptotique 5 Résultats dŠalgèbre linéaire pour les chaînes de Markov

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

M atrice S tochastique

Inversement,

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

M atrice S tochastique

Inversement, pour toute matrice Markovienne donnée,

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

M atrice S tochastique

Inversement, pour toute matrice Markovienne donnée, sur un ensemble dénombrable E,

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

M atrice S tochastique

Inversement, pour toute matrice Markovienne donnée, sur un ensemble dénombrable E, il est possible de construire un échantillon d’un espace Ω,

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

M atrice S tochastique

Inversement, pour toute matrice Markovienne donnée, sur un ensemble dénombrable E, il est possible de construire un échantillon d’un espace Ω, une probabilité p sur tous les sous-ensembles de Ω (tribu)

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

M atrice S tochastique

Inversement, pour toute matrice Markovienne donnée, sur un ensemble dénombrable E, il est possible de construire un échantillon d’un espace Ω, une probabilité p sur tous les sous-ensembles de Ω (tribu) et des variables aléatoires X1 , X2 , · · · définies sur Ω prenant ses valeurs dans E telles que

C aînes de M arkov

Pr. Chaabane Djamal

M atrice S tochastique

La matrice Pest dite matrice de MARKOV si M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

¶ pij ≥ 0, , ∀i, j ∈ E X · pij = 1 ∀i ∈ E j∈E

M atrice S tochastique

Inversement, pour toute matrice Markovienne donnée, sur un ensemble dénombrable E, il est possible de construire un échantillon d’un espace Ω, une probabilité p sur tous les sous-ensembles de Ω (tribu) et des variables aléatoires X1 , X2 , · · · définies sur Ω prenant ses valeurs dans E telles que X = {X1 , X2 , · · · , } est une chaîne de Markov.

Plan Pr. Chaabane Djamal

1 Chaînes de Markov

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov 2 Illustrations

Illustration 1

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

3 Classification des états

Passage par un état fixe 4 Etude asymptotique 5 Résultats dŠalgèbre linéaire pour les chaînes de Markov

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit X une chaîne de Markov, de matrice de probabilités de transition P, et espace des états E.

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit X une chaîne de Markov, de matrice de probabilités de transition P, et espace des états E. I Soient i, j, k trois états fixés dans E. On a :

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit X une chaîne de Markov, de matrice de probabilités de transition P, et espace des états E. I Soient i, j, k trois états fixés dans E. On a : I P (X6 = j, X7 = k | X5 = i)

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit X une chaîne de Markov, de matrice de probabilités de transition P, et espace des états E. I Soient i, j, k trois états fixés dans E. On a : I P (X6 = j, X7 = k | X5 = i) = P (X7 = k | X5 = i, X6 = j) P (X6 = j | X5 = i)

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit X une chaîne de Markov, de matrice de probabilités de transition P, et espace des états E. I Soient i, j, k trois états fixés dans E. On a : I P (X6 = j, X7 = k | X5 = i) = P (X7 = k | X5 = i, X6 = j) P (X6 = j | X5 = i) I Or P (X7 = k | X5 = i, X6 = j) = P (X7 = k | X6 = j) = pjk

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit X une chaîne de Markov, de matrice de probabilités de transition P, et espace des états E. I Soient i, j, k trois états fixés dans E. On a : I P (X6 = j, X7 = k | X5 = i) = P (X7 = k | X5 = i, X6 = j) P (X6 = j | X5 = i) I Or P (X7 = k | X5 = i, X6 = j) = P (X7 = k | X6 = j) = pjk I Donc P (X6 = j, X7 = k | X5 = i) = pij × pjk

C aînes de M arkov

Pr. Chaabane Djamal

T héorème

Pour tout n, m ∈ N avec m ≥ 1 et i0 , i1 , · · · , im ∈ E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (Xn+1 = i1 , · · · , Xn+m = im | Xn = i0 ) = Pi0 ,i1 × · · · × Pim−1 ,im

C aînes de M arkov

Pr. Chaabane Djamal

T héorème

Pour tout n, m ∈ N avec m ≥ 1 et i0 , i1 , · · · , im ∈ E M&R

P (Xn+1 = i1 , · · · , Xn+m = im | Xn = i0 ) = Pi0 ,i1 × · · · × Pim−1 ,im

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

En posant n = 0 on obtient : C orollaire

Soit π une loi de probabilité sur E, P (X0 = i) = πi ∀i ∈ E.

on suppose que

C aînes de M arkov

Pr. Chaabane Djamal

T héorème

Pour tout n, m ∈ N avec m ≥ 1 et i0 , i1 , · · · , im ∈ E M&R

P (Xn+1 = i1 , · · · , Xn+m = im | Xn = i0 ) = Pi0 ,i1 × · · · × Pim−1 ,im

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

En posant n = 0 on obtient : C orollaire

Soit π une loi de probabilité sur E, on suppose que P (X0 = i) = πi ∀i ∈ E. Alors ∀m ∈ N et i0 , · · · , im ∈ E,

C aînes de M arkov

Pr. Chaabane Djamal

T héorème

Pour tout n, m ∈ N avec m ≥ 1 et i0 , i1 , · · · , im ∈ E M&R

P (Xn+1 = i1 , · · · , Xn+m = im | Xn = i0 ) = Pi0 ,i1 × · · · × Pim−1 ,im

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

En posant n = 0 on obtient : C orollaire

Soit π une loi de probabilité sur E, on suppose que P (X0 = i) = πi ∀i ∈ E. Alors ∀m ∈ N et i0 , · · · , im ∈ E, P (X0 = i0 , · · · , Xm = im ) = πi0 Pi0 ,i1 × · · · × Pim−1 ,im

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I ∀h, i, j, k ∈ E on écrit

C aînes de M arkov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I ∀h, i, j, k ∈ E on écrit I P (Xn+1 = i, Xn+2 = j, Xn+3 = k | Xn = h) = phi pij pjk

C aînes de M arkov

Pr. Chaabane Djamal

I ∀h, i, j, k ∈ E on écrit I P (Xn+1 = i, Xn+2 = j, Xn+3 = k | Xn = h) = phi pij pjk I On a

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (Xn+3 = k | Xn = h)

=

X i∈E

phi

X j∈E

pij pjk

C aînes de M arkov

Pr. Chaabane Djamal

I ∀h, i, j, k ∈ E on écrit I P (Xn+1 = i, Xn+2 = j, Xn+3 = k | Xn = h) = phi pij pjk I On a

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (Xn+3 = k | Xn = h)

= =

X i∈E X i∈E

phi

X

j∈E phi p(2) ik

pij pjk

C aînes de M arkov

Pr. Chaabane Djamal

I ∀h, i, j, k ∈ E on écrit I P (Xn+1 = i, Xn+2 = j, Xn+3 = k | Xn = h) = phi pij pjk I On a

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

P (Xn+3 = k | Xn = h)

= =

X i∈E X i∈E

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

= p(3) hk

phi

X

j∈E phi p(2) ik

pij pjk

C aînes de M arkov

Pr. Chaabane Djamal

I ∀h, i, j, k ∈ E on écrit I P (Xn+1 = i, Xn+2 = j, Xn+3 = k | Xn = h) = phi pij pjk I On a

M&R

Chaînes de Markov

P (Xn+3 = k | Xn = h)

= =

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

X i∈E X

phi

X

j∈E phi p(2) ik

i∈E

Illustrations

= p(3) hk

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

p(2) est l’élément (i, k) de ik

la matrice P2

pij pjk

C aînes de M arkov

Pr. Chaabane Djamal

I ∀h, i, j, k ∈ E on écrit I P (Xn+1 = i, Xn+2 = j, Xn+3 = k | Xn = h) = phi pij pjk I On a

M&R

Chaînes de Markov

P (Xn+3 = k | Xn = h)

= =

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

X i∈E X

phi

X

j∈E phi p(2) ik

i∈E

Illustrations

= p(3) hk

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

p(2) est l’élément (i, k) de ik

la matrice P2

p(3) est l’élément (h, k) de la matrice P3 hk

pij pjk

C aînes de M arkov

Pr. Chaabane Djamal

Proposition

∀m ∈ N on a M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (Xn+m = j | Xn = i) =

p(m) ij ∀i, j ∈ E, n ∈ N

C aînes de M arkov

Pr. Chaabane Djamal

Proposition

∀m ∈ N on a M&R

Chaînes de Markov

P (Xn+m = j | Xn = i) =

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Pn+m = Pn Pm

p(m) ij ∀i, j ∈ E, n ∈ N

C aînes de M arkov

Pr. Chaabane Djamal

Proposition

∀m ∈ N on a M&R

Chaînes de Markov

P (Xn+m = j | Xn = i) =

p(m) ij ∀i, j ∈ E, n ∈ N

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Pn+m = Pn Pm

=⇒ p(n+m) = ij

X k∈E

p(n) p(m) ik kj

C aînes de M arkov

Pr. Chaabane Djamal

Proposition

∀m ∈ N on a M&R

Chaînes de Markov

P (Xn+m = j | Xn = i) =

p(m) ij ∀i, j ∈ E, n ∈ N

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations

Pn+m = Pn Pm

=⇒ p(n+m) = ij

X

p(n) p(m) ik kj

k∈E

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Relation de CHAPMAN-KOLMOGOROV

Plan Pr. Chaabane Djamal

1 Chaînes de Markov

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov 2 Illustrations

Illustration 1

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

3 Classification des états

Passage par un état fixe 4 Etude asymptotique 5 Résultats dŠalgèbre linéaire pour les chaînes de Markov

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

E xemple 1

Soit X = {Xn | n ∈ N} une chaîne de Markov avec E = {a, b, c} et

   0.50 0.25 0.25    P =  0.67 0.00 0.33    0.60 0.40 0.00

Pr. Chaabane Djamal

E xemple 1

Soit X = {Xn | n ∈ N} une chaîne de Markov avec E = {a, b, c} et

   0.50 0.25 0.25    P =  0.67 0.00 0.33    0.60 0.40 0.00

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

I Objectif

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (X1 = b, X2 = c, X3 = a, X4 = c, X5 = a, X6 = c, X7 = b

Pr. Chaabane Djamal

E xemple 1

Soit X = {Xn | n ∈ N} une chaîne de Markov avec E = {a, b, c} et

   0.50 0.25 0.25    P =  0.67 0.00 0.33    0.60 0.40 0.00

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

I Objectif

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (X1 = b, X2 = c, X3 = a, X4 = c, X5 = a, X6 = c, X7 = b | X0 = c)

Pr. Chaabane Djamal

E xemple 1

Soit X = {Xn | n ∈ N} une chaîne de Markov avec E = {a, b, c} et

   0.50 0.25 0.25    P =  0.67 0.00 0.33    0.60 0.40 0.00

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

I Objectif

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (X1 = b, X2 = c, X3 = a, X4 = c, X5 = a, X6 = c, X7 = b | X0 = c) = pcb pbc pca pac pca pac pcb

Pr. Chaabane Djamal

E xemple 1

Soit X = {Xn | n ∈ N} une chaîne de Markov avec E = {a, b, c} et

   0.50 0.25 0.25    P =  0.67 0.00 0.33    0.60 0.40 0.00

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

I Objectif

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (X1 = b, X2 = c, X3 = a, X4 = c, X5 = a, X6 = c, X7 = b | X0 = c) = pcb pbc pca pac pca pac pcb = 0.40 × 0.33 × 0.60 × 0.25 × 0.60 × 0.25 × 0.40

Pr. Chaabane Djamal

E xemple 1

Soit X = {Xn | n ∈ N} une chaîne de Markov avec E = {a, b, c} et

   0.50 0.25 0.25    P =  0.67 0.00 0.33    0.60 0.40 0.00

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

I Objectif

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P (X1 = b, X2 = c, X3 = a, X4 = c, X5 = a, X6 = c, X7 = b | X0 = c) = pcb pbc pca pac pca pac pcb = 0.40 × 0.33 × 0.60 × 0.25 × 0.60 × 0.25 × 0.40 = 0.0012

Processus de Bernoulli

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

E xemple 2

Nous considérons une succession de tirages de Bernoulli, θ est la probabilité de succès, Nn est le nombre de succès en n expériences Bernoulli indépendantes. On a

Processus de Bernoulli

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

E xemple 2

Nous considérons une succession de tirages de Bernoulli, θ est la probabilité de succès, Nn est le nombre de succès en n expériences Bernoulli indépendantes. On a P (Nn+m − Nn = k | N0 , · · · , Nn )

Processus de Bernoulli

Pr. Chaabane Djamal

M&R

Chaînes de Markov

E xemple 2

Nous considérons une succession de tirages de Bernoulli, θ est la probabilité de succès, Nn est le nombre de succès en n expériences Bernoulli indépendantes. On a P (Nn+m − Nn = k | N0 , · · · , Nn )

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

k k = P (Nn+m − Nn = k) = Cm θ (1 − θ)(m−k)

Processus de Bernoulli

Pr. Chaabane Djamal

M&R

Chaînes de Markov

E xemple 2

Nous considérons une succession de tirages de Bernoulli, θ est la probabilité de succès, Nn est le nombre de succès en n expériences Bernoulli indépendantes. On a P (Nn+m − Nn = k | N0 , · · · , Nn )

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations

k k = P (Nn+m − Nn = k) = Cm θ (1 − θ)(m−k)

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc, {Nn | n ∈ N} est une chaîne de Markov homogène.

Processus de Bernoulli

Pr. Chaabane Djamal

M&R

Chaînes de Markov

E xemple 2

Nous considérons une succession de tirages de Bernoulli, θ est la probabilité de succès, Nn est le nombre de succès en n expériences Bernoulli indépendantes. On a P (Nn+m − Nn = k | N0 , · · · , Nn )

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations

k k = P (Nn+m − Nn = k) = Cm θ (1 − θ)(m−k)

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc, {Nn | n ∈ N} est une chaîne de Markov homogène. La distribution initiale : π = (π0 , π1 · · · ) avec π0 = P (N0 = 0) = 1 et πj = 0 ∀j ≥ 1

Processus de Bernoulli

Pr. Chaabane Djamal

E xemple 2 (suite) M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

L’ensemble des états est E = {0, 1, 2, · · · } Les probabilités de transition sont données par :

Processus de Bernoulli

Pr. Chaabane Djamal

E xemple 2 (suite) M&R

L’ensemble des états est E = {0, 1, 2, · · · } Les probabilités de transition sont données par :

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

pij = P (Nn+1

  θ si j = i + 1    1 − θ si j=i = j | Nn = i) =     0 ailleurs

Processus de Bernoulli

Pr. Chaabane Djamal

E xemple 2 (suite)

La matrice des probabilités de transition M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

 θ ···  1 − θ  0 1−θ θ   . .. .. . . . P =  .    0

··· ··· .. . ..

.

        

Marche aléatoire

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Supposons qu’une particule se déplace entre les positions sur une ligne d’une position à la fois.

Marche aléatoire

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Supposons qu’une particule se déplace entre les positions sur une ligne d’une position à la fois. I Les positions sur la ligne sont marquées par des nombres entiers consécutifs.

Marche aléatoire

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Supposons qu’une particule se déplace entre les positions sur une ligne d’une position à la fois. I Les positions sur la ligne sont marquées par des nombres entiers consécutifs. I À chaque époque, la particule se déplace d’une position vers la droite avec la probabilité p, ou une position vers la gauche avec la probabilité 1 − p.

Marche aléatoire

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Supposons qu’une particule se déplace entre les positions sur une ligne d’une position à la fois. I Les positions sur la ligne sont marquées par des nombres entiers consécutifs. I À chaque époque, la particule se déplace d’une position vers la droite avec la probabilité p, ou une position vers la gauche avec la probabilité 1 − p. I La particule continue à se déplacer, soit à droite ou à gauche, jusqu’à ce qu’elle atteigne l’une des deux positions extrêmes appelées barrières.

Marche aléatoire

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Supposons qu’une particule se déplace entre les positions sur une ligne d’une position à la fois. I Les positions sur la ligne sont marquées par des nombres entiers consécutifs. I À chaque époque, la particule se déplace d’une position vers la droite avec la probabilité p, ou une position vers la gauche avec la probabilité 1 − p. I La particule continue à se déplacer, soit à droite ou à gauche, jusqu’à ce qu’elle atteigne l’une des deux positions extrêmes appelées barrières. I Etant donné que le mouvement de la particule ne dépend que de sa position actuelle, et non pas sur l’une de ses positions antérieures, le procédé peut être modélisé sous la forme d’une chaîne de Markov.

Marche aléatoire

Pr. Chaabane Djamal

I Cette chaîne est appelée marche aléatoire, car il peut décrire le mouvement instable d’un individu en état d’ébriété. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Marche aléatoire

Pr. Chaabane Djamal

I Cette chaîne est appelée marche aléatoire, car il peut décrire le mouvement instable d’un individu en état d’ébriété. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Les états, représentés par des nombres entiers consécutifs, sont les positions possibles de la particule sur la ligne.

Marche aléatoire

Pr. Chaabane Djamal

I Cette chaîne est appelée marche aléatoire, car il peut décrire le mouvement instable d’un individu en état d’ébriété. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Les états, représentés par des nombres entiers consécutifs, sont les positions possibles de la particule sur la ligne. I Lorsque la particule est en position i, la marche aléatoire est dans l’état i. Par conséquent, l’état Xn = i désigne la position de la particule après n mouvments.

Marche aléatoire

Pr. Chaabane Djamal

I Cette chaîne est appelée marche aléatoire, car il peut décrire le mouvement instable d’un individu en état d’ébriété. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Les états, représentés par des nombres entiers consécutifs, sont les positions possibles de la particule sur la ligne. I Lorsque la particule est en position i, la marche aléatoire est dans l’état i. Par conséquent, l’état Xn = i désigne la position de la particule après n mouvments. I Considérons une marche aléatoire de cinq états représentés sur la figure ci-dessous avec l’espace état E = {0, 1, 2, 3, 4}.

Marche aléatoire

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Pour un état i ∈ E avec 0 < i < 4, on a : P(Xn+1 = i + 1 | Xn = i) = p P(Xn+1 = i − 1 | Xn = i) = q = 1 − p. P(Xn+1 = j | Xn = i) = 0 pour j , i + 1 et j , i − 1. Pour i = ou i = 4 états barrière

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction

Barrière absorbante Quand une particule atteint une barrière absorbante, il y reste. Ainsi, une barrière absorbante est représentée par un état, qui est appelé un état absorbant. La matrice de probabilité de transition pour une marche aléatoire à cinq états avec deux barrières absorbantes, représentés par les Etats absorbant 0 et 4, est

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

    P =   

1 q 0 0 0

0 0 q 0 0

0 p 0 q 0

0 0 p 0 0

0 0 0 p 1

       

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Barrières réfléchissantes Quand une particule atteint une barrière réfléchissante, il entre dans l’état adjacent sur la prochaine transition. La matrice de probabilité de transition pour une chaîne de cinq état de marche aléatoire avec deux barrières réfléchissantes, représenté par les états 0 et 4, est    0 1 0 0 0     q 0 p 0 0  P =  0 q 0 p 0     0 0 q 0 p  0 0 0 1 0

Plan Pr. Chaabane Djamal

1 Chaînes de Markov

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov 2 Illustrations

Illustration 1

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

3 Classification des états

Passage par un état fixe 4 Etude asymptotique 5 Résultats dŠalgèbre linéaire pour les chaînes de Markov

Passage par un état fixe Pr. Chaabane Djamal

j ∈ E un état fixe M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit j un état fixé dans une chaîne de Markov homogène {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de probabilités de transition P.

Passage par un état fixe Pr. Chaabane Djamal

j ∈ E un état fixe M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit j un état fixé dans une chaîne de Markov homogène {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de probabilités de transition P. I On s’intéresse à la probabilité du premier passage par l’état j.

Passage par un état fixe Pr. Chaabane Djamal

j ∈ E un état fixe M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit j un état fixé dans une chaîne de Markov homogène {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de probabilités de transition P. I On s’intéresse à la probabilité du premier passage par l’état j. I On écrit,

Passage par un état fixe Pr. Chaabane Djamal

j ∈ E un état fixe M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit j un état fixé dans une chaîne de Markov homogène {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de probabilités de transition P. I On s’intéresse à la probabilité du premier passage par l’état j. I On écrit,
P XT1 = j|X0 = i =

Passage par un état fixe Pr. Chaabane Djamal

j ∈ E un état fixe M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit j un état fixé dans une chaîne de Markov homogène {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de probabilités de transition P. I On s’intéresse à la probabilité du premier passage par l’état j. I On écrit,
P XT1 = j|X0 = i = P (T1 = k|X0 = i) = Pi (T1 = k) =

Passage par un état fixe Pr. Chaabane Djamal

j ∈ E un état fixe M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I Soit j un état fixé dans une chaîne de Markov homogène {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de probabilités de transition P. I On s’intéresse à la probabilité du premier passage par l’état j. I On écrit,
P XT1 = j|X0 = i = P (T1 = k|X0 = i) = Pi (T1 = k) = ϑij (k) .

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Soit j ∈ E, un état fixe.

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (1)

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (1) = Pi (T1 = 1) =

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (1) = Pi (T1 = 1) = Pi (X1 = j) =

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (1) = Pi (T1 = 1) = Pi (X1 = j) = P (X1 = j|X0 = i)

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (1) = Pi (T1 = 1) = Pi (X1 = j) = P (X1 = j|X0 = i) = pij

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction

ϑij (1) = Pi (T1 = 1) = Pi (X1 = j) = P (X1 = j|X0 = i) = pij

• Pour k ≥ 2 ;

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (k) = P (X1 , j, X2 , j, · · · , Xk−1 , j, Xk = j|X0 = i)

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction

ϑij (1) = Pi (T1 = 1) = Pi (X1 = j) = P (X1 = j|X0 = i) = pij

• Pour k ≥ 2 ;

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (k) = P (X1 , j, X2 , j, · · · , Xk−1 , j, Xk = j|X0 = i) X = P (X1 = b, X2 , j, · · · , Xk−1 , j, Xk = j|X0 = i) b∈E\{j}

Passage par un état fixe Pr. Chaabane Djamal

• Soit j ∈ E, un état fixe. • Pour k = 1 ;

M&R

Chaînes de Markov Introduction

ϑij (1) = Pi (T1 = 1) = Pi (X1 = j) = P (X1 = j|X0 = i) = pij

• Pour k ≥ 2 ;

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑij (k) = P (X1 , j, X2 , j, · · · , Xk−1 , j, Xk = j|X0 = i) X = P (X1 = b, X2 , j, · · · , Xk−1 , j, Xk = j|X0 = i) b∈E\{j}

=

X

P (X1 = b|X0 = i) ×

b∈E\{j}

P (X2 , j, · · · , Xk−1 , j, Xk = j|X0 = i, X1 = b)

Passage par un état fixe Pr. Chaabane Djamal

ϑij (k) =

X b∈E\{j}

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Pib × P (X2 , j, · · · , Xk−1 , j, Xk = j|X1 = b)

Passage par un état fixe Pr. Chaabane Djamal

ϑij (k) =

X

Pib × P (X2 , j, · · · , Xk−1 , j, Xk = j|X1 = b)

b∈E\{j} M&R

= Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

X b∈E\{j}

Pib × ϑbj (k − 1)

Passage par un état fixe Pr. Chaabane Djamal

ϑij (k) =

X

Pib × P (X2 , j, · · · , Xk−1 , j, Xk = j|X1 = b)

b∈E\{j} M&R

=

Matrices Stochastiques

Pib × ϑbj (k − 1)

b∈E\{j}

Chaînes de Markov Introduction

X

Donc,

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

  pij       X ϑij (k) =    Pib × ϑbj (k − 1)     b∈E\{j}

si k = 1 si k ≥ 2

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

E xemple

On considère une chaîne de Markov avec E = {0, 1, 2} et    1 0 0   1 1 1     2 6 3   1 3 1  3 5 15

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Soit j un état fixé dans une chaîne de Markov {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de transition P.

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Soit j un état fixé dans une chaîne de Markov {Xn }n∈N d’espace des états E, de distribution initiale π0 et de matrice de transition P. Proposition On a :

vij = Pij +

X b∈E\{j}

Pib vbj

(1)

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Soit Nj (ω) le nombre de passage par un état fixé dans une chaîne de Markov {Xn}n∈N pour toute réalisation ω ∈ Ω.

Passage par un état fixe Pr. Chaabane Djamal

M&R

Soit Nj (ω) le nombre de passage par un état fixé dans une chaîne de Markov {Xn}n∈N pour toute réalisation ω ∈ Ω. * Nj (ω) = m

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Soit Nj (ω) le nombre de passage par un état fixé dans une chaîne de Markov {Xn}n∈N pour toute réalisation ω ∈ Ω. * Nj (ω) = m m (T1 (ω) < ∞), (T2 (ω) < ∞), ..., (Tm (ω) < ∞) et (Tm+1 (ω) = ∞) avec probabilité

P ((T1 (ω) < ∞), (T2 (ω) < ∞), ..., (Tm (ω) < ∞) et (Tm+1 (ω) = ∞))

Passage par un état fixe Pr. Chaabane Djamal

* Les évènements M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

(T1 < ∞), (T2 − T1 < ∞), ..., (Tm − Tm−1 < ∞) (Tm+1 − Tm = ∞)

Passage par un état fixe Pr. Chaabane Djamal

* Les évènements M&R

Chaînes de Markov Introduction

(T1 < ∞), (T2 − T1 < ∞), ..., (Tm − Tm−1 < ∞) (Tm+1 − Tm = ∞) sont indépendants et de probabilités en commençant

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

l’évolution de i

Passage par un état fixe Pr. Chaabane Djamal

* Les évènements M&R

Chaînes de Markov Introduction

(T1 < ∞), (T2 − T1 < ∞), ..., (Tm − Tm−1 < ∞) (Tm+1 − Tm = ∞) sont indépendants et de probabilités en commençant

Matrices Stochastiques Relation de Chapman-Kolmogorov

l’évolution de i

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

vij , vjj , ..., vjj et (1 − vjj ) respectivement.

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov

Proposition Soit Nj le nombre de passage par l’état j. Alors Pj (Nj = m) = vjjm−1 (1 − vjj ),

m = 1, 2, ...;

(2)

1 − vij m=0 vij vjjm−1 (1 − vjj ) m = 1, 2, ...

(3)

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

et pour i , j

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

( Pi (Nj = m) =

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Pour vjj < 1 on a :

Passage par un état fixe Pr. Chaabane Djamal

• Pour vjj < 1 on a : ∞ X

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

m=1

Pj (Nj = m) =

∞ X m=1

vjjm−1 (1 − vjj )

Passage par un état fixe Pr. Chaabane Djamal

• Pour vjj < 1 on a : ∞ X

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

m=1

Pj (Nj = m) =

∞ X

vjjm−1 (1 − vjj )

m=1

= (1 − vjj )

∞ X m=1

vm−1 jj

Passage par un état fixe Pr. Chaabane Djamal

• Pour vjj < 1 on a : ∞ X

M&R

Chaînes de Markov

m=1

Pj (Nj = m) =

∞ X

vjjm−1 (1 − vjj )

m=1

= (1 − vjj )

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

vm−1 jj

m=1

Introduction Matrices Stochastiques

∞ X

= (1 − vjj )

1 =1 1 − vjj

Passage par un état fixe Pr. Chaabane Djamal

• Pour vjj < 1 on a : ∞ X

M&R

Pj (Nj = m) =

m=1

∞ X

vjjm−1 (1 − vjj )

m=1

= (1 − vjj )

Chaînes de Markov

= (1 − vjj )

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

vm−1 jj

m=1

Introduction

Classification des états

∞ X

• Pour vjj = 1 on a :

1 =1 1 − vjj

Passage par un état fixe Pr. Chaabane Djamal

• Pour vjj < 1 on a : ∞ X

M&R

Pj (Nj = m) =

m=1

∞ X

vjjm−1 (1 − vjj )

m=1

= (1 − vjj )

Chaînes de Markov

∞ X

vm−1 jj

m=1

Introduction

= (1 − vjj )

Matrices Stochastiques Relation de Chapman-Kolmogorov

1 =1 1 − vjj

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Pour vjj = 1 on a : ∞ X m=1

Pj (Nj = m) =

∞ X m=1

1m−1 × 0 = 0

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Proposition On a :

( Pj (Nj < ∞) =

1 si vjj < 1 0 si vjj = 1

(4)

Passage par un état fixe Pr. Chaabane Djamal

Proposition On a : Pj (Nj < ∞) =

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

(

• Si vjj = 1,

1 si vjj < 1 0 si vjj = 1

(4)

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Proposition On a :

( Pj (Nj < ∞) =

1 si vjj < 1 0 si vjj = 1

• Si vjj = 1, alors Nj = ∞ certainement

(4)

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Proposition On a :

( Pj (Nj < ∞) =

1 si vjj < 1 0 si vjj = 1

• Si vjj = 1, alors Nj = ∞ certainement Pj (Nj = ∞) = 1 − Pj (Nj < ∞) = 1 − 0 = 1. Donc, Ej (Nj ) = ∞

(4)

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Proposition On a :

( Pj (Nj < ∞) =

1 si vjj < 1 0 si vjj = 1

(4)

• Si vjj = 1, alors Nj = ∞ certainement Pj (Nj = ∞) = 1 − Pj (Nj < ∞) = 1 − 0 = 1. Donc, Ej (Nj ) = ∞     1 ; probabilité de • Si vjj < 1, Nj ∼ Geom  Ej (Nj ) = p = 1 − vjj  succès est p = 1 − vjj

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Proposition On a :

( Pj (Nj < ∞) =

1 si vjj < 1 0 si vjj = 1

(4)

• Si vjj = 1, alors Nj = ∞ certainement Pj (Nj = ∞) = 1 − Pj (Nj < ∞) = 1 − 0 = 1. Donc, Ej (Nj ) = ∞     1 ; probabilité de • Si vjj < 1, Nj ∼ Geom  Ej (Nj ) = p = 1 − vjj  succès est p = 1 − vjj • La matrice potentielle est : R

= (rij )i,j∈E

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Corollaire On a : 1 1 − vjj + rij = vij rjj + rjj =

si i , j

Passage par un état fixe Pr. Chaabane Djamal

M&R

On a : ∀ω ∈ Ω : Nj (ω) =

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

∞ X

=j (Xn (ω))

n=0

avec

( =j (Xn (ω)) =

1 0

si Xn (ω) = j si Xn (ω) , j

Passage par un état fixe Pr. Chaabane Djamal

On a : rij = Ei [

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

∞ X n=0

=j (Xn )]

Passage par un état fixe Pr. Chaabane Djamal

On a : rij = Ei [

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

=j (Xn )]

n=0

M&R

Chaînes de Markov

∞ X

=

∞ X n=0

Ei [=j (Xn )]

Passage par un état fixe Pr. Chaabane Djamal

On a : rij = Ei [ =

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

=j (Xn )]

n=0

M&R

Chaînes de Markov

∞ X

=

∞ X n=0 ∞ X n=0

Ei [=j (Xn )] Pi (Xn = j) =

∞ X n=0

P(Xn = j|X0 = i)

Passage par un état fixe Pr. Chaabane Djamal

On a : rij = Ei [ =

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

=

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

=j (Xn )]

n=0

M&R

Chaînes de Markov

∞ X

=

∞ X n=0 ∞ X n=0 ∞ X n=0

Ei [=j (Xn )] Pi (Xn = j) =

∞ X n=0

Pnij

P(Xn = j|X0 = i)

Passage par un état fixe Pr. Chaabane Djamal

On a : rij = Ei [ =

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

=

Illustrations Illustration 1

Classification des états

=j (Xn )]

n=0

M&R

Chaînes de Markov

∞ X

=

∞ X n=0 ∞ X n=0 ∞ X

Ei [=j (Xn )] Pi (Xn = j) =

∞ X

P(Xn = j|X0 = i)

n=0

Pnij

n=0

Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

R = I + P + P2 + ..

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

On a : RP = P + P2 + P3 + ... = R − I

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

On a : RP = P + P2 + P3 + ... = R − I PR = P + P2 + P3 + ... = R − I

Passage par un état fixe Pr. Chaabane Djamal

M&R

On a : RP = P + P2 + P3 + ... = R − I PR = P + P2 + P3 + ... = R − I

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc

Passage par un état fixe Pr. Chaabane Djamal

M&R

On a : RP = P + P2 + P3 + ... = R − I PR = P + P2 + P3 + ... = R − I

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc *

Passage par un état fixe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction

On a : RP = P + P2 + P3 + ... = R − I PR = P + P2 + P3 + ... = R − I

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc * R(I − P) = (I − P)R = I

Rappels Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Figure: Passage par un état fixé dans E

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Étant donnée une chaîne de Markov {Xn}n∈N d’espace des états E, de distribution initiale π0 et de matrice de transition P. Soit T l’instant du premier passage par un état fixé j, j ∈ E et Nj le nombre totale de passage par l’état j.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction

Étant donnée une chaîne de Markov {Xn}n∈N d’espace des états E, de distribution initiale π0 et de matrice de transition P. Soit T l’instant du premier passage par un état fixé j, j ∈ E et Nj le nombre totale de passage par l’état j. Définition * L’état j est dit récurrent (persistant) si

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Pj {T < ∞} = 1

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction

Étant donnée une chaîne de Markov {Xn}n∈N d’espace des états E, de distribution initiale π0 et de matrice de transition P. Soit T l’instant du premier passage par un état fixé j, j ∈ E et Nj le nombre totale de passage par l’état j. Définition * L’état j est dit récurrent (persistant) si

Matrices Stochastiques Relation de Chapman-Kolmogorov

Pj {T < ∞} = 1

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Sinon, si Pj {T = ∞} > 0 alors j est transitoire .

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction

Étant donnée une chaîne de Markov {Xn}n∈N d’espace des états E, de distribution initiale π0 et de matrice de transition P. Soit T l’instant du premier passage par un état fixé j, j ∈ E et Nj le nombre totale de passage par l’état j. Définition * L’état j est dit récurrent (persistant) si

Matrices Stochastiques Relation de Chapman-Kolmogorov

Pj {T < ∞} = 1

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Sinon, si Pj {T = ∞} > 0 alors j est transitoire . * Un état récurrent j est dit nul si Ej (T) = +∞.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction

Étant donnée une chaîne de Markov {Xn}n∈N d’espace des états E, de distribution initiale π0 et de matrice de transition P. Soit T l’instant du premier passage par un état fixé j, j ∈ E et Nj le nombre totale de passage par l’état j. Définition * L’état j est dit récurrent (persistant) si

Matrices Stochastiques Relation de Chapman-Kolmogorov

Pj {T < ∞} = 1

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Sinon, si Pj {T = ∞} > 0 alors j est transitoire . * Un état récurrent j est dit nul si Ej (T) = +∞. * Sinon il est dit non nul .

C lassification Pr. Chaabane Djamal

Définition (suite) M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Un état récurrent j est dit périodique de période δ s’il existe un entiers n; n ∈ N∗ avec δ ≥ 2 est le plus grand entier tel que Pj {T = nδ pour n ≥ 1} = 1

C lassification Pr. Chaabane Djamal

Définition (suite) M&R

Chaînes de Markov Introduction Matrices Stochastiques

* Un état récurrent j est dit périodique de période δ s’il existe un entiers n; n ∈ N∗ avec δ ≥ 2 est le plus grand entier tel que Pj {T = nδ pour n ≥ 1} = 1

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Sinon, s’il n’existe pas un tel n avec δ ≥ 2, j est dit apériodique .

C lassification Pr. Chaabane Djamal

• Si j récurrent M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

• Si j récurrent ⇒ vjj = 1 M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain

C lassification Pr. Chaabane Djamal

M&R

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain • Si j est transitoire

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

M&R

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain • Si j est transitoire ⇒ vjj < 1

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain • Si j est transitoire ⇒ vjj < 1 ⇒ La probabilité de quitter sans retour 1 − vjj > 0

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain • Si j est transitoire ⇒ vjj < 1 ⇒ La probabilité de quitter sans retour 1 − vjj > 0 ⇒ rjj < ∞

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain • Si j est transitoire ⇒ vjj < 1 ⇒ La probabilité de quitter sans retour 1 − vjj > 0 ⇒ rjj < ∞ • rjj < ∞;

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain • Si j est transitoire ⇒ vjj < 1 ⇒ La probabilité de quitter sans retour 1 − vjj > 0 ⇒ rjj < ∞ • rjj < ∞;donc X rij = vij rjj < rjj < ∞ ∀i ∈ E; pnij < ∞ ⇒ Pnij → 0. n≥0

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

• Si j récurrent ⇒ vjj = 1⇒ rjj = +∞ ⇒ {Nj = ∞} est presque certain • Si j est transitoire ⇒ vjj < 1 ⇒ La probabilité de quitter sans retour 1 − vjj > 0 ⇒ rjj < ∞ • rjj < ∞;donc X rij = vij rjj < rjj < ∞ ∀i ∈ E; pnij < ∞ ⇒ Pnij → 0. n≥0

• Si j est un état récurrent nul, donc Ej (T) = ∞ (durée moyenne entre deux retours vers j est infinie) → Pnij → 0.

C lassification Pr. Chaabane Djamal

Théorème ) Si j est transitoire ou récurrent nul alors M&R

lim Pnij = 0

n→∞ Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

(5)

C lassification Pr. Chaabane Djamal

Théorème ) Si j est transitoire ou récurrent nul alors M&R

lim Pnij = 0

n→∞

(5)

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

) Si j est un état récurrent apériodique, alors πj = lim Pnij > 0 n→∞

(6)

C lassification Pr. Chaabane Djamal

Théorème ) Si j est transitoire ou récurrent nul alors lim Pnij = 0

M&R

n→∞

(5)

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

) Si j est un état récurrent apériodique, alors

Illustrations

πj = lim Pnij > 0

(6)

lim Pnij = vij πj

(7)

n→∞

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

) Pour tout i ∈ E

n→∞

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Définition (suite) * accessible :l’état j est accessible depuis l’état i si il existe au moins un chemin menant de i à j. Ce qui donne : ∃n ∈ N|pnij > 0.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Définition (suite) * accessible :l’état j est accessible depuis l’état i si il existe au moins un chemin menant de i à j. Ce qui donne : ∃n ∈ N|pnij > 0. * communiquant :les états i et j communique si il existe au moins de chemin menant de i à j et un chemin qui mène de j à i. ∃n ∈ N|pnij > 0 et ∃m ∈ N|pm ji > 0

C lassification Pr. Chaabane Djamal

Proposition i → j si et seulement si il existe n ∈ N tel que p(n) i,j > 0.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

Proposition i → j si et seulement si il existe n ∈ N tel que p(n) i,j > 0.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Proposition Si i → j et j → k alors i → k.

C lassification Pr. Chaabane Djamal

Proposition i → j si et seulement si il existe n ∈ N tel que p(n) i,j > 0.

M&R

Chaînes de Markov

Proposition Si i → j et j → k alors i → k.

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Si i → j, alors ∃r ≥ 0 | prij > 0.

C lassification Pr. Chaabane Djamal

Proposition i → j si et seulement si il existe n ∈ N tel que p(n) i,j > 0.

M&R

Chaînes de Markov

Proposition Si i → j et j → k alors i → k.

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Si i → j, alors ∃r ≥ 0 | prij > 0. r Si j → k, alors ∃s ≥ 0 | psjk > 0.

C lassification Pr. Chaabane Djamal

Proposition i → j si et seulement si il existe n ∈ N tel que p(n) i,j > 0.

M&R

Chaînes de Markov

Proposition Si i → j et j → k alors i → k.

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Si i → j, alors ∃r ≥ 0 | prij > 0. r Si j → k, alors ∃s ≥ 0 | psjk > 0. r Pour n = r + s, on a : pnik =

X α∈E

priα psαk ≥ prij psjk > 0.

C lassification Pr. Chaabane Djamal

Proposition i → j si et seulement si il existe n ∈ N tel que p(n) i,j > 0.

M&R

Chaînes de Markov

Proposition Si i → j et j → k alors i → k.

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Preuve r Si i → j, alors ∃r ≥ 0 | prij > 0. r Si j → k, alors ∃s ≥ 0 | psjk > 0. r Pour n = r + s, on a : pnik =

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc

i→k

X α∈E

priα psαk ≥ prij psjk > 0. 

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Définition Un ensemble d’états C est dit fermé si : ∀i ∈ C et si i → j alors j ∈ C.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Définition Un ensemble d’états C est dit fermé si : ∀i ∈ C et si i → j alors j ∈ C. Définition • Un ensemble C fermé est irréductible si aucun sous-ensemble de C n’est fermé.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Définition Un ensemble d’états C est dit fermé si : ∀i ∈ C et si i → j alors j ∈ C. Définition • Un ensemble C fermé est irréductible si aucun sous-ensemble de C n’est fermé. • Une chaîne de Markov est irréductible si son ensemble des états est l’unique ensemble fermé.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Définition Un ensemble d’états C est dit fermé si : ∀i ∈ C et si i → j alors j ∈ C. Définition • Un ensemble C fermé est irréductible si aucun sous-ensemble de C n’est fermé. • Une chaîne de Markov est irréductible si son ensemble des états est l’unique ensemble fermé.

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Définition Un état i est dit absorbant si {i} est un ensemble fermée.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C ritère

Un état j est absorbant si et seulement si pjj = 1

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C ritère

Un état j est absorbant si et seulement si pjj = 1 Proposition Soit C un sous-ensemble d’un ensemble des états E d’une chaîne de Markov. La sous-matrice Q correspondante à C est stochastique.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

G raphe associé

Soit une chaîne de Markov (E, P). Le graphe orienté G = (X, U) représsente la chaîne de Markov si: I X l’ensemble de sommets est en bijection avec l’ensemble des états E.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

G raphe associé

Soit une chaîne de Markov (E, P). Le graphe orienté G = (X, U) représsente la chaîne de Markov si: I X l’ensemble de sommets est en bijection avec l’ensemble des états E. I ∀a, b ∈ E,

(a, b) ∈ U si pab > 0

C lassification Pr. Chaabane Djamal

Exemple Considérons la chaîne de Markov suivante : M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Cette chaîne est irréductible car tous les états communiquent. Bien que p13 = 0, p(n) > 0 pour n ≥ 2. 13

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Exemple La matrice de probabilités de transition associée 1 0.5 0.5 0 P = 2 0.5 0.25 0.25 3 0 0.33 0.67

C lassification Pr. Chaabane Djamal

Exemple Considérons la chaîne de Markov suivante : M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

a b P= c d e

a 0.5 0 0 0.25 0.33

b 0 0.25 0 0.50 0

c 0.5 0 0.33 0 0.33

d 0 0.75 0 0.25 0

e 0 0 0.67 0 0.33

Les classes fermées : {a, c, e}, {a, b, c, d, e} et donc la chaîne n’est pas irréductible.

C lassification Pr. Chaabane Djamal

Lemme M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

Lemme Si j est un état récurrent et j → k, M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

Lemme Si j est un état récurrent et j → k, alors k → j M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C lassification Pr. Chaabane Djamal

Lemme Si j est un état récurrent et j → k, alors k → jet vkj = 1. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soit j un état récurent, et j → k, k ∈ E sans retour à j.

C lassification Pr. Chaabane Djamal

Lemme Si j est un état récurrent et j → k, alors k → jet vkj = 1. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soit j un état récurent, et j → k, k ∈ E sans retour à j. r On pose α; α > 0 la probabilité correspondante.

C lassification Pr. Chaabane Djamal

Lemme Si j est un état récurrent et j → k, alors k → jet vkj = 1. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soit j un état récurent, et j → k, k ∈ E sans retour à j. r On pose α; α > 0 la probabilité correspondante. r Une fois le processus est à k, la probabilité de ne pas retourner à j est 1 − vkj .

C lassification Pr. Chaabane Djamal

Lemme Si j est un état récurrent et j → k, alors k → jet vkj = 1. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soit j un état récurent, et j → k, k ∈ E sans retour à j. r On pose α; α > 0 la probabilité correspondante. r Une fois le processus est à k, la probabilité de ne pas retourner à j est 1 − vkj . r La probabilité de ne pas retourner à j à partir de j est la probabilité d’être dans un état quelconque de E (k est l’un de ces états) et puis ne pas retourner à j à partir de cet état.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Preuve (Suite) r Donc, 1 − vjj = S
T ne pas retourner à j de i} d’où Prob{ i∈E être à l’état i 1 − vjj ≥ α × (1 − vkj ) ≥ 0.

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

α > 0 et j récurrent donc vjj = 1.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Preuve (Suite) r Donc, 1 − vjj = S
T ne pas retourner à j de i} d’où Prob{ i∈E être à l’état i 1 − vjj ≥ α × (1 − vkj ) ≥ 0.

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

α > 0 et j récurrent donc vjj = 1. r En conclusion,vkj = 1 et donc k → j.



C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Théorème A partir d’un état récurrent seulement les états récurrent peuvent être atteint

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Théorème A partir d’un état récurrent seulement les états récurrent peuvent être atteint

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r On pose β = prjk × pskj ;

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r On pose β = prjk × pskj ; r Comme {Xs+n+r = k} ⊃ {Xs = j, Xs+n = j, Xs+n+r = k},

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r On pose β = prjk × pskj ; r Comme {Xs+n+r = k} ⊃ {Xs = j, Xs+n = j, Xs+n+r = k}, r on a : s+n+r = P {X Pkk k s+n+r = k}

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r On pose β = prjk × pskj ; r Comme {Xs+n+r = k} ⊃ {Xs = j, Xs+n = j, Xs+n+r = k}, r on a : s+n+r = P {X Pkk k s+n+r = k} ≥ Pk {Xs = j, Xs+n = j, Xs+n+r = k}

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r On pose β = prjk × pskj ; r Comme {Xs+n+r = k} ⊃ {Xs = j, Xs+n = j, Xs+n+r = k}, r on a : s+n+r = P {X Pkk k s+n+r = k} ≥ Pk {Xs = j, Xs+n = j, Xs+n+r = k} = Pskj Pnjj Prjk

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r On pose β = prjk × pskj ; r Comme {Xs+n+r = k} ⊃ {Xs = j, Xs+n = j, Xs+n+r = k}, r on a : s+n+r = Pkk ≥ = =

Pk {Xs+n+r = k} Pk {Xs = j, Xs+n = j, Xs+n+r = k} Pskj Pnjj Prjk βPnjj

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X `=0

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P`kk

≥

∞ X `=r+s

P`kk

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X

P`kk

≥

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P`kk

`=r+s

`=0 Chaînes de Markov

∞ X

=

∞ X n=0

Pn+r+s kk

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X

P`kk

≥

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P`kk

`=r+s

`=0 Chaînes de Markov

∞ X

=

∞ X

Pn+r+s kk

n=0 ∞ X

≥ β

n=0

Pnjj

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X

P`kk

≥

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P`kk

`=r+s

`=0 Chaînes de Markov

∞ X

=

∞ X

Pn+r+s kk

n=0 ∞ X

≥ β

n=0

= βrjj

Pnjj

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X

P`kk

≥ =

Introduction

Relation de Chapman-Kolmogorov

Pn+r+s kk

≥ β

Illustrations

n=0

Illustration 1

= βrjj

Classification des états Passage par un état fixe

Résultats dŠalgèbre linéaire pour les chaînes de

∞ X

n=0 ∞ X

Matrices Stochastiques

Etude asymptotique

P`kk

`=r+s

`=0 Chaînes de Markov

∞ X

r j récurrent, alors rjj = ∞.

Pnjj

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X

P`kk

≥

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états

=

∞ X

Pn+r+s kk

n=0 ∞ X

≥ β

n=0

= βrjj

Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P`kk

`=r+s

`=0 Chaînes de Markov

∞ X

r j récurrent, alors rjj = ∞. Comme β > 0

Pnjj

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X

P`kk

≥

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états

P`kk

`=r+s

`=0 Chaînes de Markov

∞ X

=

∞ X

Pn+r+s kk

n=0 ∞ X

≥ β

Pnjj

n=0

= βrjj

Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

r j récurrent, alors rjj = ∞. Comme β > 0 donc rkk = ∞

C lassification Pr. Chaabane Djamal

Preuve r on a : M&R

rkk =

∞ X

P`kk

≥

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états

P`kk

`=r+s

`=0 Chaînes de Markov

∞ X

=

∞ X

Pn+r+s kk

n=0 ∞ X

≥ β

Pnjj

n=0

= βrjj

Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

r j récurrent, alors rjj = ∞. Comme β > 0 donc rkk = ∞ ⇒ k est récurrent. 

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Exemple La chaîne suivante possède une sous- chaîne de Markov irréductible {4, 5} :

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

C lassification Pr. Chaabane Djamal

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soient j un état récurrent et C l’ensemble de tous les états accessibles de j.

C lassification Pr. Chaabane Djamal

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soient j un état récurrent et C l’ensemble de tous les états accessibles de j. Manifestement, ceci forme un ensemble fermé.

C lassification Pr. Chaabane Djamal

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soient j un état récurrent et C l’ensemble de tous les états accessibles de j. Manifestement, ceci forme un ensemble fermé.On démontre que si i, k ∈ C alors i → k.

C lassification Pr. Chaabane Djamal

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soient j un état récurrent et C l’ensemble de tous les états accessibles de j. Manifestement, ceci forme un ensemble fermé.On démontre que si i, k ∈ C alors i → k. r Si i ∈ C, alors j → i.

C lassification Pr. Chaabane Djamal

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soient j un état récurrent et C l’ensemble de tous les états accessibles de j. Manifestement, ceci forme un ensemble fermé.On démontre que si i, k ∈ C alors i → k. r Si i ∈ C, alors j → i.Comme j est récurrent, d’après le lemme (1) ceci implique i → j.

C lassification Pr. Chaabane Djamal

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soient j un état récurrent et C l’ensemble de tous les états accessibles de j. Manifestement, ceci forme un ensemble fermé.On démontre que si i, k ∈ C alors i → k. r Si i ∈ C, alors j → i.Comme j est récurrent, d’après le lemme (1) ceci implique i → j. Donc Si k ∈ C un autre état, alors j → k.

C lassification Pr. Chaabane Djamal

Lemme Pour chaque état récurrent j il existe un ensemble fermé irréductible qui contient j.

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Preuve r Soient j un état récurrent et C l’ensemble de tous les états accessibles de j. Manifestement, ceci forme un ensemble fermé.On démontre que si i, k ∈ C alors i → k. r Si i ∈ C, alors j → i.Comme j est récurrent, d’après le lemme (1) ceci implique i → j. Donc Si k ∈ C un autre état, alors j → k. i→j∧j→k ⇒i→k 

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Théorème (IMPORTANT) Dans une chaîne de Markov les états récurrents peuvent être divisé d’une manière unique, en ensembles fermés irréductibles C1 , C2 , ...

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Remarque * En général une chaîne de Markov contient l’ensemble fermé des états récurrents C = C1 ∪ C2 ∪ ... et l’ensemble des états transitoires D.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov

Remarque * En général une chaîne de Markov contient l’ensemble fermé des états récurrents C = C1 ∪ C2 ∪ ... et l’ensemble des états transitoires D. * En vertu de la remarque ci-dessus, P peut être réécrite sous la forme :

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

      P =     

P1 0 0 0 P2 0 0 0 P3 · · · · · · · · · Q1 Q2 Q3

· · · · · · ·

· · · · · · ·

· 0 · 0 · 0 · · · · · · · Q

          

(8)

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Théorème Soit X une chaîne de Markov irréductible. Ou bien tous les états sont transitoires,ou récurrents nuls ou tous sont récurrents non nuls .

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Corollaire Soit C un ensemble irréductible fermé de cardinal finie. Alors aucun état n’est récurrent nul.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov

Corollaire Soit C un ensemble irréductible fermé de cardinal finie. Alors aucun état n’est récurrent nul.

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Corollaire Si C est un ensemble irréductible fermé de cardinal finie. Alors aucun état n’est transitoire.

C lassification Pr. Chaabane Djamal

Exemple M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Soit une chaîne de Markov avec espace d’états E = {1, 2, ..., 10} et matrice des probabilités de transition          P =        

1 2

0 1 0 0 0 0 0 0 0

0 1 3

0 0 0 0 0 0 1 1 3

1 2

0 0 0 0 0 0

0 0 0 1

0 0 0 0

1 3

1 3

0 0

0 0 0 0

1 4

1 4

0 0

0 0

1 3

0 0 0 0 0 1 0 0 0 0

0

0 0 0 0

1 4

0 0 0 0 0 0 0

0 0 0

1 4

3 4

0 0 0 0 0 0 0

0 0

0 0 0

3

2 3

0 0 0 0

1 3

0

             1   4   0  1

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Exemple {Nn ; n ∈ N} le processus qui représente le nombre de succès obtenu dans une succession de tirages de Bernoulli {0, 1, ..., n}

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Exemple {Nn ; n ∈ N} le processus qui représente le nombre de succès obtenu dans une succession de tirages de Bernoulli {0, 1, ..., n} Toutes les transitions sont de la forme j → j + 1∀j ∈ E donc

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Exemple {Nn ; n ∈ N} le processus qui représente le nombre de succès obtenu dans une succession de tirages de Bernoulli {0, 1, ..., n} Toutes les transitions sont de la forme j → j + 1∀j ∈ E donc tous les états sont transitoires.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov

Théorème Soit X une chaîne de Markov iréductible dont E sont ensemble des états et P; Considérons le système d’équations linéaires X ϑj = ϑi pij ∀j ∈ E. (9) i∈E

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états

Tous les états sont récurrents positifs si et seulement si il existe une solution ϑ vérifiant X ϑj = 1 (10) j∈E

Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Si (9) et (10) admettent une solution ϑ, alors ϑj > 0, ∀j ∈ E et elle est unique.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Théorème Soit X une chaîne de Markov irréductible dont E son ensemble des états et P;

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Théorème Soit X une chaîne de Markov irréductible dont E son ensemble des états et P; soit Q la matrice obtenue de P en éliminant la ligne et la colonne k pour un k de E.

C lassification Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Théorème Soit X une chaîne de Markov irréductible dont E son ensemble des états et P; soit Q la matrice obtenue de P en éliminant la ligne et la colonne k pour un k de E. Donc tous les états sont récurrents si et seulement si l’unique solution du système d’équations linéaires

Relation de Chapman-Kolmogorov

hi =

Illustrations Illustration 1

X

Qij hj

0 ≤ hj ≤ 1∀j ∈ E\{k}.

j∈E\{k}

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

est hi = 0

∀i ∈ E\{k}.∀j ∈ E et elle est unique.

A pplications Pr. Chaabane Djamal

Marche aléatoire

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Considérons le processus stochastiqueMARCHE ALÉATOIRE avec barrière . E = {0, 1, ..} et matrice de probabilité de transition     P =   

0 q 0 .. .

 1 0 0 0 . . .   0 p 0 0 . . .   q 0 p 0 . . .   .. .. .. .. . . . .

Pour 0 < p < 1 et q=1-p. Si le système est à l’état i à un instant n,

(11)

A pplications Pr. Chaabane Djamal

Marche aléatoire

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Considérons le processus stochastiqueMARCHE ALÉATOIRE avec barrière . E = {0, 1, ..} et matrice de probabilité de transition     P =   

0 q 0 .. .

 1 0 0 0 . . .   0 p 0 0 . . .   q 0 p 0 . . .   .. .. .. .. . . . .

(11)

Pour 0 < p < 1 et q=1-p. Si le système est à l’état i à un instant n, il passera à l’état i + 1 à l’instant n + 1 ou à l’état i − 1 sauf pour i = 0, le système passera sûrement à l’état 1.

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

A pplications Pr. Chaabane Djamal

Marche aléatoire M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

A pplications Pr. Chaabane Djamal

Marche aléatoire M&R

Tous les états sont communicants ⇒ la chaîne est irréductible Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

A pplications Pr. Chaabane Djamal

Marche aléatoire M&R

Tous les états sont communicants ⇒ la chaîne est irréductible Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

L’état {0} est périodique et de période égale à δ = 2 et comme la chaîne est irréductible ⇒ donc tous les états ont la même période.

A pplications Pr. Chaabane Djamal

Marche aléatoire M&R

Tous les états sont communicants ⇒ la chaîne est irréductible Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

L’état {0} est périodique et de période égale à δ = 2 et comme la chaîne est irréductible ⇒ donc tous les états ont la même période. Tous les états sont transitoires, récurrents positifs ou récurrents nuls.

A pplications Pr. Chaabane Djamal

Le système

* Résolvons le système des équations linéaires suivant M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑ0 ϑ1 ϑ2 ...

= = = ...

qϑ1 ϑ0 + qϑ2 pϑ1 + qϑ3 ...

(12)

A pplications Pr. Chaabane Djamal

Le système

* Résolvons le système des équations linéaires suivant ϑ0 ϑ1 ϑ2 ...

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

= = = ...

qϑ1 ϑ0 + qϑ2 pϑ1 + qϑ3 ...

(12)

La solution

* On obtient ϑj =

!j−1 1 p ϑ0 ; q q ϑ0 ≥ 0

j = 1, 2, . . .

(13)

Pr. Chaabane Djamal

Si p < q

* On obtient ∞ X M&R

j=0 Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

ϑj

 !j−1  ∞  X  1 p  ϑ0 = 2q ϑ0 ; = 1 +  q j=1 q q−p

(14)

Pr. Chaabane Djamal

Si p < q

* On obtient ∞ X M&R

ϑj

j=0 Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

 !j−1  ∞  X  1 p  ϑ0 = 2q ϑ0 ; = 1 +  q j=1 q q−p

En choisissant * ϑ0 =

Illustrations

q−p 1 p 1− = 2q 2 q

(14)

! (15)

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Si p < q

* On obtient

∞ X 1

ϑj = 1

(16)

Pr. Chaabane Djamal

M&R

Si p < q

* Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

!  1 p    1− si j = 0    q  2 ! !j−1 ϑj =    1 p p    1 − si j ≥ 1  2q q q

(17)

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Si p ≥ q

* Tous les états sont récurrents nuls ou transitoires. Considérons    0 p 0 0 0 . . .   q 0 p 0 0 . . .    Q =  0 q 0 p 0 . . .     .. . . . . . . . .  . . . . .

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Si p ≥ q

* Tous les états sont récurrents nuls ou transitoires. Considérons    0 p 0 0 0 . . .   q 0 p 0 0 . . .    Q =  0 q 0 p 0 . . .     .. . . . . . . . .  . . . . .

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Résoudre le système d’équations linéaires suivant :

Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Si p ≥ q

* Tous les états sont récurrents nuls ou transitoires. Considérons    0 p 0 0 0 . . .   q 0 p 0 0 . . .    Q =  0 q 0 p 0 . . .     .. . . . . . . . .  . . . . .

Illustrations Illustration 1

Classification des états

* Résoudre le système d’équations linéaires suivant : h=Q×h

Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

où h = (h1 , h2 , ...)t

Pr. Chaabane Djamal

Si p ≥ q

* Ce qui donne ( M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

hi = qhi−1 + phi+1

Pr. Chaabane Djamal

Si p ≥ q

* Ce qui donne ( M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

hi = qhi−1 + phi+1 hi = qhi + phi

(18)

Pr. Chaabane Djamal

Si p ≥ q

* Ce qui donne ( M&R

hi = qhi−1 + phi+1 hi = qhi + phi

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

⇓

(18)

Pr. Chaabane Djamal

Si p ≥ q

* Ce qui donne ( M&R

hi = qhi−1 + phi+1 hi = qhi + phi

Chaînes de Markov Introduction Matrices Stochastiques

⇓

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Si p ≥ q

* Ce qui donne

(18)

Pr. Chaabane Djamal

Si p ≥ q

* Ce qui donne ( M&R

hi = qhi−1 + phi+1 hi = qhi + phi

(18)

Chaînes de Markov Introduction Matrices Stochastiques

⇓

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Si p ≥ q

* Ce qui donne p (hi+1 − hi ) = q (hi − hi−1 )

i = 1, 2, ...;

(19)

Pr. Chaabane Djamal

Si p ≥ q M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* On trouve    (hi+1 − hi ) =                      

q (hi − hi−1 ) p

Pr. Chaabane Djamal

Si p ≥ q M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* On trouve    (hi+1 − hi ) =           ... =            

q (hi − hi−1 ) p ! i−1 q (h2 − h1 ) p

Pr. Chaabane Djamal

Si p ≥ q M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* On trouve    (hi+1 − hi ) =           ... =            = 

q (hi − hi−1 ) p ! i−1 q (h2 − h1 ) p !i q h1 i = 1, 2, ... p

Pr. Chaabane Djamal

Si p ≥ q

* Donc M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

∀i ≥ 1 hi+1 = (hi+1 − hi ) + (hi − hi−1 ) + . . . + (h2 − h1 ) + h1

Pr. Chaabane Djamal

Si p ≥ q

* Donc M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

∀i ≥ 1 hi+1 = (hi+1 − hi ) + (hi − hi−1 ) + . . . + (h2 − h1 ) + h1  !i   q q  = 1 + + ... +  h1 . p p

Pr. Chaabane Djamal

Si p ≥ q

* Donc M&R

Chaînes de Markov Introduction

∀i ≥ 1 hi+1 = (hi+1 − hi ) + (hi − hi−1 ) + . . . + (h2 − h1 ) + h1  !i   q q  = 1 + + ... +  h1 . p p

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

* La solution du système h = Qh est de la forme  !i−1    q q  i = 1, 2, ... hi = c 1 + + ... + p p

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

c est une constante

(20)

Pr. Chaabane Djamal

Si p = q

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Dans ce cas l’équation (20) montre que la solution est hi = ic ∀i ≥ 1 avec 0 ≤ hi ≤ 1 ∀i ≥ 1 ⇒ c = 0

Pr. Chaabane Djamal

Si p = q

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Dans ce cas l’équation (20) montre que la solution est hi = ic ∀i ≥ 1 avec 0 ≤ hi ≤ 1 ∀i ≥ 1 ⇒ c = 0

⇓

Pr. Chaabane Djamal

Si p = q

M&R

* Dans ce cas l’équation (20) montre que la solution est hi = ic ∀i ≥ 1 avec 0 ≤ hi ≤ 1 ∀i ≥ 1 ⇒ c = 0

Chaînes de Markov

⇓

Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Si p = q

* Donc l’unique solution du système h = Qh est h = 0, d’où tous les états sont récurrents (ils ne sont pas positifs, donc nuls).

Pr. Chaabane Djamal

Si p > q M&R

! q on obtient * En choisissant c = 1 − p

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

hi = 1 − vérifiant 0 ≤ hi ≤ 1,

!i q , p

i = 1, 2, ...

∀i.

* Dans ce cas tous les états sont tansitoires.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit j un état de E.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit j un état de E. * Si j est un état récurrent, donc ϑjj = 1 ⇒ rjj = ∞. • Si j est accessible à partir de i; i ∈ E alors ϑij > 0 donc rij = ∞.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit j un état de E. * Si j est un état récurrent, donc ϑjj = 1 ⇒ rjj = ∞. • Si j est accessible à partir de i; i ∈ E alors ϑij > 0 donc rij = ∞. • Si j n’est pas accessible à partir de i alors ϑij = 0 donc rij = 0; (0 × ∞ = 0)

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit j un état de E. * Si j est un état récurrent, donc ϑjj = 1 ⇒ rjj = ∞. • Si j est accessible à partir de i; i ∈ E alors ϑij > 0 donc rij = ∞. • Si j n’est pas accessible à partir de i alors ϑij = 0 donc rij = 0; (0 × ∞ = 0)

Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Donc j est un état récurrent

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit j un état de E. * Si j est un état récurrent, donc ϑjj = 1 ⇒ rjj = ∞. • Si j est accessible à partir de i; i ∈ E alors ϑij > 0 donc rij = ∞. • Si j n’est pas accessible à partir de i alors ϑij = 0 donc rij = 0; (0 × ∞ = 0)

( * Donc j est un état récurrent ⇒ rij =

0 siϑij = 0 ∞ siϑij > 0

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* Si j est un état transitoire et i un état récurrent alors ϑij = 0 ⇒ rij = 0 M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* Si j est un état transitoire et i un état récurrent alors ϑij = 0 ⇒ rij = 0 M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j ∈ D ⊂ E sont des états transitoires, on considère Q la sous-matrice correspondante de P et S la sous-matrice correspondante de R.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* Si j est un état transitoire et i un état récurrent alors ϑij = 0 ⇒ rij = 0 M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j ∈ D ⊂ E sont des états transitoires, on considère Q la sous-matrice correspondante de P et S la sous-matrice correspondante de R. ! K O Ecrivons P = L Q

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* Si j est un état transitoire et i un état récurrent alors ϑij = 0 ⇒ rij = 0 M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j ∈ D ⊂ E sont des états transitoires, on considère Q la sous-matrice correspondante de P et S la sous-matrice correspondante de R. ! ! K O Kn O n Ecrivons P = ⇒P = L Q Ln Qn

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* Si j est un état transitoire et i un état récurrent alors ϑij = 0 ⇒ rij = 0 M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j ∈ D ⊂ E sont des états transitoires, on considère Q la sous-matrice correspondante de P et S la sous-matrice correspondante de R. ! ! K O Kn O n Ecrivons P = ⇒P = L QX Ln Qn     Km O X  m≥0  m X  d’où R = P =  X m   L Q m m≥0 m≥0

m≥0

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc S =

X m≥0

Qm = I + Q + Q2 + ... = S − I

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Donc S =

X

Qm = I + Q + Q2 + ... = S − I

m≥0

(

(I − Q) S = I S (I − Q) = I

(21)

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Proposition Si card(D) < ∞ alors S = (I − Q)−1 . Par contre, si card(D) = ∞ alors S est la solution minimale du systeme (21).

La matrice R Pr. Chaabane Djamal

Exemple M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Soit une chaîne de Markov avec espace d’états E = {1, 2, ..., 8} et matrice des probabilités de transition        P =     

0.5 0.3 0.2 0 0 0.3 0.7 0 0.6 0.4 0 0 0 0 0 0 0 0 0 0.5 0 0 0 0 0.2 0.5 0 0 0.2 0 0.2 0

0 0 0 0 0 0 1 0 0.5 0 0 0.1 0 0 0 0.6

 0 0   0 0   0 0  0 0   0 0   0.9 0   0 0.3  0 0

Pr. Chaabane Djamal

La matrice R M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Les classes finales : C1 = {1, 2, 3}; C2 {4, 5}, l’ensemble D = {6, 7, 8}.    0.1 0.9 0    0 0.3  Q =  0   0.6 0 0

Pr. Chaabane Djamal

La matrice R M&R

Chaînes de Markov Introduction Matrices Stochastiques

* Les classes finales : C1 = {1, 2, 3}; C2 {4, 5}, l’ensemble D = {6, 7, 8}.    0.1 0.9 0    0 0.3  Q =  0   0.6 0 0

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* S = (I − Q)−1

   1.355 1.219 0.366    =  0.244 1.219 0.366    0.813 0.732 1.219

Pr. Chaabane Djamal

La matrice R

* La matrice potentielle R : M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

       R =      

∞ ∞ ∞ 0 0 ∞ ∞ ∞

∞ ∞ ∞ 0 0 ∞ ∞ ∞

∞ 0 0 0 0 0 ∞ 0 0 0 0 0 ∞ 0 0 0 0 0 0 ∞ ∞ 0 0 0 0 ∞ ∞ 0 0 0 ∞ 0 0 1.355 1.219 0.366 ∞ 0 0 0.244 1.219 0.366 ∞ 0 0 0.813 0.732 1.219

            

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit V = (ϑij )i,j∈E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit V = (ϑij )i,j∈E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j deux états récurrents d’une même classe, alors ϑij = 1

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit V = (ϑij )i,j∈E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j deux états récurrents d’une même classe, alors ϑij = 1 * Si i, j des états récurrents dans deux classes différentes alors ϑij = 0.

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit V = (ϑij )i,j∈E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j deux états récurrents d’une même classe, alors ϑij = 1 * Si i, j des états récurrents dans deux classes différentes alors ϑij = 0. * Si i est récurrent et j transitoire, alors ϑij = 0.

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit V = (ϑij )i,j∈E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j deux états récurrents d’une même classe, alors ϑij = 1 * Si i, j des états récurrents dans deux classes différentes alors ϑij = 0. * Si i est récurrent et j transitoire, alors ϑij = 0. * Si i, j deux états transitoires, alors

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit V = (ϑij )i,j∈E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j deux états récurrents d’une même classe, alors ϑij = 1 * Si i, j des états récurrents dans deux classes différentes alors ϑij = 0. * Si i est récurrent et j transitoire, alors ϑij = 0. * Si i, j deux états transitoires, alors rij 1 rij < ∞; ϑjj = 1 − ; ϑij = rjj rjj

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Considérons une chaîne de Markov, E espace des états et P la matrice de probabilités de transition. Soit V = (ϑij )i,j∈E M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si i, j deux états récurrents d’une même classe, alors ϑij = 1 * Si i, j des états récurrents dans deux classes différentes alors ϑij = 0. * Si i est récurrent et j transitoire, alors ϑij = 0. * Si i, j deux états transitoires, alors rij 1 rij < ∞; ϑjj = 1 − ; ϑij = rjj rjj * i transitoire et j est récurrent on a :

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Lemme Soit C une classe finale irréductible, alors ϑij = ϑik

∀j, k ∈ C(j , k)

ϑij ou ϑik est la probabilité d’accès à la classe C.

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

Lemme Soit C une classe finale irréductible, alors ϑij = ϑik

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

∀j, k ∈ C(j , k)

ϑij ou ϑik est la probabilité d’accès à la classe C. La matrice V

On forme la mtrice

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

    Pˆ =   

1 0 0 1 ... ... 0 0 b1 b2

 . . . 0 0   . . . 0 0   . . . . . . . . .   . . . 1 0   . . . bn Q

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

* Les éléments des vecteurs bj ; j ∈ Cj sont bj (i) =

X k∈Cj

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

pik

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

* Les éléments des vecteurs bj ; j ∈ Cj sont bj (i) =

X k∈Cj

M&R

* On écrit P comme : Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

pik

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

* Les éléments des vecteurs bj ; j ∈ Cj sont bj (i) =

X k∈Cj

M&R

* On écrit P comme : Pˆ = Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I 0 B Q

!

pik

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

* Les éléments des vecteurs bj ; j ∈ Cj sont bj (i) =

X

pik

k∈Cj M&R

* On écrit P comme : Pˆ = Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I 0 B Q

!

! I 0 (I + Q + ... + Qn−1 )B Qn Bn (i, j) est la probabilité d’accèder la classe Cj à partir l’état i en n étapes.

* d’où Pˆ n =

C alcul de la matrice Potentielle V Pr. Chaabane Djamal

* Les éléments des vecteurs bj ; j ∈ Cj sont bj (i) =

X

pik

k∈Cj M&R

* On écrit P comme : Pˆ = Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

I 0 B Q

!

! I 0 (I + Q + ... + Qn−1 )B Qn Bn (i, j) est la probabilité d’accèder la classe Cj à partir l’état i en n étapes.   X  n  * G = limn→∞ Bn =  Q  B = S × B

* d’où Pˆ n =

k≥0

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques

Proposition Soit Q une matrice obtenue à partir de P en éliminant les entrées relatives aux états récurrents. On a G = S × B et pour tout état transitoire i et toute classe récurrente Cj on a ;

Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

Gij = ϑik

∀k ∈ Cj

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* S’il y a seulement une seule classe finale et un nombre fini d’états transitoires.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* S’il y a seulement une seule classe finale et un nombre fini d’états transitoires. Comme  P1 = 1 ⇒ B + Q1  = 1 ⇒ B = 1 − Q1 Bn = I + Q + ... + Qn−1 (1 − Q1) = 1 − Qn 1 G = lim (1 − Qn 1) = 1 n→∞ X car Qn est convegente ⇒ Qn → 0 qd n → ∞. n≥0

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* 1 est toujours valeur propre d’une matrice stochatique. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* 1 est toujours valeur propre d’une matrice stochatique. M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

P1 = 1

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* 1 est toujours valeur propre d’une matrice stochatique. P1 = 1

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Soit P une matrice carrée stochastique, elle est dite ergodique si existe lim Pn existe. n→∞

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

* 1 est toujours valeur propre d’une matrice stochatique. P1 = 1

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Soit P une matrice carrée stochastique, elle est dite ergodique si existe lim Pn existe. n→∞

* Si 1 est valeur propre simple de P, et si toutes les valeurs propres de P autres que 1 sont de module strictement inférieur à 1 , alors la suite de matrice (Pn )n∈N converge vers une matrice stochastique. De plus, toutes les lignes de la matrice sont identiques.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si 1 est valeur propre multiple de P, et que toutes les autres valeurs propres sont de module strictement inférieur à 1, la suite (Pn )n∈N converge vers une matrice stochastique.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction

* Si 1 est valeur propre multiple de P, et que toutes les autres valeurs propres sont de module strictement inférieur à 1, la suite (Pn )n∈N converge vers une matrice stochastique.

Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

* Si P a au moins une valeur propre autre que 1 dont le module est égal à 1, alors la suite (Pn )n∈N ne converge pas.

C alcul de la matrice Potentielle R Pr. Chaabane Djamal

La matrice stochastique

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de

a pour Pn ; n ≥ 15

G raphe Pr. Chaabane Djamal

M&R

Chaînes de Markov Introduction Matrices Stochastiques Relation de Chapman-Kolmogorov

Illustrations Illustration 1

Classification des états Passage par un état fixe

Etude asymptotique Résultats dŠalgèbre linéaire pour les chaînes de