Chaînes de Markov
Introduction
§ 1. Chaîne de Markov
§ 2. Chaîne de Markov homogène. Probabilités de transition. Matrice de transition
§3. égalité de Markov
§4. Distribution stationnaire. Théorème sur probabilités extrêmes
§5. Preuve du théorème des probabilités limites dans une chaîne de Markov
§6. Applications des chaînes de Markov
Conclusion
Liste de la littérature utilisée
Introduction
Notre thème travail de cours Chaînes de Markov. Les chaînes de Markov portent le nom du remarquable mathématicien russe Andrei Andreevich Markov, qui a beaucoup travaillé sur processus aléatoires et a grandement contribué au développement de ce domaine. DANS Dernièrement vous pouvez entendre parler de l'utilisation des chaînes de Markov dans la plupart des cas différentes régions: technologies Web modernes, lors de l'analyse de textes littéraires ou même lors de l'élaboration de tactiques pour une équipe de football. Ceux qui ne savent pas ce que sont les chaînes de Markov peuvent avoir le sentiment qu’il s’agit de quelque chose de très complexe et presque incompréhensible.
Non, c'est tout le contraire. La chaîne de Markov est l'une des plus cas simples séquences événements aléatoires. Mais malgré sa simplicité, il peut souvent être utile même pour décrire des phénomènes plutôt complexes. Une chaîne de Markov est une séquence d'événements aléatoires dans laquelle la probabilité de chaque événement dépend uniquement du précédent, mais ne dépend pas des événements antérieurs.
Avant d’approfondir, nous devons considérer quelques questions auxiliaires qui sont généralement connues, mais qui sont absolument nécessaires pour une exposition plus approfondie.
Le but de mon cours est d'étudier plus en détail les applications des chaînes de Markov, l'énoncé du problème et les problèmes de Markov.
§1. Chaîne de Markov
Imaginons qu'une séquence de tests soit en cours.
Définition. Une chaîne de Markov est une séquence d’essais dans chacun desquels apparaît un et un seul des éléments suivants. événements incompatibles groupe complet, et probabilite conditionnelle qu'un événement se produira lors du ème test 
, à condition que l'événement se soit produit lors du ème procès 
, ne dépend pas des résultats des tests précédents.
Par exemple, si la séquence d'essais forme une chaîne de Markov et que le groupe complet se compose de quatre événements incompatibles, et que l'on sait que l'événement s'est produit lors du sixième essai, alors la probabilité conditionnelle que l'événement se produise lors du septième essai ne dépend pas sur quels événements sont apparus dans le premier, ..., cinquième test.
remarquerez que tests indépendants sont un cas particulier de chaîne de Markov. En effet, si les tests sont indépendants, alors l'apparition de certains certain événement dans aucun test ne dépend des résultats des tests effectués précédemment. Il s’ensuit que le concept de chaîne de Markov est une généralisation du concept d’essais indépendants.
Souvent, lorsqu'ils présentent la théorie des chaînes de Markov, ils adhèrent à une terminologie différente et parlent de certains système physique, qui à chaque instant est dans l'un des états : , et ne change d'état qu'à des moments distincts dans le temps, c'est-à-dire que le système passe d'un état à un autre (par exemple, de à ). Pour les chaînes de Markov, la probabilité d’aller dans n’importe quel état est à l'heure actuelle dépend uniquement de l'état dans lequel se trouvait le système à ce moment-là et ne change pas parce que ses états à des moments antérieurs sont connus. De plus, en particulier, après le test, le système peut rester dans le même état (« passer » d'un état à l'autre).
Pour illustrer, prenons un exemple.
Exemple 1. Imaginons qu'une particule située sur une droite se déplace le long de cette droite sous l'influence de chocs aléatoires se produisant à certains moments . Une particule peut être localisée en des points dont les coordonnées sont entières : 
; Les murs réfléchissants sont situés aux points. Chaque poussée déplace la particule vers la droite avec probabilité et vers la gauche avec probabilité, sauf si la particule se trouve près d'un mur. Si la particule est près du mur, toute poussée la déplace d'une unité à l'intérieur de l'espace entre les murs. Nous voyons ici que cet exemple de particule marchant est une chaîne de Markov typique.
Ainsi, les événements sont appelés états du système et les tests sont appelés changements dans ses états.
Définissons maintenant une chaîne de Markov en utilisant une nouvelle terminologie.
Une chaîne de Markov à temps discret est un circuit dont les états changent à certains instants fixes.
Chaîne de Markov avec temps continu appelé un circuit dont les états changent à tout moment aléatoire possible.
§2. Chaîne de Markov homogène. Probabilités de transition. Matrice de transition
Définition. Une chaîne de Markov est dite homogène si la probabilité conditionnelle (transition d'un état à l'autre) ne dépend pas du numéro d'essai. Par conséquent, au lieu d’écrire simplement .
Exemple 1. Promenade aléatoire. Soit une particule matérielle sur une ligne droite en un point avec une coordonnée entière. À certains moments, la particule subit des chocs. Sous l’influence d’une poussée, la particule se déplace avec probabilité d’une unité vers la droite et avec probabilité d’une unité vers la gauche. Il est clair que la position (coordonnée) d'une particule après un choc dépend de l'endroit où se trouvait la particule après le choc immédiatement précédent, et ne dépend pas de la façon dont elle s'est déplacée sous l'influence d'autres chocs précédents.
Ainsi, une marche aléatoire est un exemple de chaîne de Markov homogène à temps discret.
La probabilité de transition est la probabilité conditionnelle qu'à partir de l'état (dans lequel le système s'est trouvé à la suite d'un test, quel que soit le nombre) à la suite du prochain test, le système passe à l'état.
Ainsi, dans la notation, le premier index indique le numéro de l'état précédent, et le second indique le numéro de l'état suivant. Par exemple, c'est la probabilité de transition du deuxième état au troisième.
Soit le nombre d'états fini et égal à .
La matrice de transition d'un système est une matrice qui contient toutes les probabilités de transition de ce système :
Puisque chaque ligne de la matrice contient les probabilités d'événements (passage du même état à n'importe quel état possible), qui forment groupe complet, alors la somme des probabilités de ces événements est égale à un. Autrement dit, la somme des probabilités de transition de chaque ligne de la matrice de transition est égale à un :
Donnons un exemple de matrice de transition d'un système qui peut être à trois états ; le passage d'un état à l'autre s'effectue selon le schéma d'une chaîne de Markov homogène ; les probabilités de transition sont données par la matrice :
Ici, nous voyons que si le système était dans un état, alors après avoir changé d'état en une seule étape, il restera dans le même état avec une probabilité de 0,5, restera dans le même état avec une probabilité de 0,5 et entrera dans un état avec une probabilité de 0,2, puis après la transition, il peut se retrouver dans des états ; il ne peut pas passer d’un état à un autre. Dernière ligne La matrice nous montre que d'un état à l'autre états possibles avec la même probabilité de 0,1.
Sur la base de la matrice de transition du système, vous pouvez construire ce qu'on appelle un graphe d'état du système ; il est également appelé graphe d'état étiqueté. Ceci est pratique pour une représentation visuelle du circuit. Regardons l'ordre de construction des graphiques à l'aide d'un exemple.
Exemple 2.À l'aide d'une matrice de transition donnée, construisez un graphe d'état.
Parce que matrice quatrième commande, alors, en conséquence, le système a 4 états possibles.
Le graphique n’indique pas les probabilités de transition du système d’un état au même. En révisant systèmes spécifiques Il est pratique de construire d'abord un graphe d'état, puis de déterminer la probabilité de transitions du système d'un état au même (en fonction de l'exigence que la somme des éléments des lignes matricielles soit égale à un), puis de construire une transition matrice du système.
§3. égalité de Markov
Définition. Désignons par la probabilité qu'à la suite d'étapes (tests), le système passe d'un état à l'autre . Par exemple, est la probabilité de transition en 10 étapes du deuxième état au cinquième.
Nous soulignons qu'à on obtient les probabilités de transition
Fixons-nous une tâche : connaître les probabilités de transition, trouver les probabilités que le système passe d'un état à l'autre par étapes.
Pour cela, nous introduisons en considération un état intermédiaire (entre et ). En d'autres termes, nous supposerons que de l'état initial par étapes, le système passera à un état intermédiaire avec probabilité , après quoi, dans les étapes restantes de l'état intermédiaire, il passera à l'état final avec probabilité .
D'après la formule pleine probabilité, on a
. (1)
Cette formule s'appelle l'égalité de Markov.
Explication. Introduisons la notation suivante :
– l’événement qui nous intéresse (par étapes le système va passer de l’état initial à l’état final), donc ; 
− hypothèses (par étapes, le système passera de l'état initial à l'état intermédiaire), donc, − probabilité conditionnelle d'occurrence, à condition que l'hypothèse ait eu lieu (par étapes, le système passera de l'état intermédiaire à l'état final), donc, 
D'après la formule de probabilité totale,
()
Ou dans la notation que nous avons adoptée
ce qui coïncide avec la formule de Markov (1).
Connaissant toutes les probabilités de transition, c'est-à-dire connaissant la matrice de transition d'un état à l'autre en une étape, vous pouvez trouver les probabilités de transition d'un état à l'autre en deux étapes, et donc la matrice de transition elle-même ; en utilisant une matrice connue, vous pouvez trouver la matrice de transition d'un état à l'autre en trois étapes, etc.
En effet, en introduisant l'égalité de Markov
,
chaîne de marques probabilité aléatoire
,
(2)
Ainsi, en utilisant la formule (2), vous pouvez trouver toutes les probabilités et donc la matrice elle-même. Puisque l'utilisation directe de la formule (2) s'avère fastidieuse et que le calcul matriciel mène au but plus rapidement, j'écrirai les relations issues de (2) sous forme matricielle :
En mettant (1), on obtient de la même manière
En général
Théorème 1. Pour tout s, t
(3)
Preuve. Calculons la probabilité 
en utilisant la formule de probabilité totale (), en mettant
Des égalités
Donc à partir des égalités (4) et
on obtient l'énoncé du théorème.
Définissons la matrice B notation matricielle(3) a la forme
Depuis, où est la matrice de probabilité de transition. De (5) il résulte
(6)
Les résultats obtenus en théorie des matrices permettent, à l'aide de la formule (6), de calculer et d'étudier leur comportement lorsque
Exemple 1. Matrice de transition spécifiée 
Trouver la matrice de transition 
Solution. Utilisons la formule
En multipliant les matrices, on obtient finalement :
.
§4. Distribution stationnaire. Théorème de probabilité limite
La distribution de probabilité à un moment arbitraire peut être trouvée à l'aide de la formule de probabilité totale
(7)
Il se peut que cela ne dépende pas du temps. Appelons distribution stationnaire vecteur 
, satisfaisant aux conditions
où sont les probabilités de transition.
Si dans une chaîne de Markov 
alors pour tout
Cette affirmation découle de l’induction de (7) et (8).
Présentons la formulation du théorème sur les probabilités limites pour un classe importante Chaînes de Markov.
Théorème 1. Si pour certains >0 tous les éléments de la matrice sont positifs, alors pour tout , pour
, (9)
Où 
distribution stationnaire avec une certaine constante satisfaisant l'inégalité 0<
h
<1.
Puisque , alors selon les conditions du théorème, depuis n'importe quel état, vous pouvez accéder à n'importe quel état à temps avec une probabilité positive. Les conditions du théorème excluent les chaînes qui sont en quelque sorte périodiques.
Si les conditions du théorème 1 sont remplies, alors la probabilité que le système soit dans un certain état dans la limite ne dépend pas de la distribution initiale. En effet, de (9) et (7) il résulte que pour toute distribution initiale ,
Considérons plusieurs exemples de chaînes de Markov pour lesquelles les conditions du théorème 1 ne sont pas remplies. Il est facile de vérifier que de tels exemples sont des exemples. Dans l'exemple, les probabilités de transition ont des limites, mais ces limites dépendent de l'état initial. En particulier, lorsque
Dans d’autres exemples, les plages de probabilité n’existent évidemment pas.
Trouvons la distribution stationnaire dans l'exemple 1. Nous devons trouver le vecteur 
conditions satisfaisantes (8) :
,
;
Par conséquent, une distribution stationnaire existe, mais tous les vecteurs de coordonnées ne sont pas positifs.
Pour le schéma polynomial, des variables aléatoires ont été introduites égales au nombre de résultats d'un type donné. Introduisons des quantités similaires pour les chaînes de Markov. Soit le nombre de fois où le système entre dans cet état dans le temps. Ensuite, la fréquence à laquelle le système frappe l'État. En utilisant les formules (9), nous pouvons prouver que lorsque s'approche de . Pour ce faire, vous devez obtenir des formules asymptotiques pour et utiliser l’inégalité de Chebyshev. Voici la dérivation de la formule pour . Représentons-le sous la forme
(10)
où, si et autrement. Parce que
,
alors, en utilisant la propriété de l'espérance mathématique et la formule (9), on obtient
.
En vertu du théorème 1, le triple terme du côté droit de cette égalité est une somme partielle d'une série convergente. En mettant 
, on a
Parce que le
De la formule (11), en particulier, il résulte que
à
Vous pouvez également obtenir une formule utilisée pour calculer la variance.
§5. Preuve du théorème des probabilités limites dans une chaîne de Markov
Démontrons d’abord deux lemmes. Mettons
Lemme 1. Il y a des limites pour tout
Preuve. En utilisant l'équation (3) avec nous obtenons
Ainsi, les séquences sont à la fois monotones et limitées. Cela implique l’énoncé du lemme 1.
Lemme 2.
Si les conditions du théorème 2 sont remplies, alors il existe des constantes , 
tel que
Pour toute
où , signifie la somme de tout ce qui est positif et la somme du reste. D'ici
. (12)
Puisque dans les conditions du théorème 1 les probabilités de transition pour tous , alors pour tout
Et en raison du nombre fini d'états
Estimons maintenant la différence 
. En utilisant l'équation (3) avec , , on obtient
De là, en utilisant (8)-(10), on trouve
=
.
En combinant cette relation avec l'inégalité (14), nous obtenons l'énoncé du lemme.
Allez à la preuve du théorème. Puisque les séquences sont monotones, alors
0<
. (15)
De ceci et du lemme 1, nous trouvons
Par conséquent, lorsque vous obtenez et
La positivité découle de l’inégalité (15). En passant à la limite en et dans l'équation (3), nous obtenons qui satisfait l'équation (12). Le théorème a été prouvé.
§6. Applications des chaînes de Markov
Les chaînes de Markov constituent une bonne introduction à la théorie des processus aléatoires, c'est-à-dire théorie des séquences simples d'une famille de variables aléatoires, dépendant généralement d'un paramètre qui, dans la plupart des applications, joue le rôle du temps. Son objectif principal est de décrire de manière complète le comportement à la fois local et à long terme d'un processus. Voici quelques-unes des questions les plus étudiées à cet égard.
Mouvement brownien et ses généralisations - processus de diffusion et processus avec incréments indépendants . La théorie des processus aléatoires a contribué à approfondir le lien entre la théorie des probabilités, la théorie des opérateurs et la théorie des équations différentielles, ce qui, entre autres, était important pour la physique et d'autres applications. Les applications incluent des processus intéressant les mathématiques actuarielles (assurance), la théorie des files d'attente, la génétique, le contrôle de la circulation, la théorie des circuits électriques et la théorie des stocks.
Martingales . Ces processus préservent suffisamment les propriétés des chaînes de Markov pour que d'importants théorèmes ergodiques restent valables pour elles. Les martingales diffèrent des chaînes de Markov en ce sens que lorsque l'état actuel est connu, seule l'espérance mathématique du futur, mais pas nécessairement la distribution de probabilité elle-même, ne dépend pas du passé. Outre le fait que la théorie des martingales constitue un outil de recherche important, elle a enrichi la théorie des processus aléatoires issus de la statistique, la théorie de la fission nucléaire, la génétique et la théorie de l'information avec de nouveaux théorèmes limites.
Processus stationnaires . Le plus ancien théorème ergodique connu, comme indiqué ci-dessus, peut être interprété comme un résultat décrivant le comportement limite d'un processus aléatoire stationnaire. Un tel processus a la propriété que toutes les lois probabilistes auxquelles il satisfait restent invariantes par rapport aux décalages temporels. Le théorème ergodique, formulé pour la première fois par les physiciens comme une hypothèse, peut être représenté comme l'affirmation selon laquelle, sous certaines conditions, la moyenne d'ensemble coïncide avec la moyenne temporelle. Cela signifie que les mêmes informations peuvent être obtenues à partir de l’observation à long terme d’un système et de l’observation simultanée (et instantanée) de nombreuses copies indépendantes du même système. La loi des grands nombres n'est rien d'autre qu'un cas particulier du théorème ergodique de Birkhoff. L'interpolation et la prédiction du comportement des processus gaussiens stationnaires, entendus au sens large, constituent une généralisation importante de la théorie classique des moindres carrés. La théorie des processus stationnaires est un outil de recherche nécessaire dans de nombreux domaines, par exemple dans la théorie de la communication, qui traite de l'étude et de la création de systèmes transmettant des messages en présence de bruit ou d'interférences aléatoires.
Les processus de Markov (processus sans séquelles) jouent un rôle énorme dans la modélisation des systèmes de file d'attente (QS), ainsi que dans la modélisation et le choix d'une stratégie de gestion des processus socio-économiques se produisant dans la société.
La chaîne de Markov peut également être utilisée pour générer des textes. Plusieurs textes sont fournis en entrée, puis une chaîne de Markov est construite avec les probabilités d'un mot après l'autre, et le texte résultant est créé sur la base de cette chaîne. Le jouet s'avère très amusant !
Conclusion
Ainsi, dans notre cours, nous parlions du circuit en chaîne de Markov. Nous avons appris dans quels domaines et comment il est utilisé, des tests indépendants ont prouvé le théorème des probabilités limites dans une chaîne de Markov, ont donné des exemples pour une chaîne de Markov typique et homogène, ainsi que pour trouver la matrice de transition.
Nous avons vu que le modèle de chaîne de Markov est une généralisation directe du modèle de test indépendant.
Liste de la littérature utilisée
1. Chistiakov V.P. Cours de théorie des probabilités. 6e éd., rév. − Saint-Pétersbourg : Maison d'édition Lan, 2003. − 272 p. − (Manuel pour les universités. Littérature spéciale).
2. Gnedenko B.V. Cours de théorie des probabilités.
3. Gmurman V.E. Théorie des probabilités et statistiques mathématiques.
4. Ventzel E.S. Théorie des probabilités et ses applications techniques.
5. Kolmogorov A.N., Zhurbenko I.G., Prokhorov A.V. Introduction à la théorie des probabilités. − Moscou-Ijevsk : Institut de recherche informatique, 2003, 188 p.
6. Katz M. Probabilités et questions connexes en physique.
Les méthodes de descriptions mathématiques des processus aléatoires de Markov dans un système à états discrets (DS) dépendent des moments dans le temps (précédemment connus ou aléatoires) où les transitions du système d'un état à l'autre peuvent se produire.
Si la transition d'un système d'un état à l'autre est possible à des moments prédéterminés, nous avons affaire à processus de Markov aléatoire à temps discret. Si la transition est possible à tout moment aléatoire, alors nous avons affaire à processus de Markov aléatoire à temps continu.
Qu'il y ait un système physique S, qui peut être dans nÉtats S 1 , S 2 , …, S n. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments t 1 , t 2 , …, merci, appelons ces moments en pas de temps. Nous considérerons la coentreprise dans le système S en fonction de l'argument entier 1, 2, …, k, où l'argument est le numéro de l'étape.
Exemple: S 1 → S 2 → S 3 → S 2 .
Acceptons de désigner S je (k) – un événement consistant dans le fait qu’après kétapes pendant lesquelles le système est dans l'état S je.
Pour toute kévénements S 1 ( k) , S 2 ( k) ,…,S n (k) formulaire groupe complet d'événements et sont incompatible.
Un processus dans un système peut être représenté comme une chaîne d’événements.
Exemple: S 1 (0) , S 2 (1) , S 3 (2) , S 5 (3) ,….
Cette séquence est appelée Chaîne de Markov
, si pour chaque étape la probabilité de transition depuis n'importe quel état S je dans n'importe quelle condition S j ne dépend pas du moment et de la manière dont le système a atteint l'état S je.
Laissez à tout moment après n'importe quel k-ème système d'étape S peut être dans l'un des États S 1 , S 2 , …, S n, c'est-à-dire qu'un événement parmi un groupe complet d'événements peut se produire : S 1 (k) , S 2 ( k) , …, S n (k) . Notons les probabilités de ces événements :
P. 1 (1) = P.(S 1 (1)); P. 2 (1) = P.(S 2 (1)); …; Pn(1) = P.(S n (k));
P. 1 (2) = P.(S 1 (2)); P. 2 (2) = P.(S 2 (2)); ... ; Pn(2) = P.(S n (2));
P. 1 (k) = P.(S 1 (k)); P. 2 (k) = P.(S 2 (k)); …; Pn(k) = P.(S n (k)).
Il est facile de voir que pour chaque numéro d’étape la condition est satisfaite
P. 1 (k) + P. 2 (k) +…+ Pn(k) = 1.
Appelons ces probabilités probabilités d'état Par conséquent, la tâche ressemblera à ceci : trouver les probabilités des états du système pour tout k.
Exemple. Qu'il y ait un système qui puisse être présent dans l'un des six États. alors les processus qui s'y déroulent peuvent être représentés soit sous la forme d'un graphique des changements dans l'état du système (Fig. 7.9, UN), ou sous la forme d'un graphe d'état du système (Fig. 7.9, b).
UN) 
Riz. 7.9
De plus, les processus du système peuvent être représentés comme une séquence d'états : S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Probabilité d'état à ( k+ 1)ème étape dépend uniquement de l'état à k- m pas.
Pour toute étape k il existe certaines probabilités que le système passe d'un état à un autre, appelons ces probabilités probabilités de transition d'une chaîne de Markov.
Certaines de ces probabilités seront nulles si le passage d’un état à un autre n’est pas possible en une seule étape.
La chaîne de Markov s'appelle homogène, si les états de transition ne dépendent pas du numéro d'étape, sinon on l'appelle hétérogène.
Qu'il y ait une chaîne de Markov homogène et que le système S Il a nétats possibles : S 1 , …, S n. Connaître la probabilité de transition vers un autre état en une seule étape pour chaque état, c'est-à-dire P ij(depuis S je V S j en une seule étape), nous pouvons alors écrire les probabilités de transition sous forme de matrice.
. (7.1)
Le long de la diagonale de cette matrice se trouvent les probabilités que le système passe de l'état S je dans le même état S je.
Utilisation d'événements saisis précédemment 
, nous pouvons écrire les probabilités de transition sous forme de probabilités conditionnelles : 
.
Évidemment, la somme des termes 
dans chaque ligne de la matrice (1) est égal à un, puisque les événements former un groupe complet d’événements incompatibles.
Lors de l'examen des chaînes de Markov, ainsi que lors de l'analyse d'un processus aléatoire de Markov, divers graphes d'état sont utilisés (Fig. 7.10). 
Riz. 7.10
Ce système peut être dans l'un des six états, tandis que P ij est la probabilité que le système passe de l'état S je dans un état S j. Pour ce système, nous écrivons les équations selon lesquelles le système était dans un certain état et hors de celui-ci pendant le temps t n'est pas sorti : 
Dans le cas général, la chaîne de Markov est inhomogène, c'est-à-dire la probabilité P ij change d’étape en étape. Supposons qu'une matrice de probabilités de transition soit donnée à chaque étape, alors la probabilité que le système S sur k-ème étape sera en l'état S je, peut être trouvé en utilisant la formule 
Connaissant la matrice des probabilités de transition et l'état initial du système, on peut trouver les probabilités des états 
après tout k-ème étape. Supposons qu'au moment initial le système soit dans l'état Petit. Alors pour t = 0
.
Trouvons les probabilités après la première étape. De l'état Petit le système ira dans les états S 1 , S 2 etc. avec probabilités PM 1 , PM 2 , …, Pmm, …, P minute. Ensuite, après la première étape, les probabilités seront égales
. (7.2)
Trouvons les probabilités de l'état après la deuxième étape : . Nous calculerons ces probabilités à l'aide de la formule de probabilité totale avec des hypothèses : 
.
Les hypothèses seront les énoncés suivants :
- après la première étape, le système était dans l'état S 1 -H 1 ;
- après la deuxième étape, le système était dans l'état S 2 -H 2 ;
- après n A la ème étape, le système était dans l'état S n -H n.
Probabilité de n'importe quel état après la deuxième étape :
(7.3)
La formule (7.3) résume toutes les probabilités de transition P ij, mais seules les valeurs non nulles sont prises en compte. Probabilité de toute condition après k-ème étape :
(7.4)
Ainsi, la probabilité d'un état après k La ème étape est déterminée par la formule récurrente (7.4) à travers les probabilités ( k- 1)ème étape.
Tâche 6. Une matrice de probabilités de transition pour une chaîne de Markov en une étape est donnée. Trouver la matrice de transition d'un circuit donné en trois étapes 
.
Solution. La matrice de transition d'un système est une matrice qui contient toutes les probabilités de transition de ce système : 
Chaque ligne de la matrice contient les probabilités d'événements (passage de l'état je dans un état j), qui forment un groupe complet, donc la somme des probabilités de ces événements est égale à un : 
Notons p ij (n) la probabilité qu'à la suite de n étapes (tests) le système passe de l'état i à l'état j. Par exemple, p 25 (10) est la probabilité de transition du deuxième état au cinquième en dix étapes. Notons que pour n=1 on obtient des probabilités de transition p ij (1)=p ij .
On nous confie une tâche : connaissant les probabilités de transition p ij, trouver les probabilités p ij (n) de transition du système depuis l'état je dans un état j derrière n pas. Pour ce faire, nous introduisons un intermédiaire (entre je Et j) État r. En d’autres termes, nous supposerons qu’à partir de l’état initial je derrière métapes par lesquelles le système passera à un état intermédiaire r avec probabilité p ij (n-m), après quoi, dans les n-m étapes restantes, de l'état intermédiaire r, il ira à l'état final j avec probabilité p ij (n-m) . En utilisant la formule de probabilité totale, nous obtenons : 
.
Cette formule s'appelle l'égalité de Markov. A l'aide de cette formule, vous pouvez retrouver toutes les probabilités p ij (n), et, par conséquent, la matrice P n elle-même. Puisque le calcul matriciel mène plus rapidement à l'objectif, nous écrivons la relation matricielle résultant de la formule résultante sous forme générale.
Calculons la matrice de transition de la chaîne de Markov en trois étapes en utilisant la formule résultante : 
Répondre:
.
Tâche n°1. La matrice de probabilité de transition en chaîne de Markov a la forme : 
.
La répartition sur les états au temps t=0 est déterminée par le vecteur :
π 0 =(0,5 ; 0,2 ; 0,3)
Trouver: a) répartition par état aux instants t=1,2,3,4.
c) distribution stationnaire.
Définition. Une chaîne de Markov est dite homogène si la probabilité conditionnelle (transition d'un état à l'autre) ne dépend pas du numéro d'essai. C'est pourquoi ils écrivent simplement à la place.
Exemple 1. Promenade aléatoire. Soit une particule matérielle sur une ligne droite en un point avec une coordonnée entière. À certains moments, la particule subit des chocs. Sous l’influence d’une poussée, la particule se déplace avec probabilité d’une unité vers la droite et avec probabilité d’une unité vers la gauche. Il est clair que la position (coordonnée) d'une particule après un choc dépend de l'endroit où se trouvait la particule après le choc immédiatement précédent, et ne dépend pas de la façon dont elle s'est déplacée sous l'influence d'autres chocs précédents.
Alors une promenade aléatoire ? un exemple de chaîne de Markov homogène à temps discret.
La probabilité de transition est la probabilité conditionnelle qu'à partir de l'état (dans lequel le système s'est trouvé à la suite d'un test, quel que soit le nombre) à la suite du prochain test, le système passe à l'état.
Ainsi, dans la désignation, le premier index indique le numéro du précédent, et le second ? numéro d'état ultérieur. Par exemple, - la probabilité de passage du deuxième état au troisième.
Que le nombre d'états soit fini et égal.
La matrice de transition d'un système est une matrice qui contient toutes les probabilités de transition de ce système :
Puisque chaque ligne de la matrice contient les probabilités d'événements (passage du même état à n'importe quel état possible) qui forment un groupe complet, la somme des probabilités de ces événements est égale à un. Autrement dit, la somme des probabilités de transition de chaque ligne de la matrice de transition est égale à un :
Donnons un exemple de matrice de transition d'un système qui peut être à trois états ; le passage d'un état à l'autre s'effectue selon le schéma d'une chaîne de Markov homogène ; les probabilités de transition sont données par la matrice :
Ici, nous voyons que si le système était dans un état, alors après avoir changé d'état en une seule étape, il restera dans le même état avec une probabilité de 0,5, restera dans le même état avec une probabilité de 0,5, entrera dans un état avec une probabilité de 0,2, alors après la transition, elle peut se retrouver dans des états ; il ne peut pas passer d’un état à un autre. La dernière ligne de la matrice nous montre que d'un état à passer à l'un des états possibles avec la même probabilité de 0,1.
Sur la base de la matrice de transition du système, vous pouvez construire ce qu'on appelle un graphe d'état du système ; il est également appelé graphe d'état étiqueté. Ceci est pratique pour une représentation visuelle du circuit. Regardons l'ordre de construction des graphiques à l'aide d'un exemple.
Exemple 2.À l'aide d'une matrice de transition donnée, construisez un graphe d'état.
Parce que matrice du quatrième ordre, alors, en conséquence, le système a 4 états possibles.
Le graphique n’indique pas les probabilités de transition du système d’un état au même. Lorsque l'on considère des systèmes spécifiques, il est pratique de construire d'abord un graphe d'état, puis de déterminer la probabilité de transition du système d'un état au même (en fonction de l'exigence que la somme des éléments des lignes matricielles soit égale à un ), puis construisez une matrice de transition du système.
Aujourd'hui, j'aimerais vous parler de l'écriture d'un cours pour faciliter le travail avec les chaînes de Markov.
S'il vous plaît sous chat.
Notions de base:
Représentation de graphiques sous forme de matrice d'adjacence, connaissance des notions de base sur les graphiques. Connaissance du C++ pour la partie pratique.
Théorie
Une chaîne de Markov est une séquence d'événements aléatoires avec un nombre fini ou dénombrable de résultats, caractérisée par la propriété que, en gros, avec un présent fixe, le futur est indépendant du passé. Nommé en l'honneur de A. A. Markov (senior).
En termes simples, une chaîne de Markov est un graphe pondéré. Il y a des événements à ses sommets, et le poids de l'arête reliant les sommets A et B est la probabilité que l'événement A soit suivi par l'événement B.
De nombreux articles ont été écrits sur l'utilisation des chaînes de Markov, mais nous continuerons à développer la classe.
Laissez-moi vous donner un exemple de chaîne de Markov :
À l'avenir, nous considérerons ce schéma comme exemple.
Évidemment, s’il n’y a qu’une seule arête sortant du sommet A, alors son poids sera égal à 1.
Désignations
Aux sommets nous avons des événements (de A, B, C, D, E...). Sur les bords, la probabilité qu'après le i-ème événement il y ait un événement j > i. Par convention et par commodité, j'ai numéroté les sommets (n° 1, n° 2, etc.).Une matrice est la matrice d'adjacence d'un graphe pondéré orienté, que nous utilisons pour représenter une chaîne de Markov. (nous en reparlerons plus tard). Dans ce cas particulier, cette matrice est aussi appelée matrice de probabilité de transition ou simplement matrice de transition.
Représentation matricielle d'une chaîne de Markov
Nous représenterons les chaînes de Markov à l'aide d'une matrice, précisément la matrice d'adjacence avec laquelle nous représentons les graphiques.Laisse-moi te rappeler:
La matrice d'adjacence d'un graphe G avec un nombre fini de sommets n (numérotés de 1 à n) est une matrice carrée A de taille n, dans laquelle la valeur de l'élément aij est égale au nombre d'arêtes du i-ème sommet du graphique au j-ième sommet.
Apprenez-en davantage sur les matrices d’adjacence dans le cours de mathématiques discrètes.
Dans notre cas, la matrice aura une taille de 10x10, écrivons-la :
0 50 0 0 0 0 50 0 0 0
0 0 80 20 0 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 0 100 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 70 30 0
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 100 0 0 0 0
Idée
Examinez de plus près notre matrice. Dans chaque ligne, nous avons des valeurs non nulles dans les colonnes dont le numéro coïncide avec l'événement ultérieur, et la valeur non nulle elle-même est la probabilité que cet événement se produise.Ainsi, nous avons la probabilité qu'un événement se produise avec un nombre égal au nombre colonne après un événement avec un nombre égal à lignes.
Ceux qui connaissent la théorie des probabilités pourraient deviner que chaque ligne est une fonction de distribution de probabilité.
Algorithme de parcours de chaîne de Markov
1) initialiser la position initiale k avec le sommet zéro.2) Si le sommet n'est pas final, alors nous générons un nombre m de 0...n-1 basé sur la distribution de probabilité dans la ligne k de la matrice, où n est le nombre de sommets et m est le nombre de sommets. prochain événement (!). Sinon on part
3) Le numéro de la position actuelle k est égal au numéro du sommet généré
4) Vers l'étape 2
Remarque : un sommet est fini si la distribution de probabilité est nulle (voir 6ème ligne de la matrice).
Un algorithme assez élégant, non ?
Mise en œuvre
Dans cet article, je souhaite inclure séparément le code pour implémenter le contournement décrit. Initialiser et peupler la chaîne de Markov n'est pas particulièrement intéressant (voir la fin pour le code complet).Implémentation de l'algorithme de traversée
modèle
::elems.at(suivant)); // renvoie la valeur au sommet ) return NULL; ) Cet algorithme semble particulièrement simple en raison des fonctionnalités du conteneur distribution_discrète
0 50 0 0 0 0 50 0 0 0
. Il est assez difficile de décrire avec des mots le fonctionnement de ce conteneur, prenons donc comme exemple la 0ème ligne de notre matrice :
En raison du fonctionnement du générateur, il renverra soit 1, soit 6 avec des probabilités de 0,5 pour chacun. Autrement dit, il renvoie le numéro de colonne (qui équivaut au numéro du sommet de la chaîne) où le mouvement doit continuer.
Un exemple de programme qui utilise la classe :
Implémentation d'un programme qui effectue le parcours de la chaîne de Markov à partir de l'exemple
outs.open("out.txt");
ifstream ins ; 
ins.open("matrice.txt");
numéro int ; double Prob = 0 ;
(ins >> num).get(); // nombre de sommets string str;
pour (int je = 0; je
> Prob).get();
if (!chain.PushAdjacency(i, j, Prob)) // entrez la matrice ( cerr
Un exemple du résultat généré par le programme : Tous les états possibles du système dans une chaîne de Markov homogène, et est la matrice stochastique qui définit cette chaîne, composée de probabilités de transition
(voir page 381).
Nous appellerons une matrice stochastique et la chaîne de Markov homogène correspondante régulière si la matrice n'a pas de nombres caractéristiques différents de l'unité et égaux en module à un, et régulière si en plus l'unité est une racine simple de l'équation caractéristique de la matrice.
Une matrice régulière se caractérise par le fait que dans sa forme normale (69) (p. 373) les matrices sont primitives. Pour une matrice régulière en plus .
De plus, une chaîne de Markov homogène est dite indécomposable, décomposable, acyclique, cyclique si pour cette chaîne la matrice stochastique est respectivement indécomposable, décomposable, primitive, imprimitive.
Puisqu'une matrice stochastique primitive est un type spécial de matrice régulière, une chaîne de Markov acyclique est un type spécial de chaîne régulière.
Nous montrerons que les probabilités de transition limites n’existent que pour les chaînes de Markov homogènes régulières.
En effet, soit le polynôme minimal d'une matrice régulière . Alors
D’après le théorème 10, on peut supposer que
Basé sur la formule (24) Ch. V (page 113)
(96)
Où 
est la matrice adjointe réduite et
Si est une matrice régulière, alors
et donc, du côté droit de la formule (96), tous les termes sauf le premier tendent vers zéro. Par conséquent, pour une matrice régulière, il existe une matrice composée des probabilités de transition limites, et
La situation inverse est évidente. S'il y a un problème
alors la matrice ne peut pas avoir de nombre caractéristique pour lequel , a , puisque alors la limite n'existerait pas [La même limite doit exister en raison de l'existence de la limite (97").]
Nous avons prouvé que pour une chaîne de Markov homogène régulière (et seulement régulière) il existe une matrice. Cette matrice est déterminée par la formule (97).
Montrons comment la matrice peut être exprimée à travers le polynôme caractéristique
et la matrice adjointe 
.
De l'identité
En vertu de (95), (95") et (98) il s'ensuit :
La formule (97) peut donc être remplacée par la formule
(97)
Pour une chaîne de Markov régulière, puisqu'il s'agit d'un type particulier de chaîne régulière, la matrice existe et est déterminée par l'une des formules (97), (97"). Dans ce cas, la formule (97") a également la forme
2. Considérons une chaîne régulière de type général (irrégulier). On écrit la matrice correspondante sous forme normale
(100)
où sont les matrices stochastiques primitives, et les matrices indécomposables ont des nombres caractéristiques maximaux. Croire
, 
écrivons-le sous la forme
(101)
Mais 
, puisque tous les nombres caractéristiques de la matrice sont inférieurs à un en valeur absolue. C'est pourquoi
(102)
Puisque sont des matrices stochastiques primitives, les matrices selon les formules (99) et (35) (p. 362) sont positives
et dans chaque colonne de l'une de ces matrices, tous les éléments sont égaux les uns aux autres :
.
A noter que la forme normale (100) de la matrice stochastique correspond à la division des états du système en groupes :
Chaque groupe dans (104) correspond à son propre groupe de séries dans (101). Selon la terminologie de L.N. Kolmogorov, les états du système inclus dans sont appelés essentiels et les états inclus dans les groupes restants sont appelés sans importance.
De la forme (101) de la matrice il résulte que pour tout nombre fini d'étapes (d'instant en instant ) la seule transition possible du système est a) d'un état essentiel à un état essentiel du même groupe, b) de d'un état sans importance à un état essentiel, et c) d'un état sans importance à un état sans importance du même groupe ou du groupe précédent.
De la forme (102) de la matrice, il résulte que dans le cas d'une transition n'est possible que de n'importe quel état à un état essentiel, c'est-à-dire que la probabilité de transition vers n'importe quel état non essentiel tend vers zéro avec le nombre d'étapes. C’est pourquoi les états essentiels sont parfois appelés états limites.
3. De la formule (97) il résulte :
.
Cela montre que chaque colonne de la matrice est un vecteur propre de la matrice stochastique pour le nombre caractéristique.
Pour une matrice régulière, le nombre 1 est une racine simple de l'équation caractéristique et ce nombre ne correspond qu'à un seul (à un facteur scalaire près) vecteur propre de la matrice. Par conséquent, dans n'importe quelle ème colonne de la matrice, tous les éléments sont égaux au même nombre non négatif :
Ainsi, dans une chaîne régulière, les probabilités limites de transition ne dépendent pas de l’état initial.
À l'inverse, si dans une chaîne de Markov homogène régulière, les probabilités de transition Prodel ne dépendent pas de l'état initial, c'est-à-dire que les formules (104) sont valables, alors dans le schéma (102) pour la matrice, il est nécessaire . Mais alors la chaîne est régulière.
Pour une chaîne acyclique, qui est un cas particulier de chaîne régulière, c'est une matrice primitive. Donc pour certains (voir Théorème 8 à la page 377). Mais alors 
.
A l'inverse, il s'ensuit que pour certains , et cela, d'après le théorème 8, signifie que la matrice est primitive et, par conséquent, la chaîne de Markov homogène donnée est acyclique.
Nous formulons les résultats obtenus sous la forme du théorème suivant :
Théorème 11. 1. Pour que toutes les probabilités de transition limites existent dans une chaîne de Markov homogène, il est nécessaire et suffisant que la chaîne soit régulière. Dans ce cas, la matrice composée des probabilités limites de transition est déterminée par la formule (95) ou (98).
2. Pour que les probabilités limites de transition dans une chaîne de Markov homogène régulière soient indépendantes de l'état initial, il est nécessaire et suffisant que la chaîne soit régulière. Dans ce cas, la matrice est déterminée par la formule (99).
3. Pour que toutes les probabilités limites de transition dans une chaîne de Markov homogène régulière soient différentes de zéro, il est nécessaire et suffisant que la chaîne soit acyclique.
4. Introduisons les colonnes de probabilités absolues
(105)
où est la probabilité que le système soit dans l'état (,) à ce moment-là. En utilisant les théorèmes d'addition et de multiplication des probabilités, on trouve :
(,),
(ins >> num).get(); // nombre de sommets string str;
où est la matrice transposée pour la matrice .
Toutes les probabilités absolues (105) sont déterminées à partir de la formule (106), si les probabilités initiales et la matrice des probabilités de transition sont connues
Introduisons les probabilités absolues limites
En passant des deux côtés de l'égalité (106) à la limite en , on obtient :
Notons que l'existence d'une matrice de probabilités de transition limites implique l'existence de probabilités absolues limites 
pour toutes probabilités initiales 
et vice versa.
De la formule (107) et de la forme (102) de la matrice il résulte que les probabilités absolues limites correspondant à des états sans importance sont égales à zéro.
Multiplier les deux côtés de l'égalité matricielle
à droite sur , on obtient grâce à (107) :
c'est-à-dire que la colonne des probabilités absolues marginales est un vecteur propre de la matrice du nombre caractéristique.
Si cette chaîne de Markov est régulière, alors c'est une racine simple de l'équation caractéristique de la matrice. Dans ce cas, la colonne des probabilités absolues limites est déterminée de manière unique à partir de (108) (puisque et ).
Soit une chaîne de Markov régulière. Alors de (104) et de (107) il résulte :
(109)
Dans ce cas, les probabilités absolues limites ne dépendent pas des probabilités initiales.
A l'inverse, cela peut ne pas dépendre en présence de la formule (107) si et seulement si toutes les lignes de la matrice sont identiques, c'est-à-dire
,
et donc (d'après le théorème 11) c'est une matrice régulière.
Si est une matrice primitive, alors , et donc en vertu de (109)
Au contraire, si tout ne dépend pas des probabilités initiales, alors dans chaque colonne de la matrice tous les éléments sont identiques et selon (109), et cela, selon le théorème 11, signifie que - une matrice primitive, c'est-à-dire cette chaîne est acyclique.
De ce qui précède, il résulte que le théorème 11 peut être formulé comme suit :
Théorème 11". 1. Pour que toutes les probabilités absolues limites existent dans une chaîne de Markov homogène pour toute probabilité initiale, il est nécessaire et suffisant que la chaîne soit régulière.
2. Pour que des probabilités absolues limites existent dans une chaîne de Markov homogène pour des probabilités initiales quelconques et ne dépendent pas de ces probabilités initiales, il est nécessaire et suffisant que la chaîne soit régulière.
3. Pour qu'une chaîne de Markov homogène ait des probabilités absolues limites positives pour toute probabilité initiale et pour que ces probabilités limites soient indépendantes des probabilités initiales, il est nécessaire et suffisant que la chaîne soit acyclique.
5. Considérons maintenant une chaîne de Markov homogène de type général avec une matrice de probabilités de transition.
Prenons la forme normale (69) de la matrice et notons-la par les indices d'imprimitivité des matrices dans (69). Soit le plus petit commun multiple d'entiers. Alors la matrice n'a pas de nombres caractéristiques égaux en module à un, mais différents de un, c'est-à-dire que c'est une matrice régulière ; dans ce cas - le plus petit indicateur auquel - la matrice correcte. On appelle le nombre la période d'une chaîne de Markov homogène donnée et... Inversement, si et 
, défini par les formules (110) et (110").
Les probabilités absolues marginales moyennes correspondant à des états sans importance sont toujours nulles.
Si la forme normale de la matrice est un nombre (et seulement dans ce cas), les probabilités absolues limites moyennes ne dépendent pas des probabilités initiales et sont déterminées de manière unique à partir de l'équation (111).
