Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chaînes de Markov et ﬁles d’attente Guillaume Matheron 2014 Table des matières

Chaînes de Markov et ﬁles d’attente Guillaume Matheron 2014 Table des matières 1 Introduction 2 2 Chaînes de Markov en temps discret 2 2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1.1 Déﬁnition d’une chaîne de Markov en temps discret . . 2 2.1.2 Matrice de transition . . . . . . . . . . . . . . . . . . . 3 2.1.3 Utilisation de la matrice de transition . . . . . . . . . 3 2.1.4 Représentation en tant que graphe . . . . . . . . . . . 3 2.1.5 Itération de la matrice de transition . . . . . . . . . . 4 2.2 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Mesure invariante . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Étude de la vitesse de convergence . . . . . . . . . . . . . . . 7 3 File d’attente M/M/1 9 3.1 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Calcul des valeurs propres de P . . . . . . . . . . . . . . . . . 11 3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3.1 Convergence vers une distribution d’équilibre pour une ﬁle non limitée . . . . . . . . . . . . . . . . . . . . . . 11 3.3.2 Etude d’un mouvement brownien avec perturbation . . 14 4 Conclusion 16 1 1 Introduction Les chaînes de Markov sont un outil mathématique permettant de modé- liser l’évolution d’un système dont l’état au temps t+1 ne dépend que de son état au temps t, et possédant un nombre ﬁni d’états. À chaque étape, le sys- tème évolue en changeant d’état. Les probabilités de passer à chaque état au temps t+1 à partir d’un état donné au temps t peuvent être regroupées sous forme d’une matrice carrée dont les propriétés algébriques nous renseignent sur l’évolution du système. Ce document s’intéresse à l’étude de l’évolution des systèmes à partir de leur matrice de transition. En particulier, on énoncera une condition suﬃsante de convergence et une majoration de la vitesse de convergence dans ce cas. On s’intéressera aux cas limite où l’intervalle de temps entre deux étapes de la simulation tend vers 0, ou lorsque le nombre d’états tend vers l’inﬁni. 2 Chaînes de Markov en temps discret 2.1 Généralités 2.1.1 Déﬁnition d’une chaîne de Markov en temps discret Définition 1 Soit (Xn)n∈N une famille de variables aléatoires à valeurs dans E un ensemble ﬁni. Cette famille est une chaîne de Markov si elle vériﬁe la propriété de Markov : pour tout entier n ∈N∗, pour tout couple (y, z) de suites à valeurs dans E déﬁnies sur J0, n −1K, on a l’égalité : P(Xn+1 = j|Xn = i, ∀k ∈J0, n −1K, Xk = yk) = P(Xn+1 = j|Xn = i, ∀k ∈K0, n −1K, Xk = zk). Autrement dit la valeur de la variable Xn ne dépend que de la valeur de la variable Xn−1, et pas de tous ses états antécédents. On écrit alors plus simplement la probabilité de transition d’un état au suivant ainsi : P(Xn+1 = j|Xn = i). Chaîne de Markov homogène Une chaîne de Markov est dite homogène si elle vériﬁe la propriété suivante : ∀n ∈N, P(Xn+1 = j|Xn = i) = P(X1 = j|X0 = i). Autrement dit une chaîne est homogène si la probabilité de transition d’un état à l’autre ne dépend pas de l’indice de la variable concernée mais uniquement de sa valeur : l’évolution du processus ne dépend pas de l’origine des temps. Dans toute la suite, nous ne manipulerons que des chaînes homogènes. 2 2.1.2 Matrice de transition E étant ﬁni à n éléments, on l’identiﬁe à J1, nK. On déﬁnit alors naturel- lement une matrice à coeﬃcients réels à partir des probabilités de transition. On exprime les coeﬃcients de la matrice : ∀(i, j) ∈E2, pi,j = P(X1 = j|X0 = i). Remarquons que dans ce cas la matrice est stochastique ligne, c’est-à-dire que : ∀i ∈E, X j∈E pi,j = 1. 2.1.3 Utilisation de la matrice de transition Si X est un vecteur ligne décrivant les probabilités de se trouver dans chaque état au temps t, le vecteur ligne X · P représente les probabilités de se trouver dans chaque état au temps t+1. Cette déﬁnition est pratique pour l’interprétation probabiliste des chaînes de Markov, mais pas pour l’interpréter comme un endomorphisme opérant sur un vecteur colonne X de distribution de probabilités. En eﬀet il faut alors multiplier à gauche : tX′ = tX ·P. Dans la suite on étudiera les valeurs propres de cet endomorphisme, qui correspondent aux valeurs propres à gauche de P, ou plus simplement aux valeurs propres usuelles de tP. 2.1.4 Représentation en tant que graphe On peut interpréter la matrice de transition P comme une matrice d’adja- cence d’un graphe orienté. Les arêtes du graphe sont indicées par la probabilité de passage d’un état à l’autre. 0 1 2 3 4 5 1 0.3 0.1 0.6 0.3 0.2 0.1 0.4 0.3 0.5 0.2 0.5 0.5 1 3 La somme des probabilités de passage est toujours égale à 1, on peut donc omettre les boucles : 0 1 2 3 4 5 0.1 0.6 0.2 0.1 0.4 0.5 0.2 0.5 0.5 On peut écrire la matrice correspondant à cette chaîne : P =         1 0 0 0 0 0 0.1 0.3 0.6 0 0 0 0.2 0.1 0.3 0 0.4 0 0 0.5 0 0.3 0 0.2 0 0 0 0.5 0 0.5 0 0 0 0 0 1         2.1.5 Itération de la matrice de transition Probabilité de transition d’un état i à un état j en n étapes On peut se demander s’il est possible d’itérer le processus, c’est-à-dire de déterminer la probabilité de passer d’un état i à un état j en n étapes, pour n ∈N. On note cette probabilité : p(n) i,j = P(Xn = j|X0 = i) On note P (n) la matrice des coeﬃcients p(n) i,j . Théorème 1 (Chapman-Kolmogorov) ∀n ∈N, P (n) = P n Preuve : Immédiat d’après P(Xn+m|X0 = i) = X k∈E P(Xm = k|X0 = i) · P(Xn = j|X0 = k) donc ∀(n, m) ∈N2, ∀(i, j) ∈E2, p(n+m) i,j = X k∈E p(m) i,k · p(n) k,j . 4 2.2 Propriétés Remarque L’objectif de ce TIPE étant l’étude de P comme un endomor- phisme pour se rapprocher du programme, on cherchera ici à expliquer sous quelles conditions une chaîne de Markov converge vers un état stable, en admettant la majorité des résultats pour se concentrer sur les démonstrations algébriques qui suivent. Définition 2 (État transient, récurrent) Un état est dit transient si, en partant de cet état au temps t, il existe une probabilité non nulle de ne jamais repasser par cet état. Un état non transient est dit récurrent. Définition 3 (Période d’un état récurrent i) ki = pgcd{n|P(Xn = i|X0 = i) > 0}. Ainsi la période d’un état i n’est pas nécessairement la durée la plus courte au bout de laquelle on peut revenir à l’état i après l’avoir quitté. Cette déﬁnition garantit cependant que tout retour à l’état i ne peut se faire qu’après un nombre d’étapes multiple de ki. Si tout état a une période égale à 1, la chaîne est dite apériodique. Exemple Dans la chaîne ci-dessous, tous les états sont apériodiques mais la matrice ne contient que des zéros sur sa diagonale, c’est-à-dire qu’on ne peut jamais revenir à l’état i en 1 pas. P =   0 1 0 0.5 0 0.5 1 0 0   0 1 2 1 0.5 0.5 1 Définition 4 (Temps moyen de récurrence d’un état i récurrent) Même si un état est récurrent, l’espérance du temps après lequel la chaîne reviendra en cet état peut être inﬁnie, on note alors Mi = +∞. Dans le cas général, on a : Mi = +∞ X n=1 nf(n) i,i 5 Définition 5 (Chaîne irréductible) Une chaîne de Markov est dite irréduc- tible si son graphe est fortement connexe, c’est-à-dire que pour tout couple (i, j) d’états, un chemin relie uploads/Litterature/ tipe.pdf