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.2 Diff'erentes techniques de la troncature des chaines de Markov

Soit P = (P(i, j))i, j = 1, une matrice stochastique infinie, irreductible et recurrente positive elle admet une distribution stationnaire unique ð_n = (ðn(j))j>1, le calcul de cette distribution etant en general difficile sinon impossible.Pour cela, une solution consiste a` approcher P par une matrice stochastique finie P_n.

»Le Coin Nord-Ouest» d'ordre n de la matrice P :

T_n = (P(i, j))n>i,j>1.

P etant irreductible, il existe au moins une ligne i pour laquelle

Xn j=1

P(i, j) < 1

alors la matrice tronquee T_n n'est pas stochastique.

A partir de T_n, on construit une matrice stochastique (Pn(i, j))n>i,j>1 verifiant P_n = Tn

c'est a` dire P_n(i, j) > P(i, j) pour 1 = i, j = n; cela peut se faire de plusieurs facons, citons les principales :

3.2.1 Augmentation linéaire

La masse de probabilitéperdue lors de la troncature de P est redistribuée sur les colonnes de P_n, plus précisément, soit

A_n = (án(i,j))1<i,j<n,

une matrice stochastique quelconque, on pose pour 1 = i, j = n,

X Pn(i,j) = P(i,j) + án(i, j) k>n En particulier, on obtient :

P(i, k).

- L'augmentation de la première colonne, travaux de Kalashnikov et Rachev [27], seulement si á_n(i, 1) = 1 pour 1 = i = n;

- L'augmentation de la dernière colonne [51], seulement si á_n(i, n) = 1 pour 1 = i = n ; - L'augmentation uniforme á_n(i,j) = n^-1 pour 1 = i,j = n .

- On peut aussi prendre pour A, une matrice dont toutes les lignes sont identiques,c'est un cas considérépar Gibson et Seneta [11].

- Encore plus simplement, on peut comme van Dijk [48], choisir A booléenne.

3.2.2 Renormalisation

On pose s(i, n) = _Pn P(i,j), on choisit alors pour 1 = i,j = n :

j=1

P (i, j) Pn(i, j) = s(i,n) . En prenant n assez grand afin que s(i, n) > 0. Notons que les deux conditions Pn stochastique et Pn = Tn, impliquent lim n-400

Pn(i,j) =

P(i, j). Par consequent si n est grand, P_n et P sont voisines, ce qui amène aux questions suivantes :

(Q1) P_n admet-elle une distribution stationnaire ð_n ? - (Q2) ð_n converge-t-elle, en un sens a` préciser vers ð ?

En ce qui concerne (Q1), l'existence d'une distribution stationnaire ð_n a ^{étéétudié}pour divers types de matrices P_n, en particulier par Seneta [41, 39]. Nous notons que si

l'état 1 est récurrent positif pour P_n, il existe au moins une distribution stationnaire ð_n. En effet, la chaàýne réduite a` la classe de l'état récurrent 1 admet une distribution stationnaire qu'on peut compléter par 0 sur les autres états.

De nombreux travaux ont étéconsacrés a` l'étude de (Q2), parmi les plus intéressants, citons :

(1) Wolf [50], qui s'est intéresséa` l'approximation de la distribution stationnaire d'une matrice infinie P, irréductible, récurrente positive, par ailleurs quelconque, par les distributions stationnaires de matrices finies P_n. Il a examinéquatre types de matrices P_n, obtenues par:

. Augmentation de la première colonne;

. Augmentation de la dernière colonne;

. Augmentation uniforme des colonnes;

. Renormalisation.

et établit la convergence en variation de ð_n vers ð, sous des conditions analogues au critère de Foster.

(2) Seneta [41] a prouvéque ð_n converge faiblement vers ð . Cette prouve a étérepris par Gibson et Seneta [11] pour établir la convergence faible de ð_n vers ð quand P est stochastiquement monotone et P_n construite par augmentation.

(3) Heyman [20] a construit des chaàýnes X_n et X de matrices de transitions respectives P_n et P et il a introduit les temps de retour en 1, C_n et C des chaàýnes X_n et X puis le temps nécessaire pour que la chaàýne X dépasse la barrière n; en s'appuyant sur les résultats de Heyman et Whitt [21], il établit une condition suffisante pour assurer la convergence faible de ð_n vers ð .

(4) Kalashnikov et Rachev [27] ont aussi étudiéle problème d'approximation d'une chaàýne de Markov infinie, l'essentiel de leurs travaux est orientévers l'approximation uniforme de la chaàýne initiale par des chaàýnes finies construites par augmentation de la première colonne.

(5) Tweedie [46] s'est intéressé, en particulier aux chaàýnes géométriquement ergodiques et les chaàýnes de Markov stochastiquement monotone, pour étudier les deux questions. Il a considéréP_n, »la matrice coin nord-ouest de troncature» de P. On connaàýt que les approximations de _ð(j)/ð(0) peut être construite a` partir de P_n, mais seulement dans des cas particuliers, sont celles connues de la convergence de la distribution de probabilitévers elle-même. Il a montre ainsi que cette convergence se produit toujours pour deux autres classes générales de chaàýnes de Markov : les chaàýnes géométriquement ergodiques, et celles dominées par les chaàýnes stochastiquement monotones. Dans les cas particuliers, de

manière uniforme, les chaàýnes ergodiques et les chaàýnes stochastiquement monotones, il a obtenu des estimations d'erreur d'approximation ||ð(n) - ð||.

(6) Zhao et Liu [51] ont prouvéque la la chaàýne de Markov censurée fournit la meilleure approximation dans le sens que, pour une taille de troncature donnée, la somme des erreurs est le minimum et ils ont montré, par exemple, que la méthode d'augmenter la dernière colonne n'est pas toujours la meilleure.