Chaîne de Markov à temps continu

Une chaîne de Markov en temps continu ( CTMC ) est un processus stochastique continu dans lequel, pour chaque état, le processus changera d'état en fonction d'une variable aléatoire exponentielle , puis passera à un état différent tel que spécifié par les probabilités d'une matrice stochastique . Une formulation équivalente décrit le processus comme changeant d'état en fonction de la plus petite valeur d'un ensemble de variables aléatoires exponentielles, une pour chaque état possible vers lequel il peut passer, avec les paramètres déterminés par l'état actuel.

Voici un exemple de CTMC à trois états : le processus effectue une transition après la durée spécifiée par le temps de maintien — une variable aléatoire exponentielle , où i est son état actuel. Chaque variable aléatoire est indépendante et telle que , et . Lorsqu'une transition doit être effectuée, le processus se déplace selon la chaîne de sauts , une chaîne de Markov à temps discret avec une matrice stochastique :

De manière équivalente, par la propriété des exponentielles concurrentes , ce CTMC change d'état de l'état i en fonction du minimum de deux variables aléatoires, qui sont indépendantes et telles que pour où les paramètres sont donnés par la matrice Q

Chaque entrée non diagonale peut être calculée comme la probabilité que la chaîne de saut passe de l'état i à l'état j , divisée par le temps de maintien attendu de l'état i . Les entrées diagonales sont choisies de manière à ce que la somme de chaque ligne soit égale à 0.

Un CTMC satisfait la propriété de Markov , selon laquelle son comportement dépend uniquement de son état actuel et non de son comportement passé, en raison de l'absence de mémoire de la distribution exponentielle et des chaînes de Markov à temps discret.

Soit un espace de probabilité, soit un ensemble dénombrable non vide, et soit ( pour « temps »). Equipé de la métrique discrète , afin que nous puissions donner un sens à la continuité droite des fonctions . Une chaîne de Markov en temps continu est définie par :

• Un vecteur de probabilité sur (que nous interpréterons ci-dessous comme la distribution initiale de la chaîne de Markov), et
• Une matrice de taux sur , c'est-à-dire une fonction telle que

1. pour tous les distincts ,
2. pour tout (Même si est infini, cette somme est a priori bien définie (éventuellement égale à ) car chaque terme apparaissant dans la somme est non négatif. A posteriori , nous savons que la somme doit également être finie (non égale à ), puisque nous supposons qu'elle est égale à et nous avons supposé qu'elle a des valeurs réelles. Certains auteurs utilisent plutôt une définition qui est mot pour mot la même à l'exception d'une stipulation modifiée , et disent qu'elle est stable ou totalement stable pour signifier , c'est-à-dire que chaque entrée a des valeurs réelles.)

Notez que les sommes des lignes de sont égales à 0 : ou plus succinctement, . Cette situation contraste avec la situation des chaînes de Markov à temps discret , où toutes les sommes des lignes de la matrice de transition sont égales à un.

Maintenant, soit tel que soit -mesurable. Il existe trois manières équivalentes de définir être Markov avec une distribution initiale et une matrice de taux : via les probabilités de transition ou via la chaîne de saut et les temps de maintien.

En prélude à une définition de probabilité de transition, nous motivons d'abord la définition d'une matrice de taux régulière . Nous utiliserons la matrice de taux de transition pour spécifier la dynamique de la chaîne de Markov en générant une collection de matrices de transition sur ( ), via le théorème suivant.

Nous disons que est régulier pour signifier que nous avons une unicité pour le système ci-dessus, c'est-à-dire qu'il existe exactement une solution. Nous disons que est irrégulier pour signifier que n'est pas régulier. Si est fini, alors il y a exactement une solution, à savoir et donc est régulier. Sinon, est infini, et il existe des matrices de taux de transition irrégulières sur . Si est régulier, alors pour la solution unique , pour chaque , sera une matrice stochastique . Nous supposerons que est régulier du début de la sous-section suivante jusqu'à la fin de cette section, même s'il est conventionnel de ne pas inclure cette hypothèse. (Remarque pour l'expert : nous ne définissons donc pas les chaînes de Markov en temps continu en général mais seulement les chaînes de Markov en temps continu non explosives .)

Soit la solution (unique) du système ( 0 ). (Unicité garantie par notre hypothèse de régularité.) On dit que le système est de Markov avec une distribution initiale et une matrice de taux signifiant : pour tout entier non négatif , pour tout tel que pour tout

En utilisant l'induction et le fait que nous pouvons montrer l'équivalence de l'énoncé ci-dessus contenant ( 1 ) et l'énoncé suivant : pour tout et pour tout entier non négatif , pour tout tel que pour tout tel que (il s'ensuit que ),

Il résulte de la continuité des fonctions ( ) que la trajectoire est presque sûrement continue à droite (par rapport à la métrique discrète sur ) : il existe un ensemble -nul tel que .

Soit continue à droite (quand on se munit de la métrique discrète ). Définir

laisser

être la séquence de temps de maintien associée à , choisir et laisser

être « la séquence d’état » associée à .

La matrice de saut , écrite alternativement si l'on souhaite souligner la dépendance sur , est la matrice où est l' ensemble nul de la fonction

On dit que c'est une chaîne de Markov avec une distribution initiale et une matrice de taux qui signifient : les trajectoires de sont presque sûrement continues à droite, soit une modification de pour avoir (partout) des trajectoires continues à droite, presque sûrement (note aux experts : cette condition dit qu'elle est non explosive), la séquence d'états est une chaîne de Markov à temps discret avec une distribution initiale (propriété de chaîne de saut) et une matrice de transition et (propriété de temps de maintien).

