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

4.3 L'augmentation de la premi`ere colonne

Dans ce cas, la matrice stochastique A est donnée sous la forme suivante :

Calcul de la borne de stabilitéforte pour le cas de troncature de la ^capacité

d'attente de la file M/M/1											Page 51
1 ? 1 1 1 A = ? ? ? ? ? ? ? ? ? ? ? ? 1 1 1 1 et la matrice P devient : á ? á 0 P= ? ? ? ? ? ? ? ? ? ? á			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 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
Pij =	? ? ?	^ePij, si 0 = i = N - 1 ; 0 = j = N; á, si j = N - 1 ; i = N; á, si j = 0 i = N.

4.3.1 Calcul de la borne de stabilitéforte :Augmentation de la premi`ere colonne

v- Stabilitéforte de la chaàýne de Markov X

Pour prouver la v- Stabilitéforte de la chaàýne de Markov X pour une fonction test v(k) = â^k pour â > 1, il est suffisant de trouver une mesure ó, et une fonction mesurable h sur N tels que :

a) ðh > 0, ó1I = 1, óh > 0,

b) Tij = Pij - óihi, est non négatif,

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 52

c) ?ñ < 1 tel que Tõ(k) = ñõ(k), pour k ? {0,1, ..., N},

d) 1P1_õ < 8.

Pour notre cas, on choisit :

· õ(k) = â^k , â > 1 avec k ? N.

· h(i) = Pi0 :

~ 1, si i = 0;

h(i) = 1Ii=0= 0, sinon.

· ój = P0j :

ój = P0j =

? ? ?

á, si j = 0; á, si j = 1; 0, sinon.

V'erifions maintenant les conditions a), b), c) et d) :

Condition a) ðh = ð0 > 0,

ðh = ð0 = (1 - 0)/(1 - Q^N+1) > 0. (4.3)

· ó1I = á + á + 0 = 1, o`u 1I est le vecteur unit'e,

· óh = á + (0 × á) + 0 = á > 0.

Condition b) V'erifions que le noyau T est non n'egatif, on a :

T = P - h ? ó, ie T = P - {1^ereligne}

~ P0j - ój = P0j - P0j = 0, si i = 0; Tij = Pij - h(i)ój = Pij - 0 × ój = Pij, sinon,

Donc, T est un noyau non-n'egatif, ?i, j = 0 : Tij = 0.

Condition c) Montrons l'existence d'une certaine constante ñ < 1 telle que : Tõ(k) = ñõ(k), pour k = 0.

Par d'efinition,

Tõ(k) =

XN j=0

õ(j)Tkj.

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 53

En effet, on a :

Pour k=0 : (Tv)(0) = Pour 1 = k = N - 1 :		XN j=0	v(j)T0j =	XN j=0	âj × 0 = 0.
(Tv)(k) =	XN j=0	v(j)Pkj = á v(k - 1) + á v(k + 1)

= á â^k-1 + á âk+1
âk{á + áâ}

= ñ1(â) v(k),

Posons

ñ1 (â) á = _â+ áâ. (4.4)

(Tv)(N) =

XN j=0

â^jPNj = v(0)PN,0 + v(N)PN,N-1

= áâ⁰ + _â^áâ^N = á + â^N{_â}

N{ á + á
_â}

âN â

= ñ2(â)v(k),

Posons

ñ2(â) = á âN + _â^á. (4.5)

On a,

á á á

ñ1(â) - ñ2(â) = _â+ áâ -

âN -

á

â

= áâ - > 0

âN

Donc, 0 < ñ2(â) < ñ1(â).

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 54

Alors, il suffit de prendre ñ(â) = ñ1(â) = max{ñ1(â), ñ2(â)} verifiant :

(Tv)(k) = ñ1(â) × v(k).

Il nous reste a` demontrer que,

ñ1(â) = á â + áâ < 1,

Pour tout â > 1,

2

ñ1(â) u ëâ 1 + 0

(ë + u)â (ë + u) (1 + e)â, (4.6)

Si on suppose que pâ < 1 ? (ë/u)â < 1. Alors :

ñ(â) < 1,

En effet, on a :

1 + Qâ²

ñ(â) = (1 + Q)â^.

Pour que ñ(â) < 1 , il faut que,

(1 + 0â²) < ((1 + p)â) 1 + %â² -- â -- âp < 1

(1 -- â) + (âp(â -- 1)) < 0

(âp(â -- 1)) < (â -- 1)

âp < 1.

D'o`u, ñ(â) < 1.

Condition d) Verifions que 11P11_v < cc .

T = P -- h ? ó P = T + h ? ó

11P11_v = 11T + h ? ó11_v

= 11T 11_v + 11h11_v11ó11_v.

Par definition, on a,

