Chaîne de Markov - Markov chain

Un diagramme représentant un processus de Markov à deux états, avec les états étiquetés E et A. Chaque nombre représente la probabilité que le processus de Markov passe d'un état à un autre, avec la direction indiquée par la flèche. Par exemple, si le processus de Markov est dans l'état A, alors la probabilité qu'il passe à l'état E est de 0,4, tandis que la probabilité qu'il reste dans l'état A est de 0,6.

Une chaîne de Markov ou processus de Markov est un modèle stochastique décrivant une séquence d'événements possibles dans laquelle la probabilité de chaque événement ne dépend que de l'état atteint lors de l'événement précédent. Une séquence dénombrable infinie , dans laquelle la chaîne se déplace d'état à des pas de temps discrets, donne une chaîne de Markov à temps discret (DTMC). Un processus en temps continu est appelé chaîne de Markov en temps continu (CTMC). Il porte le nom du mathématicien russe Andrey Markov .

Les chaînes de Markov ont de nombreuses applications en tant que modèles statistiques de processus réels, tels que l'étude des systèmes de régulation de vitesse dans les véhicules à moteur , les files d'attente ou les files de clients arrivant à un aéroport, les taux de change et la dynamique des populations animales.

Les processus de Markov sont à la base des méthodes générales de simulation stochastique connues sous le nom de chaîne de Markov Monte Carlo , qui sont utilisées pour simuler l'échantillonnage à partir de distributions de probabilité complexes, et ont trouvé une application dans les statistiques bayésiennes , la thermodynamique , la mécanique statistique , la physique , la chimie , l' économie , la finance , le signal traitement , théorie de l' information et traitement de la parole .

Les adjectifs Markovien et Markov sont utilisés pour décrire quelque chose qui est lié à un processus de Markov.

introduction

Le mathématicien russe Andrey Markov

Définition

Un processus de Markov est un processus stochastique qui satisfait la propriété de Markov (parfois caractérisé comme « absence de mémoire »). En termes plus simples, il s'agit d'un processus pour lequel des prédictions peuvent être faites concernant les résultats futurs en se basant uniquement sur son état actuel et, plus important encore, de telles prédictions sont tout aussi bonnes que celles qui pourraient être faites en connaissant l'historique complet du processus. En d'autres termes, conditionnellement à l'état présent du système, ses états futurs et passés sont indépendants .

Une chaîne de Markov est un type de processus de Markov qui a soit un espace d'état discret , soit un ensemble d'indices discrets (représentant souvent le temps), mais la définition précise d'une chaîne de Markov varie. Par exemple, il est courant de définir une chaîne de Markov comme un processus de Markov en temps discret ou continu avec un espace d'état dénombrable (donc quelle que soit la nature du temps), mais il est également courant de définir une chaîne de Markov comme ayant un temps discret dans l'espace d'état dénombrable ou continu (donc quel que soit l'espace d'état).

Types de chaînes de Markov

L' espace d'état et l'index des paramètres temporels du système doivent être spécifiés. Le tableau suivant donne un aperçu des différentes instances de processus de Markov pour différents niveaux de généralité de l'espace d'état et pour le temps discret par rapport au temps continu :

Espace d'état dénombrable Espace d'état continu ou général
Temps discret (temps discret) chaîne de Markov sur un espace d'états dénombrable ou fini Chaîne de Markov sur un espace d'état mesurable (par exemple, chaîne de Harris )
Temps continu Processus de Markov en temps continu ou processus de saut de Markov Tout processus stochastique continu avec la propriété de Markov (par exemple, le processus de Wiener )

Notez qu'il n'y a pas d'accord définitif dans la littérature sur l'utilisation de certains des termes qui signifient des cas particuliers de processus de Markov. Habituellement, le terme « chaîne de Markov » est réservé à un processus avec un ensemble de temps discret, c'est-à-dire une chaîne de Markov à temps discret (DTMC) , mais quelques auteurs utilisent le terme « processus de Markov » pour désigner un processus à temps continu. Chaîne de Markov (CTMC) sans mention explicite. De plus, il existe d'autres extensions des processus de Markov qui sont désignées comme telles mais qui ne relèvent pas nécessairement de l'une de ces quatre catégories (voir modèle de Markov ). De plus, l'indice de temps n'a pas nécessairement besoin d'être à valeur réelle ; comme avec l'espace d'état, il existe des processus concevables qui se déplacent à travers des ensembles d'index avec d'autres constructions mathématiques. Notez que la chaîne de Markov en temps continu de l'espace d'état général est générale à un degré tel qu'elle n'a pas de terme désigné.

Alors que le paramètre temporel est généralement discret, l' espace d'état d'une chaîne de Markov n'a pas de restrictions généralement acceptées : le terme peut faire référence à un processus sur un espace d'état arbitraire. Cependant, de nombreuses applications des chaînes de Markov utilisent des espaces d'états finis ou dénombrables infinis , qui ont une analyse statistique plus simple. Outre les paramètres d'index temporel et d'espace d'état, il existe de nombreuses autres variantes, extensions et généralisations (voir Variations ). Par souci de simplicité, la majeure partie de cet article se concentre sur le cas de l'espace d'état discret à temps discret, sauf mention contraire.

Transitions

Les changements d'état du système sont appelés transitions. Les probabilités associées à divers changements d'état sont appelées probabilités de transition. Le processus est caractérisé par un espace d'état, une matrice de transition décrivant les probabilités de transitions particulières et un état initial (ou distribution initiale) à travers l'espace d'état. Par convention, nous supposons que tous les états et transitions possibles ont été inclus dans la définition du processus, il y a donc toujours un état suivant et le processus ne se termine pas.

Un processus aléatoire à temps discret implique un système qui est dans un certain état à chaque étape, l'état changeant de manière aléatoire entre les étapes. Les étapes sont souvent considérées comme des moments dans le temps, mais elles peuvent tout aussi bien se référer à la distance physique ou à toute autre mesure discrète. Formellement, les étapes sont les entiers ou les nombres naturels , et le processus aléatoire est un mappage de ceux-ci aux états. La propriété de Markov indique que la distribution de probabilité conditionnelle pour le système à l'étape suivante (et en fait à toutes les étapes futures) ne dépend que de l'état actuel du système, et pas en plus de l'état du système aux étapes précédentes.

Le système changeant de manière aléatoire, il est généralement impossible de prédire avec certitude l'état d'une chaîne de Markov à un moment donné dans le futur. Cependant, les propriétés statistiques de l'avenir du système peuvent être prédites. Dans de nombreuses applications, ce sont ces propriétés statistiques qui sont importantes.

