Chaînes de Markov
Dans de nombreux modèles réels, nous supposons des résultats déterministes basés sur des formules. Cependant, de nombreux systèmes impliquent des variations aléatoires.
Un modèle stochastique utilise la probabilité pour prédire des résultats où le hasard est présent.
Une chaîne de Markov est un type spécifique de modèle stochastique qui décrit une séquence d'événements où la probabilité de chaque événement dépend uniquement de l'état atteint lors de l'événement précédent. C'est ce qu'on appelle la propriété sans mémoire ou propriété de Markov.
Un modèle stochastique utilise la probabilité pour prédire des résultats où le hasard est présent.
Une chaîne de Markov est un type spécifique de modèle stochastique qui décrit une séquence d'événements où la probabilité de chaque événement dépend uniquement de l'état atteint lors de l'événement précédent. C'est ce qu'on appelle la propriété sans mémoire ou propriété de Markov.
Chaîne de Markov
Définition
Une chaîne de Markov est une suite de variables aléatoires décrivant un système qui transite entre différents états. La propriété clé est que la probabilité de passer à l'état suivant dépend uniquement de l'état actuel et non de la séquence d'événements qui l'a précédé.
Définition Diagramme de transition
Un diagramme de transition illustre les états d'un système et les probabilités de passer d'un état à un autre.
- Les états sont représentés par des cercles (nœuds).
- Les flèches montrent le mouvement (transitions) entre les états.
- Chaque flèche est étiquetée avec une probabilité de transition.
- La somme des probabilités sur les flèches sortantes de n'importe quel état doit être égale à 1.
Exemple
- Si le temps est ensoleillé aujourd'hui, il y a une probabilité de \(0,9\) qu'il soit ensoleillé demain (boucle) et une probabilité de \(0,1\) qu'il soit pluvieux.
- Si le temps est pluvieux aujourd'hui, il y a une probabilité de \(0,5\) qu'il soit ensoleillé demain et une probabilité de \(0,5\) qu'il soit pluvieux.
Représentation matricielle
Une méthode puissante pour étudier les chaînes de Markov consiste à représenter les probabilités et les états à l'aide de matrices. Cela permet de calculer rapidement les états futurs en utilisant la multiplication matricielle.
Définition Vecteur d'état
La vecteur d'état \(S_n\) est un vecteur colonne qui montre la distribution de probabilité du système à l'étape \(n\).
- Elle représente la probabilité ou la proportion d'être dans chaque état.
- La somme des éléments d'une matrice d'état est toujours 1.
- L'état initial est noté \(S_0\).
Exemple
Si aujourd'hui est certainement Ensoleillé, la matrice d'état initial est \(S_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\).
Définition Matrice de transition
La matrice de transition \(T\) organise les probabilités de transition dans une matrice carrée.
Dans une matrice de transition \(T = (t_{ij})\) :
Dans une matrice de transition \(T = (t_{ij})\) :
- Les colonnes représentent l'état actuel (De).
- Les lignes représentent l'état suivant (Vers).
- L'entrée \(t_{ij}\) représente la probabilité de passer à l'état \(i\) depuis l'état \(j\).
- La somme de chaque colonne doit être égale à 1.
Exemple
Pour l'exemple de la météo :
Vecteurs d'état et probabilités futures
Méthode Calculer les états futurs
Pour prédire la distribution de probabilité du système après \(n\) étapes, nous multiplions la matrice de transition par le vecteur d'état de manière répétée.
La formule générale est :$$ S_n = T^n S_0 $$où \(T\) est la matrice de transition et \(S_0\) est le vecteur d'état initial.
La formule générale est :$$ S_n = T^n S_0 $$où \(T\) est la matrice de transition et \(S_0\) est le vecteur d'état initial.
- \(S_1 = T S_0\) (État après 1 étape)
- \(S_2 = T S_1 = T(TS_0) = T^2 S_0\) (État après 2 étapes)
Exemple
En utilisant la matrice météo \(T = \begin{pmatrix} 0{,}9 & 0{,}5 \\ 0{,}1 & 0{,}5 \end{pmatrix}\) et en supposant qu'il fait beau aujourd'hui (\(S_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\)), calculer les probabilités pour la météo dans 2 jours.
$$\begin{aligned}\mathbf{s}_2 &= \mathbf{T}^2 \mathbf{s}_0\\
&= \begin{pmatrix} 0{,}9 & 0{,}5 \\
0{,}1 & 0{,}5 \end{pmatrix}^2 \begin{pmatrix} 1 \\
0 \end{pmatrix} \\
&= \begin{pmatrix} 0{,}9 & 0{,}5 \\
0{,}1 & 0{,}5 \end{pmatrix} \begin{pmatrix} 0{,}9 & 0{,}5 \\
0{,}1 & 0{,}5 \end{pmatrix} \begin{pmatrix} 1 \\
0 \end{pmatrix}\\
&= \begin{pmatrix} (0{,}9)(0{,}9)+(0{,}5)(0{,}1) & (0{,}9)(0{,}5)+(0{,}5)(0{,}5) \\
(0{,}1)(0{,}9)+(0{,}5)(0{,}1) & (0{,}1)(0{,}5)+(0{,}5)(0{,}5) \end{pmatrix} \begin{pmatrix} 1 \\
0 \end{pmatrix}\\
&= \begin{pmatrix} 0{,}86 & 0{,}70 \\
0{,}14 & 0{,}30 \end{pmatrix} \begin{pmatrix} 1 \\
0 \end{pmatrix}\\
&= \begin{pmatrix} 0{,}86 \\
0{,}14 \end{pmatrix}.\end{aligned}$$Interprétation : Il y a \(86\pourcent\) de chances qu'il fasse beau et \(14\pourcent\) de chances qu'il pleuve dans 2 jours.
État stable
Définition Vecteur d'état stable
Pour de nombreuses chaînes de Markov régulières, à mesure que le nombre d'étapes augmente (\(n \to \infty\)), la matrice d'état \(S_n\) converge vers un vecteur constant \(S\), quel que soit l'état initial \(S_0\).
Ce vecteur \(S\) est appelé le vecteur d'état stable (ou distribution stationnaire).
Il satisfait l'équation d'équilibre :$$ T S = S $$Algébriquement, \(S\) est un vecteur propre de \(T\) correspondant à la valeur propre \(\lambda = 1\). La somme des éléments de \(S\) doit être égale à 1.
Ce vecteur \(S\) est appelé le vecteur d'état stable (ou distribution stationnaire).
Il satisfait l'équation d'équilibre :$$ T S = S $$Algébriquement, \(S\) est un vecteur propre de \(T\) correspondant à la valeur propre \(\lambda = 1\). La somme des éléments de \(S\) doit être égale à 1.
Méthode Trouver l'état stable
Pour trouver le vecteur d'état stable \(S = \begin{pmatrix} x \\ y \end{pmatrix}\) :
- Poser l'équation matricielle \(TS = S\).
- Convertir cela en un système d'équations linéaires.
- Utiliser la contrainte supplémentaire \(x + y = 1\) (pour un système à 2 états) pour déterminer \(x\) et \(y\).
Une ville gère un système de vélos en libre-service avec deux zones principales : le Centre-Ville (C) et la Gare (S).
Les vélos sont loués et rendus quotidiennement. La matrice de transition \(T\) représente la probabilité qu'un vélo change de zone ou reste dans la même zone à la fin de la journée :$$ T = \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7 \end{pmatrix} $$
Les vélos sont loués et rendus quotidiennement. La matrice de transition \(T\) représente la probabilité qu'un vélo change de zone ou reste dans la même zone à la fin de la journée :$$ T = \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7 \end{pmatrix} $$
- Trouver le vecteur d'état stable \(S = \begin{pmatrix} x \\ y \end{pmatrix}\) algébriquement.
- Si la ville possède \(1000\) vélos au total, déterminer comment ils devraient être répartis entre le Centre-Ville et la Gare à long terme pour répondre à la demande.
- Trouver un vecteur propre pour \(\lambda = 1\) :
$$\begin{aligned} TS &= S\\ \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} &= \begin{pmatrix} x \\ y \end{pmatrix}\\ \begin{pmatrix} 0{,}8x+0{,}3y \\ 0{,}2x+0{,}7y \end{pmatrix} &= \begin{pmatrix} x \\ y \end{pmatrix}\\ \end{aligned}$$ Cela donne \(0{,}8x+0{,}3y = x\) et \(0{,}2x+0{,}7y=y\).
En simplifiant, on obtient \(-0{,}2x+0{,}3y = 0\) et \(0{,}2x-0{,}3y=0\).
Ainsi \(0{,}2x = 0{,}3y\), ce qui implique \(2x = 3y\).
En posant \(y = 2t\), nous avons \(x = 3t\), donc : $$ S = \begin{pmatrix} 3t \\ 2t \end{pmatrix}$$ Puisque \(S\) est un vecteur d'état, la somme de ses composantes doit être égale à 1 : $$ 3t + 2t = 1 \implies 5t = 1 \implies t = \frac{1}{5} $$ $$ S = \begin{pmatrix} 3 \cdot \frac{1}{5} \\ 2 \cdot \frac{1}{5} \end{pmatrix} = \begin{pmatrix} 0{,}6 \\ 0{,}4 \end{pmatrix} $$ - À long terme, \(60\pourcent\) des vélos seront au Centre-Ville et \(40\pourcent\) à la Gare.
- Centre-Ville : \(1000 \times 0{,}6 = 600\) vélos.
- Gare : \(1000 \times 0{,}4 = 400\) vélos.