On dit que Markov a une distribution initiale et une matrice de taux qui signifient : pour tout et pour tout , pour tout et pour de petites valeurs strictement positives de , ce qui suit est vrai pour tout tel que :

où le terme est si et sinon , et le terme petit-o dépend d'une certaine manière de .

L'équation ci-dessus montre que peut être considérée comme mesurant la rapidité avec laquelle la transition de à se produit pour , et la rapidité avec laquelle la transition loin de se produit pour .

Les classes communicantes, la transience, la récurrence et la récurrence positive et nulle sont définies de manière identique à celles des chaînes de Markov à temps discret .

Écrivez P( t ) pour la matrice avec les entrées p _ij = P( X _t = j | X ₀ = i ). Alors la matrice P( t ) satisfait l'équation directe, une équation différentielle du premier ordre

où le premier désigne la différentiation par rapport à t . La solution de cette équation est donnée par une matrice exponentielle

Dans un cas simple tel qu'un CTMC sur l'espace d'état {1,2}. La matrice Q générale pour un tel processus est la matrice 2 × 2 suivante avec α , β > 0

La relation ci-dessus pour la matrice directe peut être résolue explicitement dans ce cas pour donner

Le calcul des solutions directes est compliqué dans les matrices plus grandes. Le fait que Q soit le générateur d'un semi-groupe de matrices

est utilisé.

La distribution stationnaire pour un CTMC récurrent irréductible est la distribution de probabilité vers laquelle le processus converge pour de grandes valeurs de t . On observe que pour le processus à deux états considéré précédemment avec P( t ) donné par

comme t → ∞ la distribution tend vers

Observez que chaque ligne a la même distribution car cela ne dépend pas de l'état de départ. Le vecteur de ligne π peut être trouvé en résolvant

avec la contrainte

L'image de droite décrit une chaîne de Markov en temps continu avec un espace d'état {marché haussier, marché baissier, marché stagnant} et une matrice de taux de transition

La distribution stationnaire de cette chaîne peut être trouvée en résolvant , sous réserve de la contrainte que la somme des éléments doit être égale à 1 pour obtenir

L'image de droite décrit une chaîne de Markov à temps discret modélisant Pac-Man avec un espace d'état {1,2,3,4,5,6,7,8,9}. Le joueur contrôle Pac-Man à travers un labyrinthe, en mangeant des pac-dots. Pendant ce temps, il est chassé par des fantômes. Pour plus de commodité, le labyrinthe doit être une petite grille 3x3 et les fantômes se déplacent aléatoirement dans les directions horizontale et verticale. Un passage secret entre les états 2 et 8 peut être utilisé dans les deux sens. Les entrées avec une probabilité nulle sont supprimées dans la matrice de taux de transition suivante :

Cette chaîne de Markov est irréductible, car les fantômes peuvent voler de chaque état à chaque état en un temps fini. En raison du passage secret, la chaîne de Markov est également apériodique, car les fantômes peuvent se déplacer de n'importe quel état à n'importe quel état à la fois dans un nombre pair et impair de transitions d'état. Par conséquent, une distribution stationnaire unique existe et peut être trouvée en résolvant , sous la contrainte que la somme des éléments doit être égale à 1. La solution de cette équation linéaire sous la contrainte est L'état central et les états de bordure 2 et 8 du passage secret adjacent sont les plus visités et les états d'angle sont les moins visités.

Pour un CTMC X _t , le processus inversé dans le temps est défini comme étant . Par le lemme de Kelly, ce processus a la même distribution stationnaire que le processus direct.

Une chaîne est dite réversible si le processus inverse est le même que le processus direct. Le critère de Kolmogorov stipule que la condition nécessaire et suffisante pour qu'un processus soit réversible est que le produit des taux de transition autour d'une boucle fermée soit le même dans les deux sens.

Une méthode pour trouver la distribution de probabilité stationnaire π d' une chaîne de Markov ergodique à temps continu Q consiste à trouver d'abord sa chaîne de Markov intégrée (EMC) . Strictement parlant, l'EMC est une chaîne de Markov régulière à temps discret. Chaque élément de la matrice de probabilité de transition en une étape de l'EMC, S , est noté s _ij et représente la probabilité conditionnelle de transition de l'état i à l'état j . Ces probabilités conditionnelles peuvent être trouvées en

À partir de là, S peut s'écrire comme

où I est la matrice identité et diag( Q ) est la matrice diagonale formée en sélectionnant la diagonale principale de la matrice Q et en définissant tous les autres éléments à zéro.

Pour trouver le vecteur de distribution de probabilité stationnaire, nous devons ensuite trouver tel que

étant un vecteur de ligne, tel que tous les éléments de soient supérieurs à 0 et = 1. À partir de là, π peut être trouvé comme

( S peut être périodique, même si Q ne l'est pas. Une fois π trouvé, il doit être normalisé en un vecteur unitaire .)

Un autre processus à temps discret qui peut être dérivé d'une chaîne de Markov à temps continu est un δ-squelette, la chaîne de Markov (à temps discret) formée en observant X ( t ) à des intervalles de δ unités de temps. Les variables aléatoires X (0), X (δ), X (2δ), ... donnent la séquence des états visités par le δ-squelette.