Matrice des états de transition d'une chaîne de Markov. Chaînes de Markov

1. matrice P2 transition du circuit de l'état je dans un état j en deux
étape;

2. distribution de probabilité sur les états à l'heure actuelle t=2;

3. la probabilité qu'à l'heure actuelle t=1 état du circuit sera A2;

4. distribution stationnaire.

Solution. Pour une chaîne de Markov discrète, si elle est homogène, la relation suivante est vraie :

où P1 est la matrice des probabilités de transition en une étape ;
Рn - matrice des probabilités de transition pour n étapes ;

1. Trouvez la matrice de transition P2 en deux étapes

Laissez la distribution de probabilité sur les états sur S la ième étape est déterminée par le vecteur
.
Connaître la matrice Pn transition en n étapes, nous pouvons déterminer la distribution de probabilité sur les états sur (S+n)-ème étape . (5)

2. Trouvons la distribution de probabilité sur les états du système à l'heure actuelle t=2. Mettons (5) S=0 et n=2. Alors .

Nous l'aurons.

3. Trouvons la distribution de probabilité sur les états du système à l'heure actuelle t=1.

Mettons (5) s=0 et n=1, alors .
Comment pouvons-nous voir que la probabilité qu'à l'heure actuelle t=1 état du circuit sera A2,égal r2(1)=0,69.
La distribution de probabilité sur les états est dite stationnaire si elle ne change pas d'étape en étape, c'est-à-dire
Alors à partir de la relation (5) à n=1 on obtient

4. Trouvons la distribution stationnaire. Puisque =2 nous avons =(p1; p2). Écrivons le système équations linéaires(6) dans formulaire de coordonnées

La dernière condition est appelée normalisation. Dans le système (6), une équation est toujours une combinaison linéaire d’autres. On peut donc le rayer. Résolvons ensemble la première équation du système et l'équation de normalisation. Nous avons 0,6 p1=0,3p2, c'est p2=2p1. Alors p1+2p1=1 ou , c'est-à-dire . Ainsi, .
Répondre:
1) la matrice de transition en deux étapes pour une chaîne de Markov donnée a la forme ;
2) distribution de probabilité sur les états à l'heure actuelle t=2 est égal ;
3) la probabilité qu'à l'heure actuelle t=1 état du circuit sera A2, est égal p2(t)=0,69;
4) la distribution stationnaire a la forme

Matrice donnée intensités de transition d'une chaîne de Markov continue. Créer un graphe d'état étiqueté correspondant à la matrice Λ ; créer un système équations différentielles Kolmogorov pour les probabilités d'état ; trouver la distribution de probabilité limite. Solution. Chaîne de Markov homogène avec un nombre fini d'états A1, A2,…UN caractérisé par la matrice des intensités de transition ,

Où - intensité de transition de la chaîne de Markov de l'État Je dans un état Aj; rij(Δt)-probabilité de transition Aï →Un J par intervalle de temps Δ t.

Les transitions du système d'un état à l'autre sont commodément spécifiées à l'aide d'un graphe d'état étiqueté, sur lequel sont marqués les arcs correspondant aux intensités. λ je>0. Créons un graphe d'état étiqueté pour une matrice donnée d'intensités de transition

Soit un vecteur de probabilités R.j(t),
j=1, 2,…,, le système est dans l'état UNj sur le moment t.

Évidemment 0≤ R.j(t)≤1 et . Ensuite, d'après la règle de différenciation d'une fonction vectorielle d'un argument scalaire, on obtient . Probabilités R.j(t) satisfaire le système d'équations différentielles de Kolmogorov (SDEK), qui en forme matricielle ressemble à . (7)

Si au moment initial le système était dans l'état Aj, alors le SDUK devrait être résolu dans les conditions initiales
R.je(0)=1, рj(0)=0, j≠i,j=1, 2,…,. (8)
L'ensemble de SDUK (7) et conditions initiales(8) décrit de manière unique une chaîne de Markov homogène avec temps continu et un nombre fini d'états.
Composons un SDEK pour une chaîne de Markov donnée. Puisque =3, alors j=1, 2, 3.

De la relation (7) on obtient

.
De là, nous aurons

La dernière condition est appelée normalisation.
La distribution de probabilité sur les états est appelée Stationnaire, s'il ne change pas avec le temps, c'est-à-dire où R.j=const, j=1,2,…,. D'ici .

