193
© Dunod – Toute reproduction non autorisée est un délit.
5.4 Clas si fi ca tion des états d’une chaîne de Markov
Déter mi nons, pour chaque sous chaîne, les « classes d’états com mu ni cants » qui
d’après la remarque ci dessus, coïn cident avec les com po santes for te ment connexes
du graphe (cette déter mi na tion peut se faire algorithmiquement : par un algo rithme
fondé sur un par cours en pro fon deur du graphe, donc de faible com plexité). Pour e 1 ,
on trouve 4 com po santes for te ment connexes et donc 4 classes :
c 1 5 5A6 , c 2 5 5B, H6 , c 3 5 5C, F, G6 , c 4 5 5D, E, K6.
Pour e 2 , on trouve 2 com po santes for te ment connexes et donc 2 classes :
c 5 5 5I, L6 , c 6 5 5J6.
On peut alors retra cer le graphe en fai sant appa raître l’ordre sur ces com po santes
for te ment connexes. Rap pe lons que « c k pré cède c , » (c k < c , ) si et seule ment si,
dans G, il existe un che min d’un som met quel conque de c k vers un som met quel
conque de c , ; cette rela tion étant réflexive, anti sy mé trique et tran si tive, il s’agit
d’une rela tion d’ordre sur les classes, dont voici le dia gramme de Hasse :
Les classes c 1 , c 2 et c 5 sont des classes d’états tran si toires : si le sys tème est ini
tia le ment dans l’un des som mets de ces classes, il finira par le quit ter défi ni ti ve ment
(pour tout état tran si toire E i , p
1q2
ij S 0 quand le nombre de tran si tions q S ` 2 . Dans
le dia gramme ci dessus toute classe tran si toire c k a une classe « au des sus » d’elle,
c’est àdire que c k pré cède une autre classe.
Au contraire, les classes c 3 , c 4 et c 6 – qui sont des « élé ments maximaux » (sans
classe « au des sus » d’elles) – sont nom mées « classes récur rentes » (on dit aussi
per sis tantes ou finales) ; lorsque le sys tème atteint un état d’une classe récur rente
c r , tous les états par les quels il pas sera ulté rieu re ment appar tiennent à cette même
classe c r .
Mais il existe des dif fé rences entre les classes récur rentes ; ainsi entre la classe
c 4 5 5D, E, K6 et la classe c 3 5 5C, F, G6 : en effet si le sys tème passe par l’état C
lors de la k
ième
tran si tion, il est cer tain qu’il pas sera par F lors de la k 1 1
ième
, par G
lors de la k 1 2
ième
, de nou veau par C lors de la k 1 3
ième
et ainsi de suite : il s’agit
© Dunod – Toute reproduction non autorisée est un délit.
5.4 Clas si fi ca tion des états d’une chaîne de Markov
Déter mi nons, pour chaque sous chaîne, les « classes d’états com mu ni cants » qui
d’après la remarque ci dessus, coïn cident avec les com po santes for te ment connexes
du graphe (cette déter mi na tion peut se faire algorithmiquement : par un algo rithme
fondé sur un par cours en pro fon deur du graphe, donc de faible com plexité). Pour e 1 ,
on trouve 4 com po santes for te ment connexes et donc 4 classes :
c 1 5 5A6 , c 2 5 5B, H6 , c 3 5 5C, F, G6 , c 4 5 5D, E, K6.
Pour e 2 , on trouve 2 com po santes for te ment connexes et donc 2 classes :
c 5 5 5I, L6 , c 6 5 5J6.
On peut alors retra cer le graphe en fai sant appa raître l’ordre sur ces com po santes
for te ment connexes. Rap pe lons que « c k pré cède c , » (c k < c , ) si et seule ment si,
dans G, il existe un che min d’un som met quel conque de c k vers un som met quel
conque de c , ; cette rela tion étant réflexive, anti sy mé trique et tran si tive, il s’agit
d’une rela tion d’ordre sur les classes, dont voici le dia gramme de Hasse :
Les classes c 1 , c 2 et c 5 sont des classes d’états tran si toires : si le sys tème est ini
tia le ment dans l’un des som mets de ces classes, il finira par le quit ter défi ni ti ve ment
(pour tout état tran si toire E i , p
1q2
ij S 0 quand le nombre de tran si tions q S ` 2 . Dans
le dia gramme ci dessus toute classe tran si toire c k a une classe « au des sus » d’elle,
c’est àdire que c k pré cède une autre classe.
Au contraire, les classes c 3 , c 4 et c 6 – qui sont des « élé ments maximaux » (sans
classe « au des sus » d’elles) – sont nom mées « classes récur rentes » (on dit aussi
per sis tantes ou finales) ; lorsque le sys tème atteint un état d’une classe récur rente
c r , tous les états par les quels il pas sera ulté rieu re ment appar tiennent à cette même
classe c r .
Mais il existe des dif fé rences entre les classes récur rentes ; ainsi entre la classe
c 4 5 5D, E, K6 et la classe c 3 5 5C, F, G6 : en effet si le sys tème passe par l’état C
lors de la k
ième
tran si tion, il est cer tain qu’il pas sera par F lors de la k 1 1
ième
, par G
lors de la k 1 2
ième
, de nou veau par C lors de la k 1 3
ième
et ainsi de suite : il s’agit