Notions de graphes probabilistes
Définition
On appelle graphe probabiliste tout graphe orienté pondéré par des réels positifspour lequel la somme des poids des arêtes issues d’un même sommet est toujours égale à 1.
Matrice de transition d’un graphe probabiliste
- Soit \(G\) un graphe probabiliste d’ordre \(N \in \mathbb{N}^*\). On appelle matrice de transition du graphe la matrice \(P=\left(p_{i, j}\right)_{1 \leqslant i, j \leqslant N}\) telle que, pour tout \((i, j) \in \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right]^2\), \( p_{i, j}\) soit égal au poids de l’arc allant de \(i\) vers \(j\).
- Si \(P=\left(p_{i, j}\right)_{1 \leqslant i, j \leqslant N}\) est la matrice de transition d’un graphe probabiliste \(G\), alors : \[ \forall(i, j) \in \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right]^2, \ p_{i, j} \geqslant 0 \text { et } \forall i \in \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right], \ \sum_{j=1}^N p_{i, j}=1 \] On dit que la matrice \(P\) est une matrice stochastique.
Chaînes de Markov
Dans toute la suite, on considère une suite \(\left(X_n\right)_{n \in \mathbb{N}}\) de variables aléatoires discrètes définies sur un même espace probabilisé \((\Omega, \mathcal{A}, \mathbb{P})\), toutes à valeurs dans une partie \( \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right] \) de \(\mathbb{N}^*\).
Définition
- On dit que \(\left(X_n\right)_{n \in \mathbb{N}}\) est une chaîne de Markov d’espace d’états \([1, N]\) si, pour tout \(n \in \mathbb{N}^*\) et pour toute famille \(\left(i_0, \ldots, i_{n-1}, i, j\right)\) d’éléments de \( \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right] \) tels que \(\mathbb{P}\left(X_0=i_0, X_1=i_1, \ldots, X_n=i_n\right) \neq 0\), on a : \[ \mathbb{P}_{[X_0=i_0, X_1=i_1, \ldots, X_{n-1}=i_{n-1}, X_n=i]}(X_{n+1}=j)=\mathbb{P}_{[X_n=i]}(X_{n+1}=j) \] Autrement dit, si la suite \(\left(X_n\right)_{n \in \mathbb{N}}\) représente l’évolution au cours du temps d’un processus, \(\left(X_n\right)_{n \in \mathbb{N}}\) est une suite de Markov si l’état du processus à l’instant \(n+1\) ne dépend du passé qu’au travers de l’instant \(n\). On parle aussi de processus sans mémoire.
- Une chaîne de Markov \(\left(X_n\right)_{n \in \mathbb{N}}\) dite homogène si les probabilités si les probabilités conditionnelles \(\mathbb{P}_{\left[X_n=i\right]}\left(X_{n+1}=j\right)\) sont indépendantes de \(n\).
Matrice de transition d’une chaîne de Markov
Définition
L’évolution des états d’une chaîne de Markov d’espace d’états \( \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right]\) peut être représentée par un graphe probabiliste, dont les sommes sont \(1,2, \ldots, N\) et tel que, pour tout \((i, j) \in \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right]^2\), le poids \(p_{i, j}\) de l’arc allant de \(i\) à \(j\) soit égal à la probabilité \(\mathbb{P}_{[X_n=i]}(X_{n+1}=j)\) ; cette probabilité est appelée probabilité de passage de l’état \(i\) à l’état \(j\) en une étape et la matrice de transition du graphe probabiliste associé est aussi appelée matrice de transition de la chaîne de Markov.
Propriété
Si \(P\) est la matrice de transition d’un graphe probabiliste, il existe une chaîne de Markov admettant \(P\) pour matrice de transition.
États probabilistes
Définition
Si \(\left(X_n\right)_{n \in \mathbb{N}^*}\) est une chaîne de Markov d’espace d’états \( \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right] \), alors, pour tout \(n \in \mathbb{N}^*\), on appelle \( n^{\text{ème}}\) état probabiliste de la chaîne de Markov le vecteur ligne \(V_n\) défini par : \[ V_n=\left(\mathbb{P}(X_n=j)\right)_{1 \leqslant j \leqslant N}=\left(\mathbb{P}(X_n=1) \quad \mathbb{P}(X_n=2) \quad \cdots \quad \mathbb{P}(X_n=N)\right) \]
Théorèmes
Soit \(\left(X_n\right)_{n \in \mathbb{N}^*}\) une chaîne de Markov d’espace d’états \( \left[\kern-0.15em\left[ {1 , N} \right]\kern-0.15em\right] \), \( P\) sa matrice de transition et, pour tout \(n \in \mathbb{N}^*, V_n\) le \(n^{\text {ème }}\) état probabiliste de la chaîne de Markov. On a :
- \( \forall n \in \mathbb{N}, \ V_{n+1}=V_n P \)
- \( \forall n \in \mathbb{N}, V_n=V_0 P^n \)
États stables
- Si \( \left(X_n\right)_{n \in \mathbb{N}}\) est une chaîne de Markov homogène de matrice de transition \(P\), on appelle état probabiliste stable ou loi stationnaire de la chaîne de Markov tout vecteur ligne \(V\) définissant une loi de probabilité tel que \(V P=V\).
- En particulier, un vecteur ligne \(V\) définissant une loi de probabilité n’est pas nul et est une loi stationnaire de la chaine de Markov si et seulement si \({ }^t \! P \,{}^t V={ }^t V\), donc sí et seulement \({ }^t V\) est un vecteur propre de \(P\) associé à la valeur propre 1.