Histoire

Markov a étudié les processus de Markov au début du 20e siècle, publiant son premier article sur le sujet en 1906. Les processus de Markov en temps continu ont été découverts bien avant les travaux d' Andrey Markov au début du 20e siècle sous la forme du processus de Poisson . Markov s'intéressait à l'étude d'une extension des séquences aléatoires indépendantes, motivé par un désaccord avec Pavel Nekrasov qui prétendait que l'indépendance était nécessaire pour que la loi faible des grands nombres s'applique . Dans son premier article sur les chaînes de Markov, publié en 1906, Markov montra que, dans certaines conditions, les résultats moyens de la chaîne de Markov convergeraient vers un vecteur fixe de valeurs, prouvant ainsi une loi faible des grands nombres sans l'hypothèse d'indépendance, qui avait été communément considéré comme une exigence pour que de telles lois mathématiques soient valables. Markov a ensuite utilisé des chaînes de Markov pour étudier la distribution des voyelles dans Eugène Onéguine , écrit par Alexandre Pouchkine , et a prouvé un théorème central limite pour de telles chaînes.

En 1912, Henri Poincaré étudie les chaînes de Markov sur des groupes finis dans le but d'étudier le brassage des cartes. Parmi les autres premières utilisations des chaînes de Markov, citons un modèle de diffusion, introduit par Paul et Tatyana Ehrenfest en 1907, et un processus de branchement, introduit par Francis Galton et Henry William Watson en 1873, précédant les travaux de Markov. Après les travaux de Galton et Watson, il a été révélé plus tard que leur processus de ramification avait été indépendamment découvert et étudié environ trois décennies plus tôt par Irénée-Jules Bienaymé . À partir de 1928, Maurice Fréchet s'intéresse aux chaînes de Markov, ce qui l'amène finalement à publier en 1938 une étude détaillée sur les chaînes de Markov.

Andrei Kolmogorov a développé dans un article de 1931 une grande partie de la première théorie des processus de Markov en temps continu. Kolmogorov s'est en partie inspiré des travaux de Louis Bachelier de 1900 sur les fluctuations du marché boursier ainsi que des travaux de Norbert Wiener sur le modèle d'Einstein du mouvement brownien. Il a introduit et étudié un ensemble particulier de processus de Markov connus sous le nom de processus de diffusion, où il a dérivé un ensemble d'équations différentielles décrivant les processus. Indépendamment des travaux de Kolmogorov, Sydney Chapman a dérivé dans un article de 1928 une équation, maintenant appelée équation de Chapman-Kolmogorov , d'une manière moins rigoureuse sur le plan mathématique que Kolmogorov, tout en étudiant le mouvement brownien. Les équations différentielles sont maintenant appelées équations de Kolmogorov ou équations de Kolmogorov-Chapman. D'autres mathématiciens qui ont contribué de manière significative aux fondements des processus de Markov incluent William Feller , à partir des années 1930, puis plus tard Eugene Dynkin , à partir des années 1950.

Exemples

Les marches aléatoires basées sur des nombres entiers et le problème de la ruine du joueur sont des exemples de processus de Markov. Certaines variantes de ces processus ont été étudiées des centaines d'années auparavant dans le contexte de variables indépendantes. Deux exemples importants de processus de Markov sont le processus de Wiener , également connu sous le nom de processus de mouvement brownien , et le processus de Poisson , qui sont considérés comme les processus stochastiques les plus importants et les plus centraux dans la théorie des processus stochastiques. Ces deux processus sont des processus de Markov en temps continu, tandis que les marches aléatoires sur les entiers et le problème de la ruine du joueur sont des exemples de processus de Markov en temps discret.

Une célèbre chaîne de Markov est ce qu'on appelle la "marche de l'ivrogne", une marche aléatoire sur la droite numérique où, à chaque étape, la position peut changer de +1 ou -1 avec une probabilité égale. A partir de n'importe quelle position, il y a deux transitions possibles, vers l'entier suivant ou précédent. Les probabilités de transition dépendent uniquement de la position actuelle et non de la manière dont la position a été atteinte. Par exemple, les probabilités de transition de 5 à 4 et de 5 à 6 sont toutes les deux de 0,5, et toutes les autres probabilités de transition de 5 sont de 0. Ces probabilités sont indépendantes du fait que le système était auparavant en 4 ou 6.

Un autre exemple est les habitudes alimentaires d'une créature qui ne mange que du raisin, du fromage ou de la laitue, et dont les habitudes alimentaires sont conformes aux règles suivantes :

Markov-fromage-laitue-raisins.svg
  • Il mange exactement une fois par jour.
  • S'il a mangé du fromage aujourd'hui, demain il mangera de la laitue ou du raisin avec une probabilité égale.
  • S'il a mangé du raisin aujourd'hui, demain il mangera du raisin avec une probabilité de 1/10, du fromage avec une probabilité de 4/10 et de la laitue avec une probabilité de 5/10.
  • S'il a mangé de la laitue aujourd'hui, demain il mangera du raisin avec une probabilité de 4/10 ou du fromage avec une probabilité de 6/10. Il ne mangera plus de laitue demain.

Les habitudes alimentaires de cette créature peuvent être modélisées avec une chaîne de Markov puisque son choix de demain dépend uniquement de ce qu'elle a mangé aujourd'hui, pas de ce qu'elle a mangé hier ou à n'importe quel autre moment dans le passé. Une propriété statistique qui pourrait être calculée est le pourcentage attendu, sur une longue période, des jours pendant lesquels la créature mangera du raisin.

Une série d'événements indépendants (par exemple, une série de lancers de pièces) satisfait la définition formelle d'une chaîne de Markov. Cependant, la théorie n'est généralement appliquée que lorsque la distribution de probabilité de l'étape suivante dépend de manière non triviale de l'état actuel.

Un exemple non markovien

Supposons qu'il y ait un porte-monnaie contenant cinq quarts (chacun d'une valeur de 25 ), cinq dimes (chacun d'une valeur de 10 ) et cinq nickels (chacun d'une valeur de 5 ¢), et un par un, les pièces sont tirées au hasard du porte-monnaie et sont posé sur une table. Si représente la valeur totale des pièces posées sur la table après n tirages, avec , alors la séquence n'est pas un processus de Markov.

