WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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

( Télécharger le fichier original )
par Haoua LARAB
Université Abderrahmane Mira Bejaia - Master Recherche Operationnelle 2011
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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[Xn = 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(Xn = 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 Xn 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 (xn) de S tend vers l'infini si pour toute partie finie F de S, xn 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, Xn 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).

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Tu supportes des injustices; Consoles-toi, le vrai malheur est d'en faire"   Démocrite