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

3

Chaàýnes de Markov tronquées

3.1 Chaàýnes de Markov tronquées

Les chaàýnes de Markov constituent l'outil principal pour la mod'elisation et la r'esolution de problèmes dynamiques stochastiques. Dans ce chapitre, nous allons voir certains r'esultats consacr'es aux chaàýnes de Markov tronqu'ees.

Les chaàýnes de Markov sont connues, dans des situations d'applications pratiques qui se trouvent dans les t'el'ecommunications (r'eseaux de files d'attente, de radiodiffusion, de communication par satellite), l''evaluation de performance informatique (r'eseaux informatiques, programmation parallèle, stockage et retransmission en m'emoire tampon), la fabrication (lignes d'assemblage, systèmes de manutention), la fiabilit'e (analyse de panne), et la th'eorie d'inventaire, l'analyse de performances des systèmes informatiques.

Cependant, la mod'elisation des situations r'eelles, en simplifiant les hypothèses et les estimations en utilisant l'analyse de perturbations conduisant a` des erreurs introduites par ces inexactitudes. Nous allons pr'esenter quelques travaux sur le problème de troncature des chaàýnes de Markov.

3.1.1 Principe de troncature

En g'en'eral, le »principe de troncature» peut être 'enonc'e comme suit : »Pour r'esoudre un système infini d''equations lin'eaires a` un nombre infini d'inconnues, on limite le système aux n premières 'equations, et on n'eglige le reste des 'equations». Ce principe à'et'e introduit en 1913 par Riesz [40].

3.1.2 D'efinitions

Nous rappelons d'abord brièvement quelques d'efinitions essentielles des chaàýnes irr'eductibles a` valeurs dans un ensemble d'enombrable S. De nombreux r'esultats suppl'ementaires peuvent être trouv'es dans les ouvrages de Meyn et Tweedie [33] et de Nummelin [34] :

. Soient X et Y deux variables al'eatoires a` valeurs r'eelles de fonction de r'epartition F et G respectivement, X est dite stochastiquement inférieure a` Y, est on note X _st Y , si pour tout t on a :

. P = (p(i,j))i,j>1 est dite stochastiquement inférieure a` Q = (q(i,j))i,j>1, not'e P _st Q, ssi :

Vi = 1,Vm = 1, _Xm p(i,j) = _Xm q(i,j). (3.1)

j=1 j=1

. Q = (q(i, _j))i,j>1 est dite stochastiquement monotone ssi :

i j Vm _Xm q(i,k) = _Xm q(j,k). (3.2)

k=1 k=1

. On appelle »small set» une partie A de S, pour laquelle il existe un m > 0 et une mesure non triviale õ_m sur S tels que, pour tout i dans A et tout j dans S, on ait

p^(m)(i, j) = õ_m(j) (3.3)

Pour une chaàýne irr'eductible a` valeurs dans S, toute partie finie est un »small set»(i,e petite s'erie).

. Soit Z = (Z(k))k>0 une chaàýne irr'eductible et A une partie de S, le temps d'atteinte l'ensemble A est d'efini par :

ôA = inf{k = 1; Z(k) E A}, (3.4)

La chaine Z = (Z(k))k>0 est dite geometriquement recurrente s'il existe un »small set» B et un nombre r > 1, dependant eventuellement de B, tel que

sup

iEEi {r^ôB} < +8. (3.5)

. L'etat i est dit geometriquement recurrent s'il existe r > 1, dependant eventuellement de i, tel que :

Eir^ôi < +8, (3.6)

Si la chaine est geometriquement recurrente, tous les etats sont geometriquement recurrents.

i> La chaine Z = (Z(k))k>0 est dite uniformement recurrente s'il existe un »small set» B et un nombre r > 1, dependant eventuellement de B, tel que

sup Eir^ôB < +8. (3.7)

iEs