Pour comprendre pourquoi c'est le cas, supposons que dans les six premiers tirages, les cinq nickels et un quart soient tirés. Ainsi . Si nous connaissons non seulement , mais également les valeurs antérieures, nous pouvons alors déterminer quelles pièces ont été tirées et nous savons que la prochaine pièce ne sera pas un nickel ; nous pouvons donc déterminer cela avec probabilité 1. Mais si nous ne connaissons pas les valeurs antérieures, alors en nous basant uniquement sur la valeur, nous pourrions deviner que nous avons tiré quatre dimes et deux nickels, auquel cas il serait certainement possible de tirer un autre nickel Suivant. Ainsi, nos suppositions sur sont impactées par notre connaissance des valeurs avant .

Cependant, il est possible de modéliser ce scénario comme un processus de Markov. Au lieu de définir pour représenter la valeur totale des pièces sur la table, nous pourrions définir pour représenter le nombre des différents types de pièces sur la table. Par exemple, pourrait être défini pour représenter l'état où il y a un quart, zéro centime et cinq nickels sur la table après 6 tirages un par un. Ce nouveau modèle serait représenté par 216 états possibles (c'est-à-dire 6x6x6 états, puisque chacun des trois types de pièces pourrait avoir de zéro à cinq pièces sur la table à la fin des 6 tirages). Supposons que le premier tirage donne l'état . La probabilité d'y parvenir dépend maintenant de ; par exemple, l'état n'est pas possible. Après le deuxième tirage, le troisième tirage dépend des pièces qui ont été tirées jusqu'à présent, mais plus seulement des pièces qui ont été tirées pour le premier état (puisque des informations probabilistes importantes ont depuis été ajoutées au scénario). De cette façon, la probabilité de l' État dépend exclusivement du résultat de l' État.

Définition formelle

Chaîne de Markov à temps discret

Une chaîne de Markov à temps discret est une séquence de variables aléatoires X 1 , X 2 , X 3 , ... avec la propriété de Markov , à savoir que la probabilité de passer à l'état suivant ne dépend que de l'état présent et non de l'état précédent. États:

si les deux probabilités conditionnelles sont bien définies, c'est-à-dire si

Les valeurs possibles de X i forment un ensemble dénombrable S appelé espace d'état de la chaîne.