Ensuite à partir de SDUK (7) nous obtenons un système pour trouver la distribution stationnaire
(9)
Pour ce problème, depuis le SDUK nous aurons

De la condition de normalisation on obtient 3р2+р2+р2=1 ou . Par conséquent, la distribution limite a la forme .
A noter que ce résultat peut être obtenu directement à partir du graphe d'état étiqueté si l'on utilise la règle : pour une distribution stationnaire, la somme des produits λ jipi, j≠je, pour les flèches provenant de je-ème état est égal à la somme des produits λ jipi, j≠je, pour les flèches incluses dans je-ième état. Vraiment,

Il est évident que le système résultant est équivalent à celui compilé à l’aide du SDUK. Il a donc la même solution.
Réponse : la distribution stationnaire a la forme .

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 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, 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. Dernière ligne 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, il est possible de construire un graphe d'état du système, é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. En utilisant la 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 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 de construire une transition matrice du système.

Cet article est de nature abstraite, rédigé sur la base de ceux donnés dans fin des sources, qui sont cités par endroits.

Introduction à la théorie des chaînes de Markov

Une chaîne de Markov est une telle séquence événements aléatoires, dans lequel la probabilité de chaque événement dépend uniquement de l'état dans lequel se trouve le processus ce moment et est indépendant des États antérieurs.

1. Le circuit discret final est déterminé par :
2. ensemble d'états S = (s 1, …, s n), l'événement est une transition d'un état à un autre à la suite d'un essai aléatoire vecteur probabilités initiales
3. (distribution initiale) p (0) = ( p (0) (1),…, p (0) (n)), déterminant la probabilité p (0) (i) qu'à l'instant initial t = 0 le processus était dans l'état s je matrice de probabilités de transition P = ( p je j), caractérisant la probabilité de transition de processus avecétat actuel

s i à l'état suivant s j , tandis que la somme des probabilités de transitions d'un état est égale à 1 :

∑ j =1… n p je j = 1

Un exemple de matrice de probabilité de transition avec un ensemble d'états S = (S 1, ..., S 5), un vecteur de probabilités initiales p (0) = (1, 0, 0, 0, 0) :

En utilisant le vecteur des probabilités initiales et la matrice de transition, nous pouvons calculer le vecteur stochastique p (n) - un vecteur composé des probabilités p (n) (i) que le processus sera dans l'état i au temps n. Vous pouvez obtenir p(n) en utilisant la formule :

P(n) = p(0)×Pn
Les vecteurs p (n) à mesure que n grandit, dans certains cas, se stabilisent - ils convergent vers un certain vecteur de probabilité ρ, que l'on peut appeler la distribution stationnaire de la chaîne. La stationnarité se manifeste dans le fait qu'en prenant p (0) = ρ, on obtient p (n) = ρ pour tout n.
Le critère le plus simple
, qui garantit la convergence vers une distribution stationnaire, ressemble à ceci : si tous les éléments de la matrice des probabilités de transition P sont positifs, alors comme n tend vers l'infini, le vecteur p (n) tend vers le vecteur ρ, qui est la seule solution au système du formulaire p × P = p. n tous les éléments de la matrice P n sont positifs, alors le vecteur p (n) va encore se stabiliser.
La preuve de ces affirmations est fournie en détail.

Une chaîne de Markov est représentée comme un graphe de transition dont les sommets correspondent aux états de la chaîne et les arcs correspondent aux transitions entre eux. Le poids de l'arc (i, j) reliant les sommets si et s j sera égal à la probabilité p i (j) transition du premier état au second.

Graphique correspondant à la matrice ci-dessus :

Classification des états des chaînes de Markov Lorsqu’on considère les chaînes de Markov, on peut s’intéresser au comportement du système sur une courte période de temps. Dans ce cas, les probabilités absolues sont calculées à l'aide des formules de la section précédente. Cependant, il est plus important d’étudier le comportement du système sur grand intervalle
moment où le nombre de transitions tend vers l’infini.
Ensuite, les définitions des états des chaînes de Markov sont introduites, nécessaires à l'étude du comportement du système à long terme. Les chaînes de Markov sont classées en fonction de la possibilité de transition d'un état à un autre. Les groupes d'états d'une chaîne de Markov (sous-ensembles de sommets du graphe de transition), qui correspondent aux sommets sans issue du diagramme d'ordre du graphe de transition, sont appelés classes ergodiques de la chaîne.

