Probabilité d’atteinte d’un état

DIfficulté
Moyen 50%

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 :

probabilité d'atteinte d'un état

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

En plus de la probabilité d’atteinte d’un état, il est possible de calculer le temps moyen d’atteinte de cet état.

Le temps moyen d’atteinte est la plus petite solution positive du système :

probabilité d'atteinte d'un état

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

Ici la probabilité d’atteinte d’un état n’est pas calculer. Dans les faits, la probabilité d’atteinte d’un état et le temps moyen d’atteinte des états doivent être étudiés ensemble.

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)

Partager
fr_FRFR
%d blogueurs aiment cette page :