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 troncature de l' espace d'états du système d'attente m/m/1: méthode de stabilité forte

( Télécharger le fichier original )
par Haoua LARAB
Université Abderrahmane Mira Bejaia Algérie - Master recherche opérationnelle 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

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 Pn.

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

Tn = (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 Tn n'est pas stochastique.

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

c'est a` dire Pn(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 Pn, plus précisément, soit

An = (á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, Pn et P sont voisines, ce qui amène aux questions suivantes :

(Q1) Pn 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 Pn, en particulier par Seneta [41, 39]. Nous notons que si

l'état 1 est récurrent positif pour Pn, 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 Pn. Il a examinéquatre types de matrices Pn, 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 Pn construite par augmentation.

(3) Heyman [20] a construit des chaàýnes Xn et X de matrices de transitions respectives Pn et P et il a introduit les temps de retour en 1, Cn et C des chaàýnes Xn 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éPn, »la matrice coin nord-ouest de troncature» de P. On connaàýt que les approximations de ð(j)/ð(0) peut être construite a` partir de Pn, 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.

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








"Il faudrait pour le bonheur des états que les philosophes fussent roi ou que les rois fussent philosophes"   Platon