Si l'on considère le graphe ci-dessus, nous pouvons voir qu'il contient 1 classe ergodique M 1 = ( S 5 ), accessible à partir d'une composante fortement connexe correspondant à un sous-ensemble de sommets M 2 = ( S 1 , S 2 , S 3 , S4). Les états qui appartiennent à des classes ergodiques sont appelés essentiels, et les autres sont appelés non essentiels (bien que de tels noms ne correspondent pas bien à bon sens). L'état absorbant s i est un cas particulier de la classe ergodique. Puis, une fois dans cet état, le processus s’arrêtera. Pour S i, p ii = 1 sera vrai, c'est-à-dire dans le graphe de transition, une seule arête en émanera - une boucle., les écarts et, si nécessaire, les répartitions. En utilisant ces statistiques à l'avenir, vous pourrez optimiser le code du programme - en utilisant des méthodes de bas niveau pour accélérer les parties critiques du programme. Cette méthode est appelée profilage de code.

Par exemple, dans l'algorithme de Dijkstra, les états de circuit suivants sont présents :

• sommet (v), supprimer un nouveau sommet de la file d'attente prioritaire, passer à l'état b uniquement ;
• commencer (b), le début du cycle de recherche des arcs sortants pour la procédure d'affaiblissement ;
• analyse (a), analyse de l'arc suivant, passage possible vers a, d ou e ;
• diminuer (d), diminuer l'estimation pour un sommet du graphique, passer à a ;
• fin (e), achèvement de la boucle, passage au sommet suivant.

Il reste à définir les probabilités de transition entre les sommets, et vous pouvez étudier la durée des transitions entre les sommets, les probabilités d'entrer dans divers états et d'autres caractéristiques moyennes du processus.

De même, le processus de calcul, qui revient à accéder aux ressources du système dans l'ordre déterminé par le programme, peut être représenté par une chaîne de Markov absorbante, dont les états correspondent à l'utilisation des ressources du système - transition processeur, mémoire et périphériques ; les probabilités reflètent l’ordre d’accès aux diverses ressources. Grâce à cela, le processus informatique est présenté sous une forme pratique pour analyser ses caractéristiques.

Une chaîne de Markov est dite irréductible si un état S j peut être atteint à partir de n'importe quel autre état S i dans un nombre fini de transitions. Dans ce cas, tous les états du circuit sont dits communicants et le graphe de transition est un composant d’une forte connectivité.
la probabilité que le processus soit dans les états S j , j = 1,…, n, la proportion de temps que le processus passe dans chacun des états.

Les circuits irréductibles sont utilisés comme modèles de fiabilité du système. En effet, si une ressource qu’un processus utilise tombe très souvent en panne, la fonctionnalité de l’ensemble du système sera menacée.

Dans ce cas, la duplication d’une ressource aussi critique peut permettre d’éviter les pannes.

Dans ce cas, les états du système, qui diffèrent par la composition d'équipements en bon état et en panne, sont interprétés comme des états de circuit, dont les transitions sont associées à des pannes et à la restauration des appareils et à des changements dans les connexions entre eux, effectués pour maintenir le l'opérabilité du système. Les estimations des caractéristiques d'un circuit irréductible donnent une idée de la fiabilité du comportement du système dans son ensemble. De tels circuits peuvent également être des modèles d'interaction entre les appareils et les tâches soumises au traitement. Exemples d'utilisation

2 β 1 - α - 2 β 3β

1 - α - 3 β
4β
1 - 4 β
On peut noter qu'il possède une classe ergodique unique, et donc le système p × P = p dans la classe des vecteurs de probabilité a
seule décision

. Écrivons les équations du système qui nous permettent de trouver cette solution :

P 0 (1 - α) + p 1 β = p 0 ,
p 0 α + p 1 (1 - α - β) + p 2 2 β = p 1,
p 1 α + p 2 (1 - α - 2 β) + p 3 3 β = p 2,
p 2 α + p 3 (1 - α - 3 β) + p 4 4 β = p 3,

p 3 α + p 4 (1 - 4 β) = p 4 .

De là on obtient (avec γ = α / β) :