11T11v = sup 0<i<N		1	XN j=0	õ(j) | Tij |
		õ(i)
= sup 0<i<N	1 õ(i)^ñõ(i)

= ñ(â) < 1.

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 55

et

Ihl_v = sup õ(i)|hi| = 1,

0<i<N

1ó1v =

XN j=0

õ(j)|ój| =

XN j=0

â^jP0j

= õ(0)ó0 + õ(1)ó1 + 0 = á + áâ

= á + áâ0 < 8,

avec : â0 = sup{â : ñ(â) < 1}

Donc, 1P1_v < 8.

Ainsi, toutes les conditions sont vérifiées.

In'egalit'es de stabilit'e forte

Estimation de la d'eviation du noyau de transition

Pour pouvoir estimer numériquement l'écart entre les distributions stationnaires des états des chaines de Markov (^fX_n), (X_n), estimons au préalable la norme de déviation du noyau de transition P de la chaine de Markov de système M/M/1/8 par rapport au noyau de transition P associéa` la chaine de Markov du système M/M/1/N (modèle tronqué).

L'estimation de 1 P^e - P1_v est énoncée par le lemme suivant

Lemme 4.1 : Si p < 1 , pâ < 1 et 1 < â < â0. Alors,

1 P^e - P1_v ? Ä(â) = (1â+ _N e) . (4.7)

Preuve

Par définition, on a :

e MP - PMv = sup 0<k<N		1		XN j=0		v(j)|		Pkj- - Pkj|.
		v(k)
Pour 0 = k < N - 1 : Ä0(â) = sup 0<k<N-1	1		XN j=0		v(j)|		Pkj- - Pkj| = 0.
	v(k)

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 56

Pour k = N :

1 Ä1(â) = v(N)

XN j=0

v(j)|

PNj - PNj|

âN {v(0)| 1³N0 - PN0| - 1)| 1³NN-1 - PNN-1|}

1

= âN {á + 0}

á

=

âN .

On a : Ä1(â) > Ä0(â),

1 P^e - P1_v = max{Ä0(â),Ä1(â)},

Donc ;

IIP - PM_v = Ä1(â) = á âN = (1 âN A + = (â). (4.8)

D'etermination de l'erreur due a` la troncature

L'estimation de la déviation des distributions stationnaires est donn'ee par le théoreme suivant

Th'eor`eme 4.3 Soient ^-ð et ð les distributions stationnaires des chaines de Markov décrivant respectivement les états des systemes d'attente M/M/1 et M/M/1/N. Supposons que les hypotheses du Lemme 4.1 soient vérifiées. Alors, pour tout Q < 1, et sous la condition :

Ä(â) < 1 - ñ(â)

c(â) ,

nous avons l'estimation de la borne de la stabilitédans ce cas est donn'ee par :

c0(â)c(â)Ä(â)

|if - ð||_v = = Be1.

1 - ñ(â) - Ä(â)c(â)

o`u Ä(â) est défini en (4.8) et ñ(â) en (4.7) et

â(1 - 0)(1 + â0

(4.9)

c0(â) = (â - 1)(1 - Q^N+¹)(1 -

â(1 - 0(1 + â0

c(â) = 1 + (â - 1)(1 - %^N+¹)(1 - â%). (4.10)

1

Calcul de la borne de stabilit'e forte pour le cas de troncature de la capacit'e d'attente de la file M/M/1 Page 57

Preuve

Afin de d'emontrer ce r'esultat, il suffit d'estimer ||ð||_v, et ||1I||_v , o`u 1I est la fonction identiquement 'egale a` l'unit'e.

Supposons que âp < 1 , alors la norme de la distribution stationnaire peut àetre estim'ee par la formule qu est donn'ee par :

(óõ)(ðh)(óõ)(ð0)

|_v = (4.11)

1 - ñ(â) 1 - ñ(â)^.

o`u ð0 est celle obtenue pour la file d'attente M/M/1/N tronqu'ee qui est donn'ee par :

(1 - p)

ð0 = (4.12)

(1 - Q^N+¹)^.

Donc, on obtient :	á + áâ ||ð||v = 1 - (1+â2% (1+%) )		(1 - p) (1 - QN+1) (4.13)
=		â(1 - %)(1 + â%)		= c0(â). (4.14)
		(â - 1)(1 - e^N+^1)(1 - â%)

Par d'efinition, on a :

||1||_v = sup

0<k<N

âk = 1.

Donc, nous avons

c(â) = 1 + â(1 - e)(1 + âp)

(â - 1)(1 - e^N+¹)(1 - â%)^.

Ainsi, pour tout Ä(â) < ¹V⁾, nous obtenons :

c

||if - ð||_v = 0(â)c(â)Ä(â)

=

1 - ñ(â) ? Ä(â)c(â) Be1.