La comparaison stochastique sur des espaces  multidimensionnels

Les méthodes de bornes stochastiques s’appliquent essentiellement aux chaînes de Markov et permettent d’apporter des solutions intéressantes pour l’évaluation des performances des systèmes. Nous nous focaliserons sur des chaînes de Markov multidimensionnelles permettant de modéliser des systèmes complexes. L’objectif de ce chapitre est d’expliquer d’abord d’une manière intuitive comment utiliser les méthodes de bornes stochastiques pour l’évaluation des systèmes complexes. Ensuite, on rentrera dans les détails théoriques en présentant différentes méthodes de comparaison stochastique. Ce chapitre est organisé comme suit : 1. Définition d’un ordre sur un espace d’états multidimensionnel. 2. La comparaison stochastique : définitions entre des variables aléatoires et des chaînes de Markov. 3. Méthodes de comparaisons stochastiques : le couplage et les ensembles croissants 4. Comparaison par fonction de projection.  Un système complexe, comme vu précédemment, peut-être un système de grande taille représentant un réseau avec de multiples nœuds. Il peut être aussi un système où différents types d’événements peuvent se déclencher (arrivées/services, pannes/réparations ou signaux déclencheurs). Ainsi la prise en compte de ces événements peut, de ce fait, entrainer une augmentation du nombre de composantes nécessaires pour représenter un état du système.   La comparaison stochastique sur des espaces multidimensionnels.Les solutions apportées par les méthodes de bornes stochastiques consistent à construire des systèmes bornants plus faciles à étudier. A partir de ces derniers, on pourra générer des mesures de performances bornantes (supérieures et inférieures) de la mesure exacte. Nous soulignons que les bornes ainsi obtenues sont valables aussi bien en stationnaire qu’en transitoire. La comparaison stochastique est basée sur la théorie des ordres stochastiques qui est compliquée lorsque l’espace d’état est multidimensionnel [39, 40, 49] car plusieurs ordres stochastiques peuvent être définis et les méthodes de comparaison sont plus difficiles à utiliser que sur un espace monodimensionnel. L’ordre le plus connu est l’ordre fort noté st (dit ordre « strong »), équivalent à une comparaison des trajectoires (« sample path ordering »). Dans cette thèse, nous ne travaillons que sur cet ordre et donc, nous ne présenterons que celui-ci. Nous supposons que le système peut être représenté par une chaîne de Markov à temps continu (CMTC), notée {X(t), t ≥ 0}, et définie sur un espace d’état A (représenté en général par N n ). On note par Π(x, t) la probabilité à l’instant t que le processus soit à l’état x. Nous supposons que l’espace d’état A est muni d’un préordre 1 (exemple : l’ordre composante par composante). Nous voulons calculer la mesure de performance suivante : R(t) = X x∈A Π(x, t)f(x) (I.1) où f est une fonction croissante A → R +. Quand t → ∞, si le processus a un comportement stationnaire, on note par Π(x) la probabilité stationnaire d’être à l’état x. R représente alors la mesure calculée à partir de la distribution stationnaire. Si Π(t) (ou Π) n’a pas de solution simple alors, le calcul de R(t) (ou R) devient difficile quand la taille de l’espace d’état A est importante. Nous proposons d’appliquer la comparaison stochastique. C’est-à-dire, borner {X(t), t ≥ 0} par {XS (t), t ≥ 0} (au sens borne supérieure) et {XI (t), t ≥ 0} (au sens borne inférieure) dans le sens de l’ordre stochastique st : tel que {XS (t), t ≥ 0} et {XI (t), t ≥ 0} soient plus faciles à analyser car les distributions sont calculables plus facilement ou définies sur un espace d’état plus petit (voir Fourneau et al. [45]). Ainsi, on peut déduire la mesure bornante RS (t), calculée à partir de la distribution ΠS (t) et tel que : R(t) ≤ R S (t) (I.2) 1. voir la section suivante pour la définition du préordre 18 I.2 Les ordres sur des espaces multidimensionnels ou RI (t), calculée à partir de la distribution ΠI (t) et tel que : R I (t) ≤ R(t) (I.3) 2 Les ordres sur des espaces multidimensionnels Dans cette section, nous donnons les bases théoriques essentielles à l’utilisation des ordres stochastiques sur des espaces multidimensionnels. Dans la plupart des cas, je travaillerai sur l’espace A = N n qui est discret, dénombrable, muni d’au moins un préordre  (relation binaire au moins réflexive et transitive : 1. Réflexivité : ∀x ∈ A, x  x 2. Transitivité : ∀x, y, z ∈ A, si x  y et y  z alors, x  z. Ainsi, un ordre partiel sur un ensemble A est un préordre vérifiant en plus l’antisymétrie : 3 Antisymétrie :∀x, y ∈ A, si x  y et y  x alors, x = y. Un ordre total est un ordre partiel qui satisfait à la propriété de comparabilité : 4 Comparabilité : ∀x, y ∈ A, x  y ou y  x Par exemple, sur A = N n , l’ordre lexicographique est un ordre total alors que l’ordre composante par composante (noté ) est partiel. Nous utilisons souvent l’ordre composante par composante, , pour la comparaison des processus multidimensionnels : ∀x, y ∈ N n , x  y ⇔ xi ≤ yi , ∀1 ≤ i ≤ n Ainsi, l’ordre composante par composante permet de comparer file par file les réseaux de communication, ce qui génère des inégalités sur les mesures de performances telles que les temps de réponses, ou les probabilités de blocage d’une file. On peut remarquer que cet ordre partiel peut être plus intéressant que l’ordre total lexicographique car cela génère moins d’inégalités à vérifier pour la comparaison de chaînes de Markov et donc, une meilleure qualité des bornes. Dans la suite, nous définissons la comparaison stochastique de variables aléatoires et des processus markoviens sur un espace A muni d’au moins un préordre . La comparaison stochastique La comparaison stochastique est fondée sur les ordres stochastiques. Un ordre stochastique est une relation d’ordre qui permet de comparer des variables aléatoires, des processus stochastiques ou des distributions de probabilité. Il existe deux grandes familles d’ordres : les ordres intégraux et les ordres ensemblistes. Nous orientons le lecteur intéressé à l’article de Massey [40] pour les ordres ensemblistes et aux ouvrages de Stoyan [50] et de Shaked et al. [51] pour les ordres intégraux. La thèse de Taleb [52] propose une couverture des deux approches et regroupe les principaux résultats et définitions sur les ordres stochastiques ensemblistes et intégraux ainsi que, les liens d’équivalences qui peuvent exister entre eux. Nous présentons dans la suite les définitions de base dans le cas de l’ordre fort st.

Comparaisons stochastiques de variables aléatoires

Soit donc, un espace d’état A muni d’un préordre . Considérons deux variables aléatoires X et Y définies sur A avec des mesures de probabilités respectives p et q telles que p[i] = P rob(X = i), ∀i ∈ A (resp. q[i] = P rob(Y = i), ∀i ∈ A). Leur comparaison suivant l’ordre fort st, est définie comme suit [39] : Définition .2. X st Y si et seulement si E[f(X)] ≤ E[f(Y )], ∀f : A → R +,  −croissante Sur les espaces multidimensionnels d’autres ordres, plus faibles en termes de contraintes, peuvent être définis. Par exemple, dans [40], l’ordre « weak » (noté wk) permet de comparer les queues de distribution et l’ordre « weak* » (noté wk∗ ), les fonctions de répartition. Il existe plusieurs formalismes pour définir un ordre stochastique : fonctions croissantes ou ensembles croissants. Ces deux formalismes sont équivalents car les fonctions croissantes peuvent être générées à partir des combinaisons linéaires des fonctions indicatrices des ensembles croissants. Nous proposons d’utiliser celui des ensembles croissants afin de nous ramener à des inégalités entre matrices (matrices des générateurs ou matrices des probabilités de transitions) pour la comparaison de chaînes de Markov. Soit Γ ⊂ A, Γ est un ensemble croissant si et seulement s’il est équivalent à une séquence d’éléments croissants de A. On note par : Γ ↑= {y ∈ A | y  x, x ∈ Γ} et donc la définition formelle d’un ensemble croissant est la suivante : Définition .3. Γ est un ensemble croissant si et seulement si Γ = Γ ↑.