Variantes

  • Les chaînes de Markov homogènes dans le temps sont des processus où
    pour tout n . La probabilité de la transition est indépendante de n .
  • Les chaînes de Markov stationnaires sont des processus où
    pour tout n et k . Chaque chaîne stationnaire peut être prouvée comme étant homogène dans le temps par la règle de Bayes.
    Une condition nécessaire et suffisante pour qu'une chaîne de Markov homogène dans le temps soit stationnaire est que la distribution de soit une distribution stationnaire de la chaîne de Markov.
  • Une chaîne de Markov à mémoire (ou une chaîne de Markov d'ordre m ) où m est fini, est un processus satisfaisant
    En d'autres termes, l'état futur dépend des m états passés . Il est possible de construire une chaîne à partir de laquelle a la propriété 'classique' de Markov en prenant comme espace d'état les m -uplets ordonnés de valeurs X , c'est-à-dire .

Chaîne de Markov en temps continu

Une chaîne de Markov en temps continu ( X t ) t  0 est définie par un espace d'état fini ou dénombrable S , une matrice de taux de transition Q avec des dimensions égales à celle de l'espace d'état et une distribution de probabilité initiale définie sur l'espace d'état. Pour i  ≠  j , les éléments q ij sont non négatifs et décrivent la vitesse des transitions du processus de l'état i à l'état j . Les éléments q ii sont choisis de telle sorte que chaque ligne de la matrice de taux de transition soit égale à zéro, tandis que les sommes de ligne d'une matrice de transition de probabilité dans une chaîne de Markov (discrète) sont toutes égales à un.

Il existe trois définitions équivalentes du processus.

Définition infinitésimale

La chaîne de Markov en temps continu est caractérisée par les taux de transition, les dérivées par rapport au temps des probabilités de transition entre les états i et j.

Soit la variable aléatoire décrivant l'état du processus à l'instant t , et supposons que le processus est dans un état i à l'instant t . Alors, sachant , est indépendant des valeurs précédentes , et comme h → 0 pour tout j et pour tout t ,

,

où est le delta de Kronecker , en utilisant la notation little-o . Le peut être considéré comme la mesure de la rapidité avec laquelle la transition de i à j se produit.

Définition de la chaîne de saut/du temps d'attente

Définir une chaîne de Markov à temps discret Y n pour décrire le n ième saut du processus et les variables S 1 , S 2 , S 3 , ... pour décrire les temps de maintien dans chacun des états où S i suit la distribution exponentielle avec le taux paramètre − q Y i Y i .

Définition de la probabilité de transition

Pour toute valeur n = 0, 1, 2, 3, ... et les temps indexés jusqu'à cette valeur de n : t 0 , t 1 , t 2 , ... et tous les états enregistrés à ces instants i 0 , i 1 , i 2 , i 3 , ... il retient que

p ij est la solution de l' équation directe (une équation différentielle du premier ordre )

avec la condition initiale P(0) est la matrice identité .

Espace d'état fini

Si l'espace d'état est fini , la distribution de probabilité de transition peut être représentée par une matrice , appelée matrice de transition , avec le ( i , j ) ième élément de P égal à

Étant donné que chaque ligne de P somme à un et que tous les éléments sont non négatifs, P est une matrice stochastique droite .

Relation de distribution stationnaire aux vecteurs propres et aux simplexes

Une distribution stationnaire π est (ligne) vecteur, dont les entrées sont non-négative et la somme de 1, est inchangé par l'opération de la matrice de transition P sur elle et est donc définie par

En comparant cette définition avec celle d'un vecteur propre on voit que les deux concepts sont liés et que

est un multiple normalisé ( ) d'un vecteur propre gauche e de la matrice de transition P avec une valeur propre de 1. S'il y a plus d'un vecteur propre unitaire, alors une somme pondérée des états stationnaires correspondants est également un état stationnaire. Mais pour une chaîne de Markov, on est généralement plus intéressé par un état stationnaire qui est la limite de la séquence de distributions pour une distribution initiale.

Les valeurs d'une distribution stationnaire sont associées à l'espace d'état de P et ses vecteurs propres ont leurs proportions relatives conservées. Puisque les composantes de π sont positives et que la contrainte selon laquelle leur somme est l'unité peut être réécrite car nous voyons que le produit scalaire de π avec un vecteur dont toutes les composantes sont 1 est l'unité et que π repose sur un simplexe .

Chaîne de Markov homogène dans le temps avec un espace d'état fini

Si la chaîne de Markov est homogène dans le temps, alors la matrice de transition P est la même après chaque étape, de sorte que la probabilité de transition à k étapes peut être calculée comme la puissance k de la matrice de transition, P k .

Si la chaîne de Markov est irréductible et apériodique, alors il existe une unique distribution stationnaire π . En outre, dans ce cas , P k converge vers une matrice et un rang dans lequel chaque rangée est la distribution stationnaire π :

1 est le vecteur colonne avec toutes les entrées égales à 1. Ceci est indiqué par le théorème de Perron-Frobenius . Si, par quelque moyen que ce soit, est trouvée, alors la distribution stationnaire de la chaîne de Markov en question peut être facilement déterminée pour toute distribution de départ, comme cela sera expliqué ci-dessous.

Pour certaines matrices stochastiques P , la limite n'existe pas alors que la distribution stationnaire existe, comme le montre cet exemple :

(Cet exemple illustre une chaîne de Markov périodique.)

Étant donné qu'il existe un certain nombre de cas particuliers différents à prendre en compte, le processus de recherche de cette limite, si elle existe, peut être une tâche longue. Cependant, il existe de nombreuses techniques qui peuvent aider à trouver cette limite. Soit P une matrice n × n , et définissons

C'est toujours vrai que

La soustraction de Q des deux côtés et la factorisation donnent alors

I n est la matrice identité de taille n , et 0 n , n est la matrice zéro de taille n × n . La multiplication de matrices stochastiques donne toujours une autre matrice stochastique, donc Q doit être une matrice stochastique (voir la définition ci-dessus). Il suffit parfois d'utiliser l'équation matricielle ci-dessus et le fait que Q est une matrice stochastique à résoudre pour Q . Y compris le fait que la somme de chacune des lignes de P est 1, il y a n+1 équations pour déterminer n inconnues, il est donc plus facile de calculer si d'une part on sélectionne une ligne dans Q et substitue chacun de ses éléments par un , et de l'autre on substitue l'élément correspondant (celui de la même colonne) dans le vecteur 0 , et ensuite on multiplie à gauche ce dernier vecteur par l'inverse de l'ancienne matrice transformée pour trouver Q .

Voici une méthode pour le faire : d'abord, définissez la fonction f ( A ) pour renvoyer la matrice A avec sa colonne la plus à droite remplacée par tous les 1. Si [ f ( PI n )] −1 existe alors

Expliquez : L'équation matricielle originale est équivalente à un système de n×n équations linéaires dans n×n variables. Et il y a n équations plus linéaires du fait que Q est une matrice stochastique droite dont chaque ligne est égale à 1. Il a donc besoin de n×n équations linéaires indépendantes des (n×n+n) équations pour résoudre les n× n variables. Dans cet exemple, les n équations de « Q multiplié par la colonne la plus à droite de (P-In) » ont été remplacées par les n stochastiques.

Une chose à noter est que si P a un élément P i , i sur sa diagonale principale qui est égal à 1 et que la i ème ligne ou colonne est par ailleurs remplie de 0, alors cette ligne ou colonne restera inchangée dans tous les puissances P k . Par conséquent, la i ème ligne ou une colonne de Q ont les 1 et les 0 dans les mêmes positions que dans P .

Vitesse de convergence vers la distribution stationnaire

Comme indiqué précédemment, à partir de l'équation (si elle existe), la distribution stationnaire (ou stationnaire) π est un vecteur propre gauche de la matrice stochastique de ligne P . Ensuite, en supposant que P est diagonalisable ou de manière équivalente que P a n vecteurs propres linéairement indépendants, la vitesse de convergence est élaborée comme suit. (Pour les matrices non diagonalisables, c'est-à-dire défectueuses , on peut commencer par la forme normale de Jordan de P et procéder de la même manière avec un ensemble d'arguments un peu plus complexe.

Soit U la matrice des vecteurs propres (chacun normalisé pour avoir une norme L2 égale à 1) où chaque colonne est un vecteur propre gauche de P et soit Σ la matrice diagonale des valeurs propres gauches de P , c'est-à-dire Σ = diag( λ 1 , X 2 , X 3 , ..., λ n ). Puis par décomposition propre

Soit les valeurs propres énumérées telles que :

Puisque P est une ligne matrice stochastique, la plus grande valeur propre gauche est 1. S'il y a une distribution stationnaire unique, alors la plus grande valeur propre et le correspondant vecteur propre est unique aussi (parce qu'il n'y a pas d' autre π qui permet de résoudre l'équation de distribution stationnaire au- dessus). Soit u i la i- ième colonne de la matrice U , c'est-à-dire que u i est le vecteur propre gauche de P correspondant à λ i . Soit également x un vecteur ligne de longueur n qui représente une distribution de probabilité valide ; puisque les vecteurs propres u i s'étendent, nous pouvons écrire

Si nous multiplions x avec P à partir de la droite et continuons cette opération avec les résultats, nous obtenons à la fin la distribution stationnaire π . En d'autres termes, π = u ixPP ... P = xP k comme k → ∞. Cela signifie

Puisque π = u 1 , π ( k ) les approches de tc que k → ∞ , avec une vitesse de l'ordre de λ 2 / λ 1 de façon exponentielle. Cela s'ensuit car donc λ 2 / λ 1 est le terme dominant. Plus le rapport est petit, plus la convergence est rapide. Le bruit aléatoire dans la distribution d'état π peut également accélérer cette convergence vers la distribution stationnaire.

Espace d'état général

chaînes Harris

De nombreux résultats pour les chaînes de Markov avec espace d'état fini peuvent être généralisés aux chaînes avec espace d'état indénombrable à travers les chaînes de Harris .

L'utilisation des chaînes de Markov dans les méthodes de Monte Carlo par chaînes de Markov couvre les cas où le processus suit un espace d'état continu.

Chaînes de Markov interagissant localement

Considérer une collection de chaînes de Markov dont l'évolution tient compte de l'état des autres chaînes de Markov, est lié à la notion de chaînes de Markov interagissant localement . Cela correspond à la situation où l'espace d'état a une forme de produit (cartésienne). Voir système de particules en interaction et automates cellulaires stochastiques (automates cellulaires probabilistes). Voir par exemple Interaction des processus de Markov ou

Propriétés

Deux états communiquent entre eux si les deux sont atteignables l'un de l'autre par une séquence de transitions ayant une probabilité positive. C'est une relation d'équivalence qui donne un ensemble de classes communicantes. Une classe est fermée si la probabilité de sortir de la classe est nulle. Une chaîne de Markov est irréductible s'il existe une classe communicante, l'espace d'état.

Un état i a une période si est le plus grand commun diviseur du nombre de transitions par lesquelles i peut être atteint, à partir de i . C'est-à-dire:

Un état i est dit transitoire si, à partir de i , il existe une probabilité non nulle que la chaîne ne revienne jamais à i . C'est récurrent sinon. Pour un état récurrent i , le temps d'impact moyen est défini comme :

L'état i est récurrent positif s'il est fini et récurrent nul sinon. La périodicité, la fugacité, la récurrence et la récurrence positive et nulle sont des propriétés de classe, c'est-à-dire que si un état a la propriété, alors tous les états de sa classe communicante ont la propriété.

Un état i est dit absorbant s'il n'y a pas de transitions sortantes de l'état.

Ergodicité

Un état i est dit ergodique s'il est apériodique et récurrent positif. En d'autres termes, un état i est ergodique s'il est récurrent, a une période de 1 et a un temps de récurrence moyen fini. Si tous les états d'une chaîne de Markov irréductible sont ergodiques, alors la chaîne est dite ergodique.

On peut montrer qu'une chaîne de Markov irréductible à l'état fini est ergodique si elle a un état apériodique. Plus généralement, une chaîne de Markov est ergodique s'il existe un nombre N tel que n'importe quel état puisse être atteint à partir de n'importe quel autre état en n'importe quel nombre de pas inférieur ou égal à un nombre N . Dans le cas d'une matrice de transition entièrement connectée, où toutes les transitions ont une probabilité non nulle, cette condition est remplie avec  N  = 1.

Une chaîne de Markov avec plus d'un état et une seule transition sortante par état est soit non irréductible, soit non apériodique, donc ne peut pas être ergodique.

Représentations markoviennes

Dans certains cas, des processus apparemment non markoviens peuvent encore avoir des représentations markoviennes, construites en élargissant le concept des états « actuel » et « futur ». Par exemple, soit X un processus non-markovien. Ensuite, définissez un processus Y , tel que chaque état de Y représente un intervalle de temps d'états de X . Mathématiquement, cela prend la forme :

Si Y a la propriété de Markov, alors c'est une représentation markovienne de X .

Un exemple de processus non-markovien avec une représentation markovienne est une série temporelle autorégressive d'ordre supérieur à un.

Temps de frappe

Le temps de frappe est le temps, commençant dans un ensemble d'états donné jusqu'à ce que la chaîne arrive dans un état ou un ensemble d'états donné. La distribution d'une telle période de temps a une distribution de type phase. La distribution la plus simple est celle d'une seule transition à distribution exponentielle.

Temps de frappe attendus

Pour un sous - ensemble d'états A  ⊆  S , le vecteur k A de frapper fois (où élément représente la valeur attendue , à partir de l' état i que la chaîne entre dans l' un des états dans l'ensemble A ) est le minimum de solution non négative à

