Estimation de l'erreur de troncature de l' espace d'états du système d'attente m/m/1: méthode de stabilité forte

1.5 Classification des chaàýnes de Markov discrètes

On dit qu'une chaàýne de Markov X est discrète si son espace d'états S est fini ou dénombrable.

1.5.1 Chaàýnes de Markov homogènes

Une chaàýne de Markov est homogène (dans le temps) si la probabilitéd'effectuer une transition d'un état dans un autre est indépendante de l'instant auquel a lieu cette transition [16]. En d'autre termes, pour tout paire d'états (i,j) et pour tout instant n

P[X_n = j/Xn_1 = i] = P[Xn+k = j/Xn+k_1 = i],

quel que soit k = 0.

1.5.2 Chaàýnes de Markov irréductibles

Les notions de récurrence et d'irréductibilitéadmettent une caractérisation simple pour les chaàýne discrètes.

D'efinition 1.1 : Une chaine de Markov est irr'eductible si elle n'est constitu'ee que d'une seule classe d''etats communicants.

On peut aussi faire une classification probabiliste des 'etats d'une chaine de Markov. D'efinissons la probabilit'e de premier passage : ?k = 1, ..., n - 1/X0 = i

_f(n)

ij = P(X_n = j, Xk =6 j),

et le temps de premier passage

Tij = min{k > 0 : Xk = j; X0 = i},

Nous avons alors, Posons :	fi(j n) = P(Tij = n).
Fij(n) =		Xn i=1	fij(k).

qui repr'esente la probabilit'e pour que la chaine passant en i atteigne j en moins de n + 1 transitions.

Th'eor`eme 1.1 [16] : Consid'erons une chaine de Markov X_n irr'eductible. Pour tout i ? S ;

ôi = inf{k > 0; Xk = i}.

On voit que ôi est le temps d'atteinte de l''etat i, i.e, le temps de premier passage. Pour tout i, j ? S, on a

Ei(ôi) =

X+ n=0

Pn(i, j).

C'est l'esp'erance du nombre de passages par j partant de i.

Les conditions suivantes sont 'equivalentes :

1. Il existe un 'etat i ? S tel que Ei(ôi) < +8 ;

2. Pour tout 'etat i ? S, Ei(ôi) < +8;

3. La chaine de Markov poss`ede une probabilit'e invariante ð.

Sous ces conditions, la chaine est dite r'ecurrente positive et ð est la seule probabilit'e invariante. Pour tout k ? S,

1

Ek(ôk)^,

ð(k) =

et pour tout i ? S,

ð(k) = Ei(ôi)Ei(Óô%-1

1 n=0 1k(Xn)).

On dit qu'une suite (x_n) de S tend vers l'infini si pour toute partie finie F de S, x_n n'appartient pas a` F pour tout n assez grand.

Définition 1.2 : Une chaàýne de Markov est irréductible si son graphe représentatif est fortement connexe. Dans le cas contraire la chaàýne est réductible.

Les deux propriétés suivantes qui découlent directement de la définition d'une classe persistante et des états communiquants, auraient également pu servir de définition d'une chaàýne irréductible.

Propriété1.1 : Une chaàýne de Markov est irréductible, si pour tout état i et j, il existe in = 0 (pouvant dépendre de i et j) tel que :

P ^(m)

ij > 0.

Propriété1.2 : Une chaàýne de Markov est irréductible si et selement si toute paire d'états sont communiquants.

Proposition 1.1 : Si S est un espace d'états fini, toute chaàýne irréductible est récurrente.

Théorème 1.2 :

On considère une chaàýne de Markov irréductible. Alors, un et un seul des deux cas suivants peut se produire :

Cas récurrent : Tous les états sont récurrents et partant de tout point, la chaàýne visite une infinitéde fois tous les autres, presque sàurement.

Cas transitoire : Partant de tout état, X_n tend vers l'infini, presque sàurement.

Quelques autres propriétés [4]

. Une chaàýne de Markov irréductible ne possédant qu'une seule classe et tous ses états ont la même période. Nous dirons qu'une telle chaàýne est périodique. Apériodique dans le cas contraire.

. Une chaàýne de Markov irréductible est fortement irréductible si et seulement si elle est irréductible et apériodique.

. Si P est la matrice de transition d'une chaàýne de Markov irréductible, alors tous les états ont même nature (récurrents positifs ou bien récurrents nuls ou bien récurrents).