Chaque matin, Léa choisit entre le vélo et le bus ; à chaque étape, une boule change d'urne au hasard. L'étape suivante ne dépend que de l'état présent : c'est le hasard sans mémoire des chaînes de Markov, que le calcul matriciel étudie. À la fin, tu sauras passer d'un énoncé à un graphe pondéré et à une matrice, calculer la distribution après étapes, interpréter et trouver une distribution invariante.
Chaîne de Markov et graphe pondéré
Définition
On observe un système aux instants ; à chaque instant, il occupe l'un de ses deux ou trois états, noté à l'instant : c'est une variable aléatoire. La probabilité se note , pour la distinguer de la matrice .
La suite est une chaîne de Markov si la probabilité d'être dans l'état à l'instant , sachant qu'on est dans l'état à l'instant , ne dépend que de et de : ni de , ni des états occupés avant. Ce nombre est la probabilité de transition de vers :
Exemple
Chaque jour, Léa va au lycée à vélo (V) ou en bus (B). Si elle a pris le vélo, elle le reprend le lendemain avec la probabilité ; si elle a pris le bus, elle prend le vélo le lendemain avec la probabilité . Son choix ne dépend que de la veille : c'est une chaîne de Markov à deux états, avec , , et .
Le graphe orienté pondéré associé
On associe à la chaîne un graphe orienté pondéré : un sommet par état, et un arc de vers de poids dès que ; l'arc de vers est une boucle. Les poids des arcs sortant d'un sommet, boucle comprise, ont pour somme : le système va forcément quelque part.
Exemple
Le graphe de Léa a deux sommets V et B, deux boucles (V → V de poids , B → B de poids ) et deux arcs (V → B de poids , B → V de poids ). Contrôle : et .
La matrice de transition
Les états étant numérotés (ou ), la matrice de transition est la matrice carrée dont le coefficient ligne , colonne , vaut . La ligne décrit les départs depuis l'état : ses coefficients sont positifs et leur somme vaut . Un arc absent donne un coefficient nul.
Exemple 1. Pour Léa, dans l'ordre V puis B :
Exemple 2 : le modèle d'Ehrenfest. Deux boules sont réparties entre deux urnes A et B ; à chaque étape, on choisit une boule au hasard et on la change d'urne. L'état est le nombre de boules dans A. Depuis ou , on passe forcément à . Depuis , on va en ou en avec la probabilité chacune, selon l'urne de la boule choisie. Dans l'ordre , , :
Une marche aléatoire sur un graphe est aussi une chaîne de Markov : depuis un sommet de degré , le pion rejoint chacun de ses voisins avec la probabilité . Sur le graphe complet à trois sommets, a des sur la diagonale et des ailleurs.
Évolution de la distribution
Distribution initiale et récurrence
La distribution à l'instant est la matrice ligne des probabilités des états, dans l'ordre choisi ; ses coefficients ont pour somme . Pour deux états, . La distribution initiale est .
Propriété. Pour tout entier naturel , , et donc .
Démonstration (deux états). Les événements et forment une partition de l'univers ; pour chaque état , la formule des probabilités totales donne
C'est le produit de la ligne par la colonne de , donc le coefficient de : ainsi . Par récurrence, , et si , alors . Avec trois états, la somme a trois termes.
Exemple
Lundi (instant ), Léa prend le vélo : . Alors , puis
Mercredi, Léa prend le vélo avec la probabilité ; contrôle : .
Interpréter les puissances de la matrice
Propriété. Le coefficient de est la probabilité de passer de l'état à l'état en transitions : .
Démonstration. Partir de , c'est prendre pour la ligne qui porte en position et ailleurs. Alors est la ligne de , et son coefficient est la probabilité d'être en à l'instant : c'est .
Exemple
Pour Léa, : sa première ligne est , car Léa partait de V. Partie à vélo, elle prend le bus deux jours plus tard avec la probabilité . L'arbre retrouve ce nombre : deux chemins mènent de V à B en deux étapes, V → V → B et V → B → B.
Ainsi : un coefficient de additionne les probabilités de tous les chemins de longueur .
Distribution invariante
Une distribution est invariante (on dit aussi probabilité invariante) si : si , alors pour tout . Pour la trouver, pose (ou ), écris le système et ajoute-lui (ou ) : sans cette équation, le système a une infinité de solutions.
Exemple 1 (Léa). Le système s'écrit
et ses deux équations reviennent à . Avec : , donc , d'où et . La distribution invariante est .
Exemple 2 (Ehrenfest). Avec , le système s'écrit , et . Avec : , soit , puis . La distribution invariante est .
Comportement à long terme
Pour Léa, pose , d'où ; la relation donne
La suite est arithmético-géométrique. Comme , on obtient : la suite est géométrique de raison . Avec , . Comme , tend vers et tend vers : à long terme, Léa prend le vélo environ quatre jours sur sept. Quel que soit , tend vers la distribution invariante .
La convergence n'est pas automatique. Pour Ehrenfest, partant de , on trouve , , puis , et ainsi de suite : alterne entre deux valeurs et ne tend pas vers la distribution invariante.
Les pièges
- Ligne ou colonne. se lit sur la ligne de départ : chaque ligne, pas chaque colonne, a pour somme .
- Le sens du produit. La distribution est une ligne : on calcule , et n'est pas défini.
- Le coefficient élevé au carré. , pas : on additionne tous les chemins de longueur .
- La boucle oubliée. La probabilité de rester en va sur la diagonale de .
- L'ordre des états. Garde le même dans , dans et dans ta conclusion.
- La condition oubliée. Sans elle, la distribution invariante n'est pas déterminée.
- Invariante n'est pas limite. Pour Ehrenfest, ne converge pas vers la distribution invariante : une limite se démontre.
Ce qu'il faut retenir
- Chaîne de Markov : la probabilité de passer de à ne dépend que de et de .
- Graphe orienté pondéré : un arc de poids ; les poids sortant d'un sommet ont pour somme .
- Matrice de transition : en ligne , colonne ; chaque ligne a pour somme .
- et , où est une matrice ligne.
- est la probabilité de passer de à en transitions.
- Distribution invariante : , coefficients positifs de somme .
À l'épreuve
En contrôle continu, ce chapitre tombe en devoir surveillé sous forme d'exercice à partir d'un texte. Questions habituelles : « Représente la situation par un graphe pondéré », « Donne la matrice de transition », « Interprète le coefficient de », « Détermine la distribution invariante », « Montre que , puis étudie la limite ».
Le professeur attend l'ordre des états annoncé, les calculs de ou de posés et une conclusion rédigée dans le contexte ; les deux démonstrations du cours peuvent être demandées. On perd des points pour une ligne de somme différente de , un produit ou une limite affirmée sans preuve.