Inversion du temps

Pour un CTMC X t , le processus inversé dans le temps est défini comme étant . D'après 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 inversé 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 doit être le même dans les deux sens.

Chaîne de Markov intégrée

Un procédé pour trouver la distribution de probabilité stationnaire , π , d'une ergodique chaîne de Markov à temps continu, Q , est en trouvant d' abord sa chaîne de Markov intégré (EMC) . À proprement parler, l'EMC est une chaîne de Markov régulière à temps discret, parfois appelée processus de saut . Chaque élément de la matrice de probabilité de transition à une étape de l'EMC, S , est noté s ij , et représente la probabilité conditionnelle de passer de l'état i à l'état j . Ces probabilités conditionnelles peuvent être trouvées par

A partir de là, S peut s'écrire

I est la matrice identité et diag( Q ) est la matrice diagonale formée en sélectionnant la diagonale principale dans la matrice Q et en mettant tous les autres éléments à zéro.

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

avec étant un vecteur ligne, tel que tous les éléments dans sont 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 que π est 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 d'états visités par le -squelette.

Types spéciaux de chaînes de Markov

modèle de Markov

Les modèles de Markov sont utilisés pour modéliser des systèmes changeants. Il existe 4 grands types de modèles, qui généralisent les chaînes de Markov selon que chaque état séquentiel est observable ou non, et si le système doit être ajusté sur la base des observations faites :

L'état du système est entièrement observable L'état du système est partiellement observable
Le système est autonome chaîne de Markov Modèle de Markov caché
Le système est contrôlé Processus de décision de Markov Processus décisionnel de Markov partiellement observable

schéma de Bernoulli

Un schéma de Bernoulli est un cas particulier d'une chaîne de Markov où la matrice de probabilité de transition a des lignes identiques, ce qui signifie que l'état suivant est même indépendant de l'état actuel (en plus d'être indépendant des états passés). Un schéma de Bernoulli avec seulement deux états possibles est connu sous le nom de processus de Bernoulli .

Notez, cependant, par le théorème d'isomorphisme d'Ornstein , que chaque chaîne de Markov apériodique et irréductible est isomorphe à un schéma de Bernoulli; ainsi, on pourrait également prétendre que les chaînes de Markov sont un « cas particulier » des schémas de Bernoulli. L'isomorphisme nécessite généralement un recodage compliqué. Le théorème de l'isomorphisme est même un peu plus fort : il énonce que tout processus stochastique stationnaire est isomorphe à un schéma de Bernoulli ; la chaîne de Markov n'en est qu'un exemple.

Sous-shift de type fini

Lorsque la matrice de Markov est remplacée par la matrice d'adjacence d'un graphe fini , le décalage résultant est en termes de chaîne de Markov topologique ou de sous- décalage de type fini . Une matrice de Markov compatible avec la matrice d'adjacence peut alors fournir une mesure sur le sous-shift. De nombreux systèmes dynamiques chaotiques sont des chaînes de Markov isomorphes à topologiques ; exemples difféomorphismes de collecteurs fermés , le système Prouhet-Thue-Morse , le système de Chacon , systèmes Sofic , des systèmes sans contexte et les systèmes de blocs de codage .

Applications

La recherche a rapporté l'application et l'utilité des chaînes de Markov dans un large éventail de sujets tels que la physique, la chimie, la biologie, la médecine, la musique, la théorie des jeux et les sports.

La physique

