Le graphe de transitions
Le graphe orienté dont les sommets sont les états et les arcs sont les transitions possibles (Pi,j > 0) permet de trouver les états persistants etc.

Les chemins dans ce graphe correspondent aux transitions possibles en plusieurs étapes (ou 1 ou 0).

Important: les composants fortement connexes du graphe appelés classes de la ch^ine
(ensemble maximal de sommets tel qu'il existe un chemin de chacun à chaque autre)
Le système entrera (avec probabilité 1) dans un composant sans sortie et ensuite devra y rester; Les états d'un tel composant constituent une petite chaîne où tous les états sont persistants (donc ergodiques)
S'il y a un seul composant fortement connexe la chaîne est irréductible
Tous les états d'un composant sont du même type: tous persistants (une classe finale d'états) ou tous transitoires (une classe de passage);

Décomposition en chaînes simples

Un autre graphe (sommets les composants du premier; arcs correspondant aux transitions entre composants) suffit pour montrer dans quels composants le système peut finir étant donné un état initial
Si l'un des états d'un composant est périodique avec période l, c'est vrai pour tous.

En ce cas, on peut diviser les états de la classe en l sous-classes:
C0,C1,¼Cl-1, de telle façon que chaque transition est d'une sous-classe Ci à Ci+1 (ou de Cl-1 à C0); les chemins de longueur l donnent une chaîne à l'intérieur de chaque Ci où tous les états sont persistants et apériodiques.
L'étude du comportement du système a été réduite à deux questions: l'étude des systèmes ergodiques et apériodiques; et la question de dans quelle sous-chaîne on peut finir et avec quelle probabilité.

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 2 transitions est la somme pour tout k de la probabilité d'une transition de i à k dans la première transition suivie d'une transition de k à j dans la deuxième:
P(2)i,j  =  n
å
k=1 
Pi,kPk,j

P(2) =  P2

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:


P(m)i,j  =  n
å
k=1 
P(m-1)i,kPk,j

P(m)   =  P(m-1)P

P(m)   =  Pm

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 (une classe finale 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, elle ne va jamais changer

C'est-à-dire que si pj est la limite de Pi,j(m), åi pi Pi,j = pj.

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:

p1+p2+¼pn = 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.

Choisir une classe finale C et pour chaque état i, définir pi la probabilité de tomber enfin dans C.

Si i est dans C, pi=1; si i est dans une autre classe finale pi=0; sinon
pi = n
å
j=1 
Pi,jpj
(Une équation pour chaque ligne de P)
Et cette fois les équations sont indépendantes et, donc, suffisent pour calculer les pi.
On peut faire ça pour chaque C finale et la distribution limite pour un état initial i est la somme pondérée des distributions limite de chaque classe finale C avec pour poids la probabilité de tomber en C à partir de l'état i.

Savoir si une classe est périodique

Le cas périodique

Il n'y a plus de distribution limite.
Pour tout i < l il y a une distribution limite valable pour les temps º i mod l.

On divise les états persistants en les l sous-classes et on calcule une distribution limite sur chaque sous-classe en utilisant la matrice de transitions en l étapes, Pl.

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 l.

Trivial dans le cas où tous les états sont persistants;
sinon le cas i=0 est résolu par le calcul des probabilités de tomber dans chacune des classes finales appliqué à Pl;
et on en déduit les valeurs pour les autres i.




File translated from TEX by TTH, version 3.05.
On 16 Sep 2003, 17:16.