On connaît maintenant l'ensemble des probabilités π i selon lesquelles, en mode stationnaire, le système aura i blocs occupés. Ensuite, pendant une fraction du temps p 4 = C γ 4 /4, tous les blocs du système sont occupés, le système ne répond pas aux requêtes. Les résultats obtenus s'appliquent à un nombre quelconque de blocs. Vous pouvez désormais en profiter : vous pouvez comparer les coûts des appareils supplémentaires et la réduction du temps d'occupation complète du système.
Vous pouvez en savoir plus sur cet exemple dans .

Processus de prise de décision comportant un nombre fini et infini d’étapes

Considérons un processus dans lequel il existe plusieurs matrices de probabilité de transition. Pour chaque instant, le choix de l'une ou l'autre matrice dépend de la décision que nous prenons. Ce qui précède peut être compris à l’aide de l’exemple suivant.À la suite de l'analyse du sol, le jardinier évalue son état avec l'un des trois nombres suivants : (1) - bon, (2) - satisfaisant ou (3) - mauvais. Dans le même temps, le jardinier a remarqué que la productivité du sol de l'année en cours ne dépend que de son état de l'année précédente. Par conséquent, la probabilité d’une transition du sol sans

influences extérieures

Introduisons les matrices R1 et R2, qui déterminent les fonctions de revenu en fonction du coût des engrais et de la qualité du sol : R1 R2 Enfin, le jardinier est confronté au problème de savoir quelle stratégie choisir pour maximiser le rendement moyen attendu. Deux types de problèmes peuvent être considérés : finis et nombre infiniétapes. Supposons que le jardinier ait l'intention d'arrêter son activité au bout de N années.