Les systèmes markoviens apparaissent abondamment en thermodynamique et en mécanique statistique , chaque fois que des probabilités sont utilisées pour représenter des détails inconnus ou non modélisés du système, si l'on peut supposer que la dynamique est invariante dans le temps et qu'aucune histoire pertinente n'a besoin d'être considérée qui n'est pas déjà incluse dans la description de l'état. Par exemple, un état thermodynamique fonctionne sous une distribution de probabilité difficile ou coûteuse à acquérir. Par conséquent, la méthode de Markov Chain Monte Carlo peut être utilisée pour tirer des échantillons au hasard d'une boîte noire pour approximer la distribution de probabilité des attributs sur une gamme d'objets.

Les chemins, dans la formulation intégrale de chemin de la mécanique quantique, sont des chaînes de Markov.

Les chaînes de Markov sont utilisées dans les simulations QCD sur réseau .

Chimie

Cinétique de Michaelis-Menten . L'enzyme (E) se lie à un substrat (S) et produit un produit (P). Chaque réaction est une transition d'état dans une chaîne de Markov.

Un réseau réactionnel est un système chimique impliquant de multiples réactions et espèces chimiques. Les modèles stochastiques les plus simples de tels réseaux traitent le système comme une chaîne de Markov à temps continu avec l'état étant le nombre de molécules de chaque espèce et avec des réactions modélisées comme des transitions possibles de la chaîne. Les chaînes de Markov et les processus de Markov en temps continu sont utiles en chimie lorsque les systèmes physiques se rapprochent étroitement de la propriété de Markov. Par exemple, imaginez un grand nombre n de molécules en solution dans l'état A, chacune pouvant subir une réaction chimique jusqu'à l'état B avec une certaine vitesse moyenne. Peut-être que la molécule est une enzyme, et les états se réfèrent à la façon dont elle est repliée. L'état d'une seule enzyme suit une chaîne de Markov, et puisque les molécules sont essentiellement indépendantes les unes des autres, le nombre de molécules dans l'état A ou B à la fois est n fois la probabilité qu'une molécule donnée soit dans cet état.

Le modèle classique de l'activité enzymatique, la cinétique de Michaelis-Menten , peut être considéré comme une chaîne de Markov, où à chaque pas de temps la réaction se déroule dans une certaine direction. Alors que Michaelis-Menten est assez simple, des réseaux de réaction beaucoup plus compliqués peuvent également être modélisés avec des chaînes de Markov.

Un algorithme basé sur une chaîne de Markov a également été utilisé pour concentrer la croissance de produits chimiques in silico basée sur des fragments vers une classe souhaitée de composés tels que des médicaments ou des produits naturels. Au fur et à mesure qu'une molécule croît, un fragment est sélectionné à partir de la molécule naissante comme état « actuel ». Il n'est pas conscient de son passé (c'est-à-dire qu'il n'est pas conscient de ce qui lui est déjà lié). Il passe ensuite à l'état suivant lorsqu'un fragment lui est attaché. Les probabilités de transition sont entraînées sur des bases de données de classes authentiques de composés.

De plus, la croissance (et la composition) des copolymères peut être modélisée à l'aide de chaînes de Markov. Sur la base des rapports de réactivité des monomères qui composent la chaîne polymère en croissance, la composition de la chaîne peut être calculée (par exemple, si les monomères ont tendance à s'ajouter en alternance ou en longues séries du même monomère). En raison des effets stériques , les effets de Markov de second ordre peuvent également jouer un rôle dans la croissance de certaines chaînes polymères.

De même, il a été suggéré que la cristallisation et la croissance de certains matériaux d'oxyde de super-réseau épitaxié peuvent être décrites avec précision par des chaînes de Markov.

La biologie

Les chaînes de Markov sont utilisées dans divers domaines de la biologie. Les exemples notables incluent :

Essai

Plusieurs théoriciens ont proposé l'idée du test statistique des chaînes de Markov (MCST), une méthode consistant à joindre des chaînes de Markov pour former une " couverture de Markov ", en organisant ces chaînes en plusieurs couches récursives ("wafering") et en produisant des ensembles de tests plus efficaces - des échantillons - en remplacement des tests exhaustifs. Les MCST ont également des utilisations dans les réseaux basés sur l'état temporel ; L'article de Chilukuri et al. intitulé "Temporal Uncertainty Reasoning Networks for Evidence Fusion with Applications to Object Detection and Tracking" (ScienceDirect) présente un contexte et une étude de cas pour l'application des MCST à un plus large éventail d'applications.

Variabilité de l'irradiance solaire

Les évaluations de la variabilité de l'irradiance solaire sont utiles pour les applications d' énergie solaire . La variabilité de l'irradiance solaire à n'importe quel endroit au cours du temps est principalement une conséquence de la variabilité déterministe de la trajectoire du soleil à travers le dôme du ciel et de la variabilité de la nébulosité. La variabilité de l'irradiance solaire accessible à la surface de la Terre a été modélisée à l'aide de chaînes de Markov, y compris également la modélisation des deux états de clair et de nébulosité sous la forme d'une chaîne de Markov à deux états.

Reconnaissance de la parole

Les modèles de Markov cachés sont à la base de la plupart des systèmes de reconnaissance vocale automatique modernes.

Théorie de l'information

Les chaînes de Markov sont utilisées tout au long du traitement de l'information. Le célèbre article de 1948 de Claude Shannon , A Mathematical Theory of Communication , qui en une seule étape a créé le domaine de la théorie de l' information , s'ouvre en introduisant le concept d' entropie à travers la modélisation markovienne de la langue anglaise. De tels modèles idéalisés peuvent saisir bon nombre des régularités statistiques des systèmes. Même sans décrire parfaitement la structure complète du système, de tels modèles de signaux peuvent permettre une compression de données très efficace grâce à des techniques de codage entropique telles que le codage arithmétique . Ils permettent également une estimation d'état et une reconnaissance de formes efficaces . Les chaînes de Markov jouent également un rôle important dans l' apprentissage par renforcement .

Les chaînes de Markov sont également à la base des modèles de Markov cachés, qui sont un outil important dans des domaines aussi divers que les réseaux téléphoniques (qui utilisent l' algorithme de Viterbi pour la correction d'erreurs), la reconnaissance vocale et la bioinformatique (comme dans la détection de réarrangements).

L' algorithme de compression de données sans perte LZMA combine les chaînes de Markov avec la compression Lempel-Ziv pour obtenir des taux de compression très élevés.

Théorie des files d'attente

