Calculs exacts et asymptotiques
Calcul exact des probabilités de transition en plusieurs étapes
|
|
La probabilité d'une transition de l'état i à l'état j dans m transitions est la somme pour tout k de la probabilité d'une transition de i à k dans les premières m-1 transitions suivie d'une transition de k à j dans la dernière:
|
|
|
Calcul qui peut être fait de façon efficace par calcul des carrés
Trouver les composantes fortement connexes
Les calculs asymptotiques
La distribution limite (s'il existe une seule classe finale et elle est
apériodique)
(Le cas le plus important)
Propriété de stationnarité
Pour n'importe quelle configuration initiale (un seul état ou une distribution aléatoire entre plusieurs), les probabilités du système doivent converger sur la même distribution limite
Si la configuration initiale est déjà la distribution limite, alors elle ne va jamais changer
C'est-à-dire que si Πj est la limite de Pi,j(m), ∑i Πi Pi,j = Πj.
n équations linéaires en n variables.
(une pour chaque colonne de P)
Un seul vecteur possède cette propriété?
Ces n équations linéaires suffisent-elles pour déterminer les n variables (valeurs de la distribution limite)?
Non! Le vecteur (0,0,0,…,0) est aussi une solution!
(en effet la dernière équation est une combinaison linéaire des autres parce que la matrice est stochastique)
Il faut ajouter une nouvelle équation (indépendante) afin de réduire le nombre de solutions à 1:
Π1+Π2+…Πn = 1.
Le cas de plusieurs classes finales
(non périodiques)
Il suffit de calculer la probabilité de tomber dans chaque classe finale
La probabilité asymptotique d'être dans l'état i est 0 si i est
un état transitoire et, sinon, la probabilité de tomber dans la classe
finale contenant i multipliée par la probabilité d'être dans l'état i
dans la distribution limite de la chaîne irréductible de cette classe.
Pour déterminer la probabilité de finir dans une classe C, on peut définir pour chaque état i la probabilité qi de tomber enfin dans C.
Si i est dans C, qi=1; si i est dans une autre
classe finale qi=0;
sinon
|
Savoir si une classe est périodique
Le cas périodique
Il n'y a plus de distribution limite.
Pour tout i < λ il y a une distribution limite valable pour les temps
= i mod λ (étant donné un état initial).
On divise les états persistants en les λ sous-classes et on calcule une distribution limite sur chaque sous-classe en utilisant la matrice de transitions en λ étapes, Pλ.
Pour savoir la probabilité que, à temps t (t grand) on est dans un état donné, il faut d'abord calculer la probabilité d'être tombé dans chaque sous-classe, probabilité qui dépend de t mod λ.
Trivial dans le cas où tous les états de la chaîne
sont persistants;
sinon le cas i=0 est résolu par le
calcul des probabilités de tomber dans chacune
des classes finales appliqué à Pλ;
et on en déduit les valeurs pour les autres i.