Module C1.7 : Processus stochastique et simulation
Les chaînes de Markov
Les calculs exacts et asymptotiques

Les calculs exacts
Les calculs asymptotiques
Exercices


Auteur(s) : Mike Robson - IUP Miage Bordeaux
Date de dernière modification : 12 juin 2004

Il s'agit ici de calculer pour une chaîne donnée les probabilités de transition d'un état i à un état j sur une période plus ou moins longue. Si la durée d'attente est finie, nous réalisons des calculs exacts, sinon on peut calculer la tendance, c'est-à-dire que les calculs donnent des probabilités asymptotiques.

Les calculs exacts

Type de calcul

La probabilité d'une transition de l'état i à l'état j en deux étapes est la somme pour tout état intermédiaire k de la probabilité d'une transition de i à k dans la première et d'une transition de k à j dans la deuxième.

Ces équations se traduisent en équation matricielle :

 ,

où l'élément de la i-ième ligne et la j-ième colonne de la matrice P(2) est la probabilité de la transition de l'état i à l'état j en deux étapes, pour 1≤ i ≤ n et 1≤ j ≤ n .

On peut généraliser le calcul de ces probabilités à m étapes. Pour aller de l'état i à l'état j en m étapes, il est donc facile de définir la matrice des probabilités de transition .

La probabilité d'une transition de l'état i à l'état j dans m étapes est la somme pour tout état k de la probabilité d'une transition de i à k dans les premières m-1 transitions et d'une transition de k à j dans la dernière. Donc

 .

Et, bien sûr, on peut calculer Pm pour m grand, avec peu de multiplications de matrices en utilisant . (Approximativement au lieu de m-1 pour le calcul naïf).

Une variante de ce calcul

 

Les calculs asymptotiques

Caractéristiques

Pour n'importe quelle configuration initiale d'une chaîne non périodique, les probabilités du système convergent vers une distribution limite. Une fois la distribution limite atteinte, on dit que le système est stationnaire. S'il n'y a qu'une seule classe finale, alors la distribution limite ne dépend pas de la distribution initiale et la distribution limite est l'unique distribution stationnaire. La limite de ne dépend pas de i. On peut alors écrire pour cette limite.

On peut remarquer que si la configuration initiale est déjà la distribution limite alors elle ne va jamais changer. Donc,

(une équation par colonne de la matrice) où n est le nombre d'états de la chaîne.

Détermination de la distribution limite d'une chaîne

Le cas de plusieurs classes finales non périodiques

Avec probabilité 1, le système va terminer dans une classe finale ; pour un état initial donné, on veut savoir la probabilité de chaque classe finale.

La méthode à appliquer est la suivante :

Et cette fois comme les équations sont indépendantes, elles suffisent pour calculer les .

On peut faire cela 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 ou non

On sait déjà calculer la matrice des chemins de longueur ≤ m. Voici les repères à avoir maintenant :

Le cas périodique

Ici, il n'y a plus de distribution limite, mais pour tout i < λ il y a une distribution limite valable pour les temps . Voici la méthode a appliquer :

 


 

Exercices

Questionnaire de compréhension immédiate