Modèles de systèmes qui évoluent dans le temps selon des transitions probabilistes
Exemple: jouer au Pile ou Face
D'abord j'ai 3 francs et mon opposant a aussi 3 francs
A chaque tour j'ai une probabilité p de gagner un franc et
une probabilité 1-p de perdre un franc
L'``état'' du système est combien d'argent j'ai (0,1,2,3,4,5 ou 6)
Les transitions possibles sont:
Un ensemble E d'états possibles
Transitions à des moments de temps discrets
Probabilité de transition de l'état i à l'état j (à moment t) ne dépend pas des états antérieurs
Ici on considère les chaînes finies (nombre d'états fini) et homogènes (probabilité de transition d'état i à l'état j ne dépend pas de t).
On veut savoir, par exemple, le pourcentage des demandes qui échouent (faute d'assez de camions dans la ville de la demande).
On suppose bi la probabilité d'une demande qui nécessite exactement i camions de Bordeaux à Paris et ai la même probabilité dans la direction inverse.
Et on suppose que les demandes dans les 2 villes sont indépendantes.
Il y a 5 états selon le nombre de camions sur Bordeaux (la nuit).
La probabilité d'une transition de l'état i à l'état j:
i=j=0: a0
i=0, j=1: a1
i=1, j=0: a0(b1+b2+b3+b4)
i=1, j=1: a0b0 + a1(b1+b2+b3+b4)
etc.
On note Pi,j la probabilité d'une transition de l'état i à l'état j à un moment et P la matrice de ces probabilités.
Une matrice vérifiant les deux propriétés évidentes:
pour tout i,j et
est une
On note P(m)i,j la probabilité d'une transition de l'état i à l'état j dans m transitions et P(m) la matrice de ces probabilités.
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:
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:
Dans le jeu de Pile ou Face 0 et 6 sont des états persistants; les autres
sont transitoires.
Dans le système des camions ça dépend des probabilités:
si a0=b0=0 et les autres probabilités sont non-nulles,
0 et 4 sont des états transitoires et tous les autres sont
persistants..
On parle aussi des états ergodiques, c'est-à-dire ceux pour lesquels le temps moyen du premier retour à l'état i après être arrivé une fois en i est fini. Pour les chaînes finies il n'y a pas de différence entre persistant et ergodique.
Un état i est périodique avec période
si chaque circuit
de i à i comporte un nombre de transitions qui est un multiple de
(et
est l'entier maximum (supérieur à 1)
avec cette propriété), c'est-à-dire le plus grand diviseur
commun
des longueurs de tous les circuits qui contiennent i.
Les chemins dans ce graphe correspondent aux transitions possibles en plusieurs étapes (ou 1 ou 0).
Important: les composants fortement connexes
(ensemble 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
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
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);
Si l'un des états d'un composant est périodique avec période ,
c'est vrai pour tous.
On peut diviser les états en
classes:
,
de telle façon que chaque transition est d'une classe Ci à Ci+1
(ou de
à C0); les chemins de longueur
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é.