Notre tâche est maintenant de déterminer la stratégie comportementale optimale pour le jardinier, c'est-à-dire la stratégie qui maximisera ses revenus. La finitude du nombre d'étapes de notre problème se manifeste dans le fait que le jardinier ne se soucie pas de ce qui arrivera à sa terre agricole en N + 1 an (toutes les années jusqu'à N inclus sont importantes pour lui). Nous pouvons maintenant voir que dans ce cas, le problème de recherche de stratégie se transforme en problème de programmation dynamique. Si nous désignons par f n (i) le revenu moyen maximum attendu qui peut être obtenu par étapes de n à N inclus, à partir du numéro d'état i, alors il est facile de dériver une relation de récurrence reliant f n (i) aux nombres f n + 1 (j)

F n (i) = max k (∑ j =1 m p ij k [ r ij k + f n +1 (j)]), n = 1, 2, …, N
Ici k est le numéro de la stratégie utilisée. Cette équation est basée sur le fait que le revenu total r ij k + f n +1 (j) est obtenu à la suite du passage de l'état i à l'étape n à l'état j à l'étape n +1 avec une probabilité p ij k .
La solution optimale peut maintenant être trouvée en calculant séquentiellement f n (i) dans le sens descendant (n = N ...1). Dans le même temps, introduire un vecteur de probabilités initiales dans l'énoncé du problème ne compliquera pas sa solution.

Cet exemple

également discuté dans . Modélisation de combinaisons de mots dans un texte. Mais il est impossible d'avancer de cette manière, car la croissance de la charge sémantique du texte dans les chaînes de Markov d'ordre élevé se produit beaucoup plus lentement que le déclin de l'unicité du texte. Et un texte construit sur des chaînes de Markov, par exemple, du trentième ordre, n'aura toujours pas assez de sens pour intéresser les humains, mais déjà assez similaire à texte original De plus, le nombre d'états dans un tel circuit sera étonnant.
Cette technologie est désormais très largement utilisée (malheureusement) sur Internet pour créer du contenu de pages web. Les personnes qui souhaitent augmenter le trafic vers leur site Web et améliorer son classement moteurs de recherche, efforcez-vous d'en mettre le plus possible sur leurs pages mots clés Pour la recherche. Mais les moteurs de recherche utilisent des algorithmes capables de distinguer le texte réel d’un fouillis incohérent de mots-clés. Ensuite, pour tromper les moteurs de recherche, ils utilisent des textes créés par un générateur basé sur une chaîne de Markov. Il y a bien sûr, exemples positifs l'utilisation de chaînes de Markov pour travailler avec du texte ; elles sont utilisées pour déterminer la paternité et analyser l'authenticité des textes.

Chaînes markoviennes et loteries

Dans certains cas modèle probabiliste utilisé pour prédire les numéros dans diverses loteries. Apparemment, cela ne sert à rien d’utiliser des chaînes de Markov pour modéliser l’enchaînement des différentes circulations. Ce qui est arrivé aux boules lors du tirage n'affectera en aucun cas les résultats du prochain tirage, car après le tirage, les boules sont récupérées et lors du prochain tirage, elles sont placées dans le plateau de loterie en ordre fixe. Dans ce cas, le lien avec la circulation passée est perdu. Une autre chose est la séquence de boules qui tombent au cours d'un même tirage.états correspondant au même événement observé. Par conséquent, nous ne pouvons construire qu’une matrice de probabilités de transition entre de tels groupes d’états. Ces probabilités sont la moyenne des probabilités de transitions entre différents États séparés, ce qui réduit bien sûr l'efficacité de l'application du modèle de chaîne de Markov aux loteries numériques.
Semblable à ce cas, un tel modèle réseau neuronal peut être utilisé pour les prévisions météorologiques, les cotations de devises et en relation avec d'autres systèmes où des données historiques sont disponibles et où les informations nouvellement reçues peuvent être utilisées à l'avenir. Bon usage dans ce cas, lorsque seules les manifestations du système sont connues, mais pas les états internes (cachés), des modèles de Markov cachés peuvent être appliqués, qui sont discutés en détail dans les Wikibooks (modèles de Markov cachés).

Littérature

1. Romanovsky I.V.
2. Analyse discrète : un manuel pour les étudiants, 3e éd. - Saint-Pétersbourg : dialecte Nevski ; BHV Saint-Pétersbourg, 2003. Taha, Hamdy A. Introduction à la recherche opérationnelle, 6e éd.
3. - M. :
4. Maison d'édition

Williams, 2001.

1. Werner M. Bases du codage. Manuel pour les universités.
2. - M. : Tekhnosphère, 2004.

Belyaev A., Gavrilov M., Masalskikh A., Medvinsky M. Processus de Markov, 2004. Visualiseurs Alekseev V. Markov processus décisionnels, 2002. Chaînes Belyaev A. Markov, 2002. Méthodes
descriptions mathématiques Markovien processus aléatoires dans un système à états discrets (DS), cela dépend 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 moment aléatoire S temps, alors nous avons affaire à n processus de Markov aléatoire à temps continu. S 1 , S 2 , …, Qu'il y ait système physique t 1 , t 2 , …, , qui peut être dansÉtats S S n . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments merci
, appelons ces moments en pas de temps. Nous considérerons la coentreprise dans le système S 1 → S 2 → S 3 → S 2 .
en fonction de l'argument entier 1, 2, ..., k (, où l'argument est le numéro de l'étape. Exemple: . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments Acceptons de désigner S je.
k . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments) – un événement consistant dans le fait qu’après , où l'argument est le numéro de l'étape.étapes pendant lesquelles le système est dans l'état S , où l'argument est le numéro de l'étape. je Pour toute (, où l'argument est le numéro de l'étape.événements S 1 ( ) , S 2 () ,…,S n

) formulaire
groupe complet d'événements S 1 (0) , S et sont
Cette séquence est appelée Chaîne de Markov , si pour chaque étape la probabilité de transition depuis n'importe quel état k 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 k.
Laissez à tout moment après n'importe quel . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments-ème système d'étape S peut être dans l'un des États S 1 , S 2 , …, Qu'il y ait, c'est-à-dire qu'un événement parmi un groupe complet d'événements peut se produire : S 1 (, où l'argument est le numéro de l'étape.étapes pendant lesquelles le système est dans l'état S , où l'argument est le numéro de l'étape.) , …, Qu'il y ait (, où l'argument est le numéro de l'étape.) . Notons les probabilités de ces événements :
P. 1 (1) = P.(S 1 (1)); P. 2 (1) = P.(S 2 (1)); …; P n(1) = P.(Qu'il y ait (, où l'argument est le numéro de l'étape.));
P. 1 (2) = P.(S 1 (2)); P. 2 (2) = P.(S 2 (2)); ... ; P n(2) = P.(Qu'il y ait (2));
P. 1 (. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments) = P.(S 1 (. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments)); P. 2 (. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments) = P.(S 2 (. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments)); …; P n(. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments) = P.(Qu'il y ait (. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments)).
Il est facile de voir que pour chaque numéro d’étape la condition est satisfaite
P. 1 (. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments) + P. 2 (. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments) +…+ P n(. Les transitions d'un état à l'autre ne sont possibles qu'à certains moments) = 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 . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments.
Exemple. Qu'il y ait une sorte de système qui puisse exister 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 à ( . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments+ 1)ème étape dépend uniquement de l'état à k- m pas.
Pour toute étape . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments 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 , …, Qu'il y ait. Connaître la probabilité de transition vers un autre état en une seule étape pour chaque état, c'est-à-dire P ij(depuis k 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 k dans le même état k.
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 k 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 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 à chaque étape soit donnée, alors la probabilité que le système S sur . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments-ème étape sera en l'état k, 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 . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments-ème étape. Supposons qu'au moment initial le système soit dans l'état S m. Alors pour t = 0
.
Trouvons les probabilités après la première étape. De l'état S m 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 pleine probabilité 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 seuls les non nuls sont pris en compte. Probabilité de toute condition après . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments-ème étape :

(7.4)
Ainsi, la probabilité d'un état après . Les transitions d'un état à l'autre ne sont possibles qu'à certains moments 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, pour le reste n-m étapes de l'état intermédiaire r, il ira à l'état final j avec une 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.

La chaîne de Markov est un processus de Markov à temps discret défini dans un espace mesurable.

Introduction

Les processus aléatoires de Markov portent le nom de l'éminent mathématicien russe A.A. Markov (1856-1922), qui a commencé l'étude de la connexion probabiliste des variables aléatoires et a créé une théorie que l'on peut appeler « dynamique des probabilités ».

DANS autres bases cette théorie était la base initiale théorie générale processus aléatoires, ainsi que des processus aussi importants sciences appliquées, comme la théorie des processus de diffusion, la théorie de la fiabilité, la théorie faire la queue etc. Actuellement, la théorie des processus markoviens et ses applications sont largement utilisées dans divers domaines.

En raison de la simplicité et de la clarté comparatives de l'appareil mathématique, de la grande fiabilité et de la précision des solutions obtenues, Attention particulière Processus de Markov acquis auprès de spécialistes impliqués dans la recherche opérationnelle et la théorie de la prise de décision optimale.

Exemple simple : lancer une pièce de monnaie

Avant de donner une description régime général, tournons-nous vers exemple simple. Faisons comme si nous parlons de sur les lancers successifs d'une pièce de monnaie dans un jeu de tirage au sort ; une pièce est lancée à des instants conditionnels t = 0, 1, ... et à chaque étape, le joueur peut gagner ±1 avec la même probabilité 1/2, donc à l'instant t sa victoire totale est valeur aléatoireξ(t) avec valeurs possibles j = 0, ±1, ...

Pourvu que ξ(t) = k, à l'étape suivante le gain sera déjà égal à ξ(t+1) = k ± 1, en prenant valeurs spécifiées j = k ± 1 avec probabilité égale 1/2.

Classiquement, on peut dire qu'ici, avec la probabilité correspondante, une transition se produit de l'état ξ(t) = k à l'état ξ(t+1) = k ± 1.

Formules et définitions

En généralisant cet exemple, nous pouvons imaginer un « système » avec un nombre dénombrable d'états de « phase » possibles, qui au cours d'un temps discret t = 0, 1, ... passe aléatoirement d'un état à l'autre.

Soit ξ(t) sa position au temps t résultant d'une chaîne de transitions aléatoires

ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Désignons formellement tout états possibles entiers i = 0, ±1, ... Supposons que pour un état connu ξ(t) = k, à l'étape suivante le système passe à l'état ξ(t+1) = j avec probabilité conditionnelle

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

quel que soit son comportement dans le passé, plus précisément quel que soit l'enchaînement de transitions (1) jusqu'à l'instant t :

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) pour tout t, k, j... (3) - Propriété de Markov.

Ce schéma probabiliste est appelé chaîne de Markov homogène avec un nombre dénombrable d'états- son homogénéité réside dans le fait que ceux définis en (2) probabilités de transition p kj, ∑ j p kj = 1, k = 0, ±1, ..., ne dépendent pas du temps, c'est-à-dire P(ξ(t+1) = j|ξ(t) = k) = P ij - matrice de probabilité de transition en une étape ne dépend pas de n.

Il est clair que P ij - Matrice Carrée avec des éléments non négatifs et des sommes unitaires sur les lignes.

Une telle matrice (finie ou infinie) est appelée matrice stochastique. Toute matrice stochastique peut servir de matrice de probabilités de transition.

En pratique : livraison de matériel aux quartiers

Supposons qu'une certaine entreprise livre du matériel à Moscou : district nord(noté A), sud (B) et central (C). L'entreprise dispose d'une équipe de coursiers qui dessert ces zones. Il est clair que pour effectuer la prochaine livraison, le coursier se rend dans la zone actuellement la plus proche de lui. Les éléments suivants ont été déterminés statistiquement :

1) après la livraison à A, la livraison suivante est effectuée dans 30 cas en A, dans 30 cas - en B et dans 40 cas - en C ;

2) après la livraison à B, la livraison suivante est effectuée dans 40 cas en A, dans 40 cas - en B et dans 20 cas - en C ;

3) après livraison à C, la livraison suivante est effectuée dans 50 caisses en A, dans 30 caisses - en B et dans 20 caisses - en C.

Ainsi, la zone de livraison suivante est déterminée uniquement par la livraison précédente.

La matrice de probabilité de transition ressemblera à ceci :

Par exemple, p 12 = 0,4 est la probabilité qu'après la livraison dans la zone B, la prochaine livraison soit effectuée dans la zone A.

Supposons que chaque livraison suivie d'un déplacement vers la zone suivante prend 15 minutes. Ensuite, selon les statistiques, après 15 minutes, 30 % des coursiers qui étaient en A seront en A, 30 % seront en B et 40 % seront en C.

Puisqu'à l'instant suivant chacun des courriers sera définitivement dans l'un des quartiers, la somme des colonnes est égale à 1. Et comme il s'agit de probabilités, chaque élément de la matrice est 0<р ij <1.

La circonstance la plus importante qui nous permet d'interpréter ce modèle comme une chaîne de Markov est que la localisation du courrier à l'instant t+1 dépend seulement de l'emplacement au temps t.

Posons maintenant une question simple : si le coursier part de C, quelle est la probabilité qu'après avoir effectué deux livraisons, il se retrouve en B, c'est-à-dire comment atteindre B en 2 étapes ? Il existe donc plusieurs chemins de C à B en 2 étapes :

1) d'abord de C vers C puis de C vers B ;