Les chaînes de Markov sont à la base du traitement analytique des files d'attente ( théorie des files d' attente ). Agner Krarup Erlang a initié le sujet en 1917. Cela les rend essentiels pour optimiser les performances des réseaux de télécommunications, où les messages doivent souvent rivaliser pour des ressources limitées (comme la bande passante).

De nombreux modèles de files d'attente utilisent des chaînes de Markov en temps continu. Par exemple, une file d'attente M/M/1 est un CTMC sur les entiers non négatifs où les transitions ascendantes de i à i  + 1 se produisent au taux λ selon un processus de Poisson et décrivent les arrivées d'emplois, tandis que les transitions de i à i  – 1 (pour i  > 1) se produisent au taux μ (les temps de service des tâches sont distribués de manière exponentielle) et décrivent les services terminés (départs) de la file d'attente.

Applications Internet

Un diagramme d'état qui représente l'algorithme PageRank avec une probabilité de transition de M, ou .

Le PageRank d'une page Web tel qu'utilisé par Google est défini par une chaîne de Markov. C'est la probabilité d'être à la page dans la distribution stationnaire sur la chaîne de Markov suivante sur toutes les pages Web (connues). Si est le nombre de pages Web connues et qu'une page a des liens vers elle, alors il y a une probabilité de transition pour toutes les pages qui sont liées et pour toutes les pages qui ne sont pas liées. Le paramètre est considéré comme étant d'environ 0,15.

Les modèles de Markov ont également été utilisés pour analyser le comportement de navigation Web des utilisateurs. La transition de lien Web d'un utilisateur sur un site Web particulier peut être modélisée à l'aide de modèles de Markov de premier ou de second ordre et peut être utilisée pour faire des prédictions concernant la navigation future et pour personnaliser la page Web pour un utilisateur individuel.

Statistiques

Les méthodes de chaîne de Markov sont également devenues très importantes pour générer des séquences de nombres aléatoires afin de refléter avec précision des distributions de probabilité souhaitées très compliquées, via un processus appelé chaîne de Markov Monte Carlo (MCMC). Ces dernières années, cela a révolutionné la praticabilité des méthodes d' inférence bayésienne , permettant de simuler un large éventail de distributions postérieures et de trouver leurs paramètres numériquement.

Économie et finance

Les chaînes de Markov sont utilisées en finance et en économie pour modéliser une variété de phénomènes différents, notamment la distribution des revenus, la distribution de la taille des entreprises, les prix des actifs et les krachs boursiers. DG Champernowne a construit un modèle de chaîne de Markov de la distribution des revenus en 1953. Herbert A. Simon et le co-auteur Charles Bonini ont utilisé un modèle de chaîne de Markov pour dériver une distribution de Yule stationnaire de la taille des entreprises. Louis Bachelier a été le premier à observer que les cours boursiers suivaient une marche aléatoire. La marche aléatoire a ensuite été considérée comme une preuve en faveur de l' hypothèse du marché efficace et les modèles de marche aléatoire étaient populaires dans la littérature des années 1960. Les modèles de changement de régime des cycles économiques ont été popularisés par James D. Hamilton (1989), qui a utilisé une chaîne de Markov pour modéliser les changements entre les périodes de croissance élevée et faible du PIB (ou, à défaut, les expansions économiques et les récessions). Un exemple plus récent est le modèle multifractal à commutation de Markov de Laurent E. Calvet et Adlai J. Fisher, qui s'appuie sur la commodité des modèles de changement de régime antérieurs. Il utilise une chaîne de Markov arbitrairement grande pour déterminer le niveau de volatilité des rendements des actifs.

La macroéconomie dynamique fait un usage intensif des chaînes de Markov. Un exemple consiste à utiliser des chaînes de Markov pour modéliser de manière exogène les prix des actions (actions) dans un cadre d' équilibre général .

Les agences de notation de crédit produisent des tableaux annuels des probabilités de transition pour les obligations de différentes notations de crédit.

Sciences sociales

Les chaînes de Markov sont généralement utilisées pour décrire des arguments dépendants du chemin , où les configurations structurelles actuelles conditionnent les résultats futurs. Un exemple est la reformulation de l'idée, à l' origine en raison de Karl Marx de Das Kapital , liant le développement économique à la montée du capitalisme . Dans les recherches actuelles, il est courant d'utiliser une chaîne de Markov pour modéliser comment, une fois qu'un pays atteint un niveau spécifique de développement économique, la configuration des facteurs structurels, tels que la taille de la classe moyenne , le ratio de résidence urbaine/rurale, le taux de de mobilisation politique , etc., générera une probabilité plus élevée de transition d' un régime autoritaire à un régime démocratique .

Jeux

Les chaînes de Markov peuvent être utilisées pour modéliser de nombreux jeux de hasard. Les jeux pour enfants Snakes and Ladders et " Hi Ho! Cherry-O ", par exemple, sont représentés exactement par des chaînes de Markov. À chaque tour, le joueur commence dans un état donné (sur une case donnée) et à partir de là, il a des chances fixes de se déplacer vers certains autres états (carrés).

Musique

Les chaînes de Markov sont utilisées dans la composition musicale algorithmique , en particulier dans des logiciels tels que Csound , Max et SuperCollider . Dans une chaîne du premier ordre, les états du système deviennent des valeurs de note ou de hauteur, et un vecteur de probabilité pour chaque note est construit, complétant une matrice de probabilité de transition (voir ci-dessous). Un algorithme est construit pour produire des valeurs de note de sortie basées sur les pondérations de la matrice de transition, qui peuvent être des valeurs de note MIDI , une fréquence ( Hz ) ou toute autre métrique souhaitable.

Matrice du 1er ordre
Noter UNE C E
UNE 0,1 0,6 0,3
C 0,25 0,05 0,7
E 0,7 0,3 0
Matrice d'ordre 2
Remarques UNE g
AA 0,18 0,6 0,22
UN D 0,5 0,5 0
AG 0,15 0,75 0,1
JJ 0 0 1
AD 0,25 0 0,75
DG 0,9 0,1 0
GG 0,4 0,4 0,2
Géorgie 0,5 0,25 0,25
DG 1 0 0

Une chaîne de Markov du second ordre peut être introduite en considérant l'état courant et aussi l'état précédent, comme indiqué dans le deuxième tableau. Les chaînes d'ordre n supérieur ont tendance à « regrouper » des notes particulières ensemble, tout en « se séparant » occasionnellement en d'autres motifs et séquences. Ces chaînes d'ordre supérieur ont tendance à générer des résultats avec un sens de la structure phrasale , plutôt que l'« errance sans but » produite par un système de premier ordre.

