Probabilité d’atteinte d’un état
La probabilité d’atteinte d’un état et par extension le temps d’atteinte d’un état désigne le nombre de temps avant d’atteindre un état de la chaine de Markov.
(Xn)n désigne une chaîne de Markov homogène d’espace d’états X fini ou dénombrable de matrice de transition Q : on pourra interpréter Xn comme modélisant l’état d’un système à l’instant n.
La loi initiale de la chaîne (Xn) ayant été fixée, seuls interviennent dans l’étude de l’évolution de la chaîne les états susceptibles d’être atteints. On pose Xa = {x ∈ X, il existe n ≥ 0, P(Xn = x) > 0}.
Pour un état e ∈ Xa, on notera T(n)e le temps qu’il faut à la chaine pour atteindre l’état e strictement après l’instant n :
- T(n)e désigne donc le plus petit entier k > 0 tel que Xn+k = e si la chaîne passe par e après l’instant n
- T(n)e = +∞ si la chaine ne passe pas par l’état e après l’instant n.
- Pour simplifier les notations T(0)e sera aussi noté simplement Te.
Soit i, e ∈ Xa.
- Pour tout n ∈ N et k ∈ N∗ , la probabilité d’atteindre l’état e à l’instant n+k pour la première fois après l’instant n sachant que Xn = i ne dépend pas de n, on la notera fi,e(k) = P(T(n)e = k|Xn = i). Elle vérifie l’équation suivante : fi,e(1) = Q(i, e) et fi,e(k) = ∑j∈X\{e} Q(i, j)fj,e(k − 1) pour tout k ≥ 2.
L’équation pour fi,e(k) traduit simplement le fait que pour arriver pour la première fois dans l’état e en k pas, en partant de l’état i, il faut aller de l’état i à un état j≠e, puis partant de j, arriver pour la première fois en e en k − 1 pas.
- La probabilité d’atteinte d’un état e après l’instant n, sachant que Xn = i ne dépend pas de n, on la notera fi,e : fi,e = P(T(n)e < +∞|Xn = i). Elle vérifie : fi,e = Q(i e) + ∑j∈X\{e} Q(i,j)fj,e.
L’équation pour fi,e traduit le fait que la chaine atteint e à partir d’un état i soit directement, soit passe de l’état i à un état j≠e puis atteint e à partir de l’état j.
Notons que fi,e=1 si et seulement si fj,e=1 pour tout état j≠e tel que Q(i,j)>0.
Lorsque la chaîne est ergodique, il est possible de calculer le temps de retour dans un état en calculant l’inverse de la probabilité stationnaire. Pour cela il faut que tous les états sont récurrents positifs, c’est à dire que son espérance est positive et non infini :
Exemple de probabilité d’atteinte d’un état
Afin de montrer comment calculer la probabilité d’atteinte d’un état, nous allons prendre l’exemple suivant.
Supposons que le joueur dispose de 1 euro et joue à un jeu de hasard où la mise est de 1 euro jusqu’à ce qu’il ait atteint la somme de 3 euros ou jusqu’à ce qu’il soit ruiné.
Rappelons que p désigne la probabilité qu’il gagne une partie et donc gagne 1 euro et 1−p est la probabilité qu’il perde la partie et donc perde 1 euro.
On cherche la probabilité qu’il réussisse ainsi à avoir 3 euros, c’est-à-dire f1,3. L’équation avec i=1 et e=3 s’écrit f1,3 = pf2,3 + (1 − p)f0,3. On a f0,3 = 0 puisque le joueur ne peut pas jouer s’il n’a pas d’argent initialement (0 est un état absorbant). Il reste à écrire l’équation pour f2,3 qui est la probabilité qu’un joueur arrive à obtenir 3 euros s’il a au départ 2 euros. On obtient : f2,3 = 1 − p + (1 − p)f1,3. On a donc à résoudre un système de 2 équations à 2 inconnues : {f1,3 = pf2,3; f2,3 = p + (1 − p)f1,3}.
Ce système a une seule solution qui est f2,3 =p/(1−p(1−p) et f1,3 =p²/1−p(1−p).
En particulier, si le jeu est équitable c’est-à-dire si p = 1/2, on a f1,3 = 1/3 ce qui signifie que si le joueur a initialement 1 euro, il a une chance sur trois d’arriver à obtenir 3 euros. La probabilité que le jeu s’arrête car le joueur est ruiné se calcule de façon analogue en écrivant les équations satisfaites par f1,0, f2,0 et f3,0 et en résolvant le système obtenu. Ce calcul permet de voir que f1,0 + f1,3 = 1, ce qui signifie que le joueur s’arrête forcément au bout d’un nombre fini de parties soit parce qu’il a réussi à obtenir 3 euros, soit parce qu’il est ruiné.
Temps moyen d’atteinte à partir d’une configuration
Le temps moyen d’atteinte est la plus petite solution positive du système :
où la classe absorbante désigne les états dans lequel commence le système. En effet, puisque l’on part de ces états, le temps moyen pour les atteindre est de 0 mouvement.
Exemple de temps moyen d’atteinte
Une puce saute sur un triangle, avec une probabilité 2/3 dans le sens horaire, et 1/3 dans le sens anti-horaire.
- On numérote les sommets : 1,2,3.
- Intéressons-nous aux temps d’atteinte. Nous partons du sommet 1. On a
pour i = 1 : x1=0 - Pour i = 2, 3, nous devons résoudre les systèmes suivants :
- x2=1+ 1/3 x1 + 0 x2+ 2/3 x3
- x3=1+ 2/3x1+ 1/3 x2+ 0 x3
Ce qui donne pour solution le vecteur (0, 15/7, 12/7)