2) C-->B et B-->B ;

3) C-->A et A-->B.

Étant donné la règle de multiplication événements indépendants, on trouve que la probabilité recherchée est égale à :

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Remplacement de valeurs numériques :

P = 0,5*0,3 + 0,3*0,4 + 0,2*0,3 = 0,33

Le résultat obtenu suggère que si le coursier commençait à travailler à partir de C, alors dans 33 cas sur 100, il se retrouverait en B après deux livraisons.

Les calculs sont évidemment simples, mais s’il faut déterminer la probabilité après 5 ou 15 livraisons, cela peut prendre beaucoup de temps.

Montrons une manière plus simple de calculer de telles probabilités. Afin d’obtenir les probabilités de transition de diverses conditions en 2 étapes, on met au carré la matrice P :

Alors l'élément (2, 3) est la probabilité de transition de C à B en 2 étapes, qui a été obtenue ci-dessus d'une autre manière. Notez que les éléments de la matrice P2 vont également de 0 à 1 et que la somme des colonnes est 1.

Que. s'il faut déterminer les probabilités de passage de C à B en 3 étapes :

1 façon. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0,37*0,3 + 0,33*0,4 + 0,3*0,3 = 0,333, où p(CA) - la probabilité de transition de C à A en 2 étapes (c'est-à-dire qu'il s'agit de l'élément (1, 3) de la matrice P 2).

Méthode 2. Calculer la matrice P3 :

La matrice des probabilités de transition à la puissance 7 ressemblera à ceci :

Il est facile de remarquer que les éléments de chaque ligne tendent vers certains nombres. Cela suggère qu'après suffisamment grande quantité livraison, peu importe dans quelle région le coursier a commencé à travailler. Que. à la fin de la semaine, environ 38,9% seront en A, 33,3% en B et 27,8% en C.

Une telle convergence est garantie si tous les éléments de la matrice de probabilité de transition appartiennent à l'intervalle (0, 1).