Les chaînes de Markov peuvent être utilisées structurellement, comme dans les Analogiques A et B de Xenakis. Les chaînes de Markov sont également utilisées dans les systèmes qui utilisent un modèle de Markov pour réagir de manière interactive à l'entrée musicale.

Habituellement, les systèmes musicaux doivent imposer des contraintes de contrôle spécifiques sur les séquences de longueur finie qu'ils génèrent, mais les contraintes de contrôle ne sont pas compatibles avec les modèles de Markov, car elles induisent des dépendances à longue portée qui violent l'hypothèse de Markov de mémoire limitée. Afin de surmonter cette limitation, une nouvelle approche a été proposée.

Base-ball

Les modèles de chaînes de Markov sont utilisés dans l'analyse avancée du baseball depuis 1960, bien que leur utilisation soit encore rare. Chaque demi-manche d'un match de baseball correspond à l'état de la chaîne de Markov lorsque le nombre de coureurs et de retraits est pris en compte. Lors de chaque présence au bâton, il y a 24 combinaisons possibles de nombre de retraits et de position des coureurs. Mark Pankin montre que les modèles de chaîne de Markov peuvent être utilisés pour évaluer les courses créées à la fois pour les joueurs individuels et pour une équipe. Il discute également de divers types de stratégies et de conditions de jeu : comment les modèles de chaîne de Markov ont été utilisés pour analyser les statistiques de situations de jeu telles que le bruant et le vol de base et les différences entre le jeu sur gazon et AstroTurf .

Générateurs de texte Markov

Les processus de Markov peuvent également être utilisés pour générer un texte d'apparence superficielle à partir d' un exemple de document. Les processus de Markov sont utilisés dans une variété de logiciels récréatifs de « générateur de parodie » (voir la presse dissociée , Jeff Harrison, Mark V. Shaney et Academias Neutronium ). Plusieurs bibliothèques de génération de texte open source utilisant des chaînes de Markov existent, dont The RiTa Toolkit .

Prévision probabiliste

Les chaînes de Markov ont été utilisées pour la prévision dans plusieurs domaines : par exemple, les tendances des prix, l'énergie éolienne et l'ensoleillement. Les modèles de prévision en chaîne de Markov utilisent une variété de paramètres, allant de la discrétisation des séries chronologiques aux modèles de Markov cachés combinés avec des ondelettes, et le modèle de distribution de mélange de chaînes de Markov (MCM).

Voir également

Remarques

Les références

  • AA Markov (1906) "Rasprostranenie zakona bol'shih ciseau na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete , 2-ya seriya, tom 15, pp. 135-156.
  • AA Markov (1971). « Extension des théorèmes limites de la théorie des probabilités à une somme de variables connectées dans une chaîne ». réimprimé à l'annexe B de : R. Howard. Systèmes probabilistes dynamiques, tome 1 : Chaînes de Markov . John Wiley et fils.
  • Texte classique en traduction : Markov, AA (2006). Traduit par Link, David. "Un exemple d'enquête statistique du texte Eugène Onéguine concernant la connexion d'échantillons dans les chaînes" . Sciences en contexte . 19 (4) : 591-600. doi : 10.1017/s0269889706001074 . S2CID  144854176 .
  • Leo Breiman (1992) [1968] Probabilité . Édition originale publiée par Addison-Wesley; réimprimé par la Society for Industrial and Applied Mathematics ISBN  0-89871-296-3 . (Voir chapitre 7)
  • JL Doob (1953) Processus stochastiques . New York : John Wiley and Sons ISBN  0-471-52369-0 .
  • SP Meyn et RL Tweedie (1993) Chaînes de Markov et stabilité stochastique . Londres : Springer-Verlag ISBN  0-387-19832-6 . en ligne : MSSC . Deuxième édition à paraître, Cambridge University Press, 2009.
  • SP Meyn. Techniques de contrôle pour les réseaux complexes . Cambridge University Press, 2007. ISBN  978-0-521-88441-9 . L'annexe contient Meyn & Tweedie abrégé. en ligne : [1]
  • Booth, Taylor L. (1967). Machines séquentielles et théorie des automates (1ère éd.). New York, NY : John Wiley and Sons, Inc. Numéro de catalogue de la carte de la Bibliothèque du Congrès 67-25924.] Un ouvrage complet et de grande envergure destiné aux spécialistes, écrit à la fois pour les informaticiens théoriques et les ingénieurs électriciens. Avec des explications détaillées sur les techniques de minimisation d'état, les FSM, les machines de Turing, les processus de Markov et l'indécidabilité. Excellent traitement des processus de Markov pp. 449ff. Discute des transformations Z, des transformations D dans leur contexte.
  • Kemeny, John G.; Hazleton Mirkil ; J. Laurie Snell; Gerald L. Thompson (1959). Structures mathématiques finies (1ère éd.). Englewood Cliffs, NJ : Prentice-Hall, Inc. Library of Congress Card Numéro de catalogue 59-12841.Texte classique. cf Chapitre 6 Chaînes de Markov finies pp. 384ff.
  • John G. Kemeny & J. Laurie Snell (1960) Chaînes de Markov finies , D. van Nostrand Company ISBN  0-442-04328-7
  • E. Nummelin. « Chaînes de Markov irréductibles générales et opérateurs non négatifs ». Cambridge University Press, 1984, 2004. ISBN  0-521-60494-X
  • Seneta, E. Matrices non négatives et chaînes de Markov . 2e rév. éd., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Publié à l'origine par Allen & Unwin Ltd., Londres, 1973) ISBN  978-0-387-29765-1
  • Kishor S. Trivedi , Probabilités et statistiques avec fiabilité, files d'attente et applications informatiques , John Wiley & Sons, Inc. New York, 2002. ISBN  0-471-33341-7 .
  • KS Trivedi et RASahner, SHARPE à l'âge de vingt-deux ans , vol. 36, non. 4, pp. 52-57, ACM SIGMETRICS Performance Evaluation Review, 2009.
  • RA Sahner, KS Trivedi et A. Puliafito, Analyse des performances et de la fiabilité des systèmes informatiques: une approche basée sur des exemples utilisant le progiciel SHARPE , Kluwer Academic Publishers, 1996. ISBN  0-7923-9650-2 .
  • G. Bolch, S. Greiner, H. de Meer et KS Trivedi, Queuing Networks and Markov Chains , John Wiley, 2e édition, 2006. ISBN  978-0-7923-9650-5 .

Liens externes