Chaînes de Markov · Terminale maths expertes

Avant de commencer5 questions pour vérifier tes bases

1. Deux issues exhaustives ont pour probabilités 0,3 et p. Que vaut p ?

0,30,71,3

2. P(B | A) désigne…

la probabilité de B sachant Ala probabilité de A sachant Btoujours P(A)P(B)

3. Avec P(A)=0,5, P(B | A)=0,8 et P(B | non A)=0,2, P(B) vaut…

0,40,51

4. Le produit d’une matrice 2 × 3 par une matrice 3 × 2 a pour format…

2 × 23 × 3Il est impossible

5. Si u₀ = 2 et uₙ₊₁ = 3uₙ, alors uₙ vaut…

2 + 3n2 × 3ⁿ3 × 2ⁿ

Pourquoi ce chapitre ?

Le problème fondamental : prévoir une évolution aléatoire

Une personne choisit entre vélo et bus. Si son choix demain dépend de celui d'aujourd'hui, les jours ne sont pas indépendants. Un arbre de probabilités permet de calculer deux jours, mais devient encombrant après vingt jours. La matrice de transition conservera toutes les branches utiles dans un tableau de taille fixe.

Prérequis. Probabilités conditionnelles, formule des probabilités totales, matrices et puissances, suites géométriques et limites. Le programme porte sur des chaînes à deux ou trois états.

Les résultats sur les probabilités de transition et les distributions invariantes sont au programme. Le modèle d'Ehrenfest final est un prolongement guidé. Aucune théorie générale des chaînes de Markov n'est supposée.

L'idée avant la formule

Une probabilité conditionnelle fixe le point de départ

« 80 pour cent des cyclistes reprennent le vélo » décrit ce qui arrive parmi les personnes à vélo aujourd'hui. Ce n'est pas encore la proportion totale de cyclistes demain. Il faut aussi compter les personnes venant du bus. La formule des probabilités totales additionne ces deux origines.

Construire le calcul sur cent personnes

Suppose 50 cyclistes et 50 usagers du bus. Si 80 pour cent des premiers restent à vélo et 30 pour cent des seconds y reviennent, l'effectif attendu à vélo demain est $50\times0{,}8+50\times0{,}3=55$ . Diviser par 100 donne la probabilité $$0{,}55$$ . Une colonne de la matrice réunira ces contributions vers le même état d'arrivée.

Un équilibre possible n'est pas une convergence prouvée

Une distribution invariante se reproduit après une transition. Mais une population partie ailleurs peut osciller : si deux états s'échangent à chaque étape, $$(1/2,1/2)$$ reste fixe tandis que $$(1,0)$$ alterne avec $$(0,1)$$ . Nous séparerons donc la recherche d'un invariant et la preuve d'une limite.

Le cours formel

États, propriété de Markov et homogénéité

Pour une histoire de probabilité non nulle se terminant en i, le modèle impose $P(X_{n+1}=j\mid X_n=i,\ldots,X_0=i_0)=p_{ij}$ . Les nombres $p_{ij}$ définissent aussi la loi de l'étape suivante si l'on décide de démarrer en i, même lorsque la distribution initiale étudiée ne donne pas de masse à cet état.

Exemple · Deux modes de déplacement

Fixons les états : $$V$$ signifie « vélo aujourd'hui » et $$B$$ « bus aujourd'hui ». Depuis $$V$$ , rester à vélo a probabilité $$0{,}8$$ ; le seul autre choix a donc probabilité $$1-0{,}8=0{,}2$$ . Depuis $$B$$ , revenir au vélo a probabilité $$0{,}3$$ ; rester au bus a probabilité $$1-0{,}3=0{,}7$$ .

Ce sont quatre probabilités conditionnelles : le départ est connu. La probabilité $$0{,}8$$ ne signifie donc pas que 80 % de toute la population utilise le vélo demain. Il faut encore connaître combien de personnes partent de chaque état.

On suppose que ces règles dépendent uniquement du mode actuel, et qu'elles sont identiques chaque jour. La première hypothèse donne la propriété de Markov ; la seconde donne l'homogénéité. Si, même à mode actuel identique, les choix dépendent encore du mode d'avant-hier, notre état ne contient pas assez d'information.

À toi d’essayer

Identifier une hypothèse de modèle

Un client choisit demain en fonction de ses deux derniers achats. Le seul dernier achat suffit-il toujours à définir un modèle de Markov ?

Pour démarrer. Compare deux historiques qui ont le même dernier achat, mais pas le même avant-dernier.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le futur doit dépendre seulement de l’état choisi.

Indice 2 · Un pas de plus

L’état peut contenir plus d’information qu’un seul achat.

Voir l’explication

Considérons les historiques $$A,A$$ et $$B,A$$ : le dernier achat est $$A$$ dans les deux cas. Si le choix de demain dépend aussi de l'avant-dernier achat, il peut avoir probabilité $$0{,}8$$ de $$A$$ dans le premier cas, $$0{,}3$$ dans le second. L'état « dernier achat $$A$$ » ne permet alors pas de fixer une seule transition. Il ne définit donc pas nécessairement un modèle de Markov. En prenant comme état le couple des deux derniers achats, on distingue ces situations ; il reste à vérifier que le passé plus ancien n'intervient plus. Agrandir l'état peut résoudre le manque d'information, mais c'est une hypothèse à examiner.

Graphe pondéré et matrice de transition

Dans l'ordre V,B,

P=\begin{pmatrix}0{,}8&0{,}2\\0{,}3&0{,}7\end{pmatrix}.

La boucle V vers V vaut 0,8 ; l'arc B vers V se lit à la deuxième ligne, première colonne. Pour chaque sommet, les probabilités des arcs sortants totalisent 1. Un arc de probabilité nulle peut être omis du dessin.

À toi d’essayer

Compléter une ligne en gardant son sens

Depuis A, on reste dans A avec probabilité 0,6 et on va vers B avec probabilité 0,1. Quelle probabilité vers C ? Que représente la somme de la colonne A ?

Pour démarrer. Écris une égalité pour la somme des trois arrivées depuis le même départ $$A$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Les trois arrivées épuisent les possibilités depuis A.

Indice 2 · Un pas de plus

Une colonne rassemble plusieurs départs conditionnels différents.

Voir l’explication

Depuis $$A$$ , les arrivées $$A,B,C$$ sont incompatibles et couvrent tous les cas : $$0{,}6+0{,}1+p=1$$ , donc $$p=0{,}3$$ . Les trois coefficients sont positifs et la ligne somme à 1. La colonne $$A$$ contient au contraire les probabilités vers $$A$$ conditionnées par trois départs différents. Les additionner sans poids n'est pas une probabilité d'arrivée de la population. Si les poids de départ sont $$u,v,w$$ , cette arrivée vaut $u p_{AA}+v p_{BA}+w p_{CA}$ . Ce sont les poids qui permettent de mélanger correctement les origines.

Distribution initiale et une transition

Démonstration · Probabilités totales

L'idée : classer les arrivées par leur origine. Pour être dans l'état $$j$$ demain, on doit être aujourd'hui dans l'un des états $1,\ldots,r$ . Ces possibilités sont incompatibles : on ne peut pas être dans deux états à la fois au même instant. Elles couvrent tous les cas, donc leurs probabilités s'additionnent.

Pour une origine $$i$$ de probabilité non nulle, la règle du produit des probabilités conditionnelles donne

\begin{aligned}P(X_n=i\text{ et }X_{n+1}=j) &= P(X_n=i)P(X_{n+1}=j\mid X_n=i)\\[.35em] &= P(X_n=i)p_{ij}.\end{aligned}

Le premier facteur est la probabilité d'être au départ $$i$$ ; le second, la probabilité du déplacement vers $$j$$ une fois ce départ connu. Si $$P(X_n=i)=0$$ , ce chemin apporte zéro, sans qu'il soit nécessaire de conditionner par un événement impossible.

En additionnant toutes les origines, $P(X_{n+1}=j)=\sum_{i=1}^rP(X_n=i)p_{ij}$ . C'est exactement le produit de la ligne $\pi_n$ par la colonne $$j$$ de $$P$$ . L'égalité vaut pour chaque arrivée $$j$$ , donc $\pi_{n+1}=\pi_nP$ .

Passer d'une étape à $$n$$ étapes. Au rang 0, $\pi_0P^0=\pi_0I=\pi_0$ . Supposons $\pi_n=\pi_0P^n$ . Alors $\pi_{n+1}=\pi_nP=(\pi_0P^n)P=\pi_0P^{n+1}$ , par associativité. L'initialisation et cette transmission prouvent $\pi_n=\pi_0P^n$ pour tout entier $n\ge0$ .

Exemple · Une population initiale

La ligne $\pi_0=(0{,}6,0{,}4)$ signifie que le départ est à vélo avec probabilité $$0{,}6$$ , en bus avec probabilité $$0{,}4$$ .

Pour arriver à vélo, les deux chemins sont $V\to V$ , de probabilité $0{,}6\times0{,}8=0{,}48$ , et $B\to V$ , de probabilité $0{,}4\times0{,}3=0{,}12$ . Leur somme vaut $$0{,}60$$ . Pour arriver au bus, les chemins donnent $0{,}6\times0{,}2=0{,}12$ et $0{,}4\times0{,}7=0{,}28$ , soit $$0{,}40$$ .

Ainsi

\begin{aligned}\pi_1 &= (0{,}6,0{,}4)\\[.35em] &= \pi_0.\end{aligned}

Les probabilités sont conservées, même si chaque individu peut changer de mode. Depuis un départ certain à vélo, $\pi_0=(1,0)$ donne au contraire $(1\times0{,}8+0\times0{,}3,1\times0{,}2+0\times0{,}7)=(0{,}8,0{,}2)$ . La distribution initiale et la matrice décrivent donc deux informations distinctes.

À toi d’essayer

Deux étapes depuis V

En partant de V avec certitude, calcule la probabilité d'être dans V après deux transitions.

Pour démarrer. Dessine les deux états possibles après le premier pas ; chaque branche doit ensuite revenir vers $$V$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Il existe deux chemins : V,V,V et V,B,V.

Indice 2 · Un pas de plus

Multiplie les probabilités le long de chaque chemin, puis additionne.

Voir l’explication

Au premier pas, soit on reste en $$V$$ , soit on va en $$B$$ . Dans le premier cas, le chemin $$V,V,V$$ a probabilité $0{,}8\times0{,}8=0{,}64$ . Dans le second, le chemin $$V,B,V$$ a probabilité $0{,}2\times0{,}3=0{,}06$ . Les deux chemins sont distincts et couvrent toutes les arrivées à vélo au temps 2, donc on additionne : $$0{,}64+0{,}06=0{,}70$$ . On retrouve la case $$(V,V)$$ de $$P^2$$ par le produit de la ligne $$(0{,}8,0{,}2)$$ et de la colonne $(0{,}8,0{,}3)^T$ . Le terme $0{,}8^2$ seul compterait uniquement ceux qui ne quittent jamais le vélo.

À toi d’essayer

Deux origines pour une même arrivée

Pour $P=\begin{pmatrix}0{,}8&0{,}2\\0{,}3&0{,}7\end{pmatrix}$ et $\pi_0=(0{,}2\,;\,0{,}8)$ , calcule la probabilité d’être dans le premier état après une étape.

Pour démarrer. Écris séparément « partir de 1 et rester en 1 » et « partir de 2 et aller en 1 ».

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Utilise les deux origines possibles, avec leurs poids initiaux.

Indice 2 · Un pas de plus

Additionne $0{,}2\times0{,}8$ et $0{,}8\times0{,}3$ .

Voir l’explication

Le premier chemin a probabilité $0{,}2\times0{,}8=0{,}16$ : $$0{,}2$$ pour partir de 1, puis $$0{,}8$$ pour y rester. Le second a probabilité $0{,}8\times0{,}3=0{,}24$ . Les origines sont incompatibles, donc on additionne : $$0{,}40$$ . La seconde coordonnée vaut

\begin{aligned}0{,}2\times0{,}2+0{,}8\times0{,}7 &= 0{,}04+0{,}56\\[.35em] &= 0{,}60.\end{aligned}

Le total vaut 1. Le coefficient $$0{,}8$$ de la matrice seul répondrait à un départ certain de 1 ; ici, ce départ n'a que probabilité $$0{,}2$$ .

Interpréter les puissances de transition

Démonstration · Une récurrence sur les trajectoires

Ce que désigne une case. Fixons un départ certain $$i$$ . Nous cherchons la probabilité d'une arrivée en $$j$$ après exactement $$n$$ déplacements, quels que soient les états intermédiaires.

Rang 0. Sans déplacement, on est encore en $$i$$ avec probabilité 1 et dans tout autre état avec probabilité 0. Ces nombres forment la ligne $$i$$ de $$I=P^0$$ .

Hypothèse. Supposons qu'après $$n$$ transitions, la probabilité d'être dans chaque état $$k$$ , depuis $$i$$ , soit $(P^n)_{ik}$ .

Dernière transition. Si l'avant-dernier état est $$k$$ , la probabilité de prolonger vers $$j$$ est $p_{kj}$ . La propriété de Markov permet de ne conserver que cet état $$k$$ ; l'homogénéité permet d'utiliser le même coefficient à chaque date. Le chemin passant par $$k$$ à cet instant a donc pour probabilité $(P^n)_{ik}p_{kj}$ . Les possibilités $$k$$ sont incompatibles et couvrent tous les cas. Leur somme est

\begin{aligned}\sum_{k=1}^r(P^n)_{ik}p_{kj} &= (P^nP)_{ij}\\[.35em] &= (P^{n+1})_{ij}.\end{aligned}

C'est la propriété au rang suivant : elle est donc démontrée par récurrence. Pour un départ aléatoire de distribution $\pi_0$ , on pondère ensuite chaque départ $$i$$ par $(\pi_0)_i$ . Cela donne $\sum_i(\pi_0)_i(P^n)_{ij}$ , la coordonnée $$j$$ de $\pi_0P^n$ .

Dans ce contrôle, $(AB)_{ij}=\sum_k a_{ik}b_{kj}$ est une somme de produits positifs ou nuls, donc reste positif ou nul. Pour la somme d'une ligne, on additionne ensuite sur $$j$$ . Les sommes sont finies : on peut les échanger et mettre $a_{ik}$ en facteur, car il ne dépend pas de $$j$$ . La parenthèse vaut 1 puisque c'est la somme de la ligne $$k$$ de $$B$$ . La somme restante vaut 1 puisque c'est la ligne $$i$$ de $$A$$ . Les deux conditions sont ainsi vérifiées, et se transmettent à toutes les puissances par récurrence.

La puissance décrit une arrivée après exactement n transitions. Elle ne donne pas directement la probabilité d'avoir visité j au moins une fois avant n : cette autre question nécessite un événement ou un modèle adapté.

À toi d’essayer

Une case, un départ et une durée

Que signifie $(P^4)_{23}=0{,}18$ dans une chaîne à trois états ? Est-ce une probabilité non conditionnée pour n’importe quel départ ?

Pour démarrer. Lis successivement l’exposant 4, l’indice de ligne 2 et l’indice de colonne 3.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

L’indice 2 fixe l’état initial.

Indice 2 · Un pas de plus

La puissance fixe le nombre exact de transitions.

Voir l’explication

L'exposant 4 fixe quatre transitions. La ligne 2 fixe le départ certain dans l'état 2 ; la colonne 3 fixe l'arrivée. La case signifie donc : depuis 2, la probabilité d'être en 3 après quatre pas est $$0{,}18$$ . Pour un départ $$(u,v,w)$$ , l'arrivée en 3 vaut $u(P^4)_{13}+v(P^4)_{23}+w(P^4)_{33}$ . Le nombre $$0{,}18$$ est seulement le deuxième terme avant pondération ; il ne donne pas le résultat pour toute distribution initiale. Il autorise aussi des visites intermédiaires à 3 suivies de départs et de retours.

Distributions invariantes et limites

Méthode · Résoudre le système

Pour deux états, écris $\pi=(x,1-x)$ : la somme vaut déjà 1. Avec le modèle vélo/bus, la première coordonnée de $\pi P=\pi$ impose $$0{,}8x+0{,}3(1-x)=x$$ . Développer donne $$0{,}5x+0{,}3=x$$ , donc $$0{,}3=0{,}5x$$ et $$x=0{,}6$$ . La seconde coordonnée vaut $$1-0{,}6=0{,}4$$ .

Vérifions aussi la seconde équation :

\begin{aligned}0{,}2\times0{,}6+0{,}7\times0{,}4 &= 0{,}12+0{,}28\\[.35em] &= 0{,}4.\end{aligned}

Les deux coefficients sont positifs, de somme 1. L'unique candidat convient donc.

Pour trois états, écris $$(u,v,w)$$ , calcule les trois colonnes du produit, puis ajoute $$u+v+w=1$$ . Si deux équations de transition disent la même chose, ce n'est pas une erreur : la normalisation est indispensable pour déterminer l'échelle. Une ligne solution du seul système homogène n'est pas automatiquement une distribution.

Supposons que chaque coordonnée de $\pi_n$ converge vers la coordonnée correspondante de $\ell$ . Une limite de nombres positifs ou nuls reste positive ou nulle. La somme comporte seulement deux ou trois termes ; sa limite est donc la somme des limites, égale à 1. Ainsi $\ell$ est une distribution.

Pour chaque arrivée $$j$$ , l'égalité d'évolution s'écrit $(\pi_{n+1})_j=\sum_i(\pi_n)_ip_{ij}$ . À gauche, décaler le rang de 1 ne change pas la limite, qui vaut $\ell_j$ . À droite, les $p_{ij}$ sont constants et la somme est finie ; sa limite vaut $\sum_i\ell_ip_{ij}$ . Donc $\ell_j=(\ell P)_j$ pour chaque $$j$$ , d'où $\ell=\ell P$ .

Nous sommes partis de l'hypothèse de convergence : cette preuve donne une propriété de la limite si elle existe. Elle ne démontre pas cette existence. Les exemples périodiques ci-dessous montrent pourquoi l'implication ne peut pas être retournée.

À toi d’essayer

Normaliser une solution de l’équation

Pour une matrice stochastique, une ligne non nulle L vérifie LP=L. Est-elle forcément une distribution ?

Pour démarrer. Essaie de multiplier une distribution invariante par 2 et vérifie les deux conditions.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Deux conditions concernent les coefficients eux-mêmes.

Indice 2 · Un pas de plus

L’équation homogène admet aussi des multiples de solutions.

Voir l’explication

Si $\pi P=\pi$ , alors

\begin{aligned}(2\pi)P &= 2(\pi P)\\[.35em] &= 2\pi.\end{aligned}

La ligne $2\pi$ satisfait donc la même équation, mais sa somme vaut 2 : ce n'est pas une distribution. L'équation $$LP=L$$ doit être accompagnée de coefficients positifs ou nuls et d'une somme 1. Si les coefficients de $$L$$ sont tous positifs ou nuls et leur somme $$s>0$$ , on peut diviser par $$s$$ ; alors $$(L/s)P=L/s$$ et la somme devient 1. Si $$L$$ contient à la fois des coefficients positifs et négatifs, cette division positive ne supprime pas les signes négatifs. L'équation seule ne suffit donc pas.

Chaîne à deux états : étude complète

Démonstration · Réduire à une suite géométrique

1. Obtenir la récurrence. La probabilité d'arriver dans le premier état vaut « départ du premier et maintien » plus « départ du second et retour ». Ainsi

\begin{aligned}x_{n+1} &= x_n(1-a)+(1-x_n)b\\[.35em] &= x_n-ax_n+b-bx_n\\[.35em] &= (1-a-b)x_n+b.\end{aligned}

La probabilité de l'autre état est $1-x_{n+1}$ , car les deux arrivées épuisent les possibilités.

2. Trouver la valeur qui ne bouge pas. Posons $$x=(1-a-b)x+b$$ . En soustrayant $$(1-a-b)x$$ , il vient $$(a+b)x=b$$ . Lorsque $$a+b>0$$ , on peut diviser et obtenir l'unique $$x_*=b/(a+b)$$ . L'autre coordonnée vaut $$1-b/(a+b)=a/(a+b)$$ . Ces deux nombres sont positifs ou nuls et leur somme vaut 1 : ils définissent bien une distribution.

3. Mesurer l'écart à cette valeur. Écrivons aussi $$x_*=(1-a-b)x_*+b$$ . Soustraire cette égalité de la récurrence annule les deux termes $$b$$ :

\begin{aligned}x_{n+1}-x_* &= (1-a-b)x_n-(1-a-b)x_*\\[.35em] &= (1-a-b)(x_n-x_*).\end{aligned}

Avec $$y_n=x_n-x_*$$ et $$q=1-a-b$$ , on a $y_{n+1}=qy_n$ . Donc $$y_1=qy_0$$ , $$y_2=q^2y_0$$ . Au rang 0, $$y_0=q^0y_0$$ ; si $$y_n=q^ny_0$$ , alors $y_{n+1}=q^{n+1}y_0$ . La récurrence donne $$y_n=q^ny_0$$ à tous les rangs.

4. Revenir à la probabilité. Rajoutons $$x_*$$ : $$x_n=x_*+q^n(x_0-x_*)$$ . On retrouve la formule annoncée. Si $$q=0$$ , on lit séparément le rang initial $$x_0$$ et les rangs $n\ge1$ , où $$x_n=x_*$$ ; aucune ambiguïté sur $$0^0$$ n'est nécessaire.

Exemple · Retour au vélo et au bus

Les probabilités de changer d'état sont $$a=0{,}2$$ et $$b=0{,}3$$ . Leur somme vaut $$0{,}5$$ , donc

\begin{aligned}x_* &= 0{,}3/0{,}5\\[.35em] &= 0{,}6\end{aligned}

\begin{aligned}\text{et }q &= 1-0{,}2-0{,}3\\[.35em] &= 0{,}5.\end{aligned}

Depuis $$V$$ avec certitude, $$x_0=1$$ et l'écart initial est $$1-0{,}6=0{,}4$$ . Ainsi $x_n=0{,}6+0{,}4(0{,}5)^n$ .

Le facteur géométrique tend vers zéro, donc la limite est $$0{,}6$$ . Pour rendre l'écart au plus égal à $$0{,}01$$ , on résout $0{,}4/2^n\le0{,}01$ . Multiplier par $$2^n>0$$ , puis diviser par $$0{,}01>0$$ , donne $2^n\ge40$ . Comme $$2^5=32<40$$ et $2^6=64\ge40$ , le premier rang est 6. L'écart y vaut $$0{,}4/64=0{,}00625$$ ; au rang 5, il vaut $$0{,}0125$$ , encore trop grand. Les puissances $$2^n$$ augmentent, donc tous les rangs suivants conviennent.

Justifions les cas limites annoncés. Si $$0<a+b<2$$ , soustraire à 1 donne $$-1<1-a-b<1$$ . Les puissances de ce nombre tendent vers zéro, donc l'écart explicite tend vers zéro. Si $$a+b=0$$ , la positivité impose

\begin{aligned}a &= b\\[.35em] &= 0\end{aligned}

$$P=I$$ et $\pi_n=\pi_0$ pour tout $$n$$ . Si $$a+b=2$$ , les bornes $a\le1$ , $b\le1$ imposent

\begin{aligned}a &= b\\[.35em] &= 1\end{aligned}

$x_{n+1}=1-x_n$ , donc $x_{2k}=x_0$ et $x_{2k+1}=1-x_0$ . Ces deux valeurs sont égales seulement si $$x_0=1/2$$ . Sinon deux sous-suites constantes ont des limites différentes, ce qui interdit une limite commune.

Si le coefficient $$1-a-b$$ est négatif, l'écart change de signe : on approche l'équilibre en alternant de part et d'autre. S'il est positif, on s'en approche du même côté. Si la distribution initiale est déjà invariante, l'écart est nul dès le départ.

À toi d’essayer

Une limite trompeuse

Pour $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ , trouve la distribution invariante et étudie le départ $$(1,0)$$ .

Pour démarrer. Multiplie une ligne $$(x,1-x)$$ par la matrice, puis recommence avec $$(1,0)$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La matrice échange les deux coordonnées.

Indice 2 · Un pas de plus

Compare les temps pairs et impairs.

Voir l’explication

Le produit vaut $$(1-x,x)$$ : la matrice échange les deux coordonnées. Pour être invariant, il faut $$x=1-x$$ , donc $$2x=1$$ et $$x=1/2$$ . La distribution $$(1/2,1/2)$$ est l'unique invariant. Mais depuis $$(1,0)$$ , les étapes donnent $$(0,1)$$ , puis $$(1,0)$$ , puis $$(0,1)$$ , sans diminution de l'écart. Les rangs pairs restent $$(1,0)$$ et les rangs impairs $$(0,1)$$ ; ces deux sous-suites ne peuvent avoir une même limite. L'existence d'un départ stable ne rend donc pas tous les départs convergents.

À toi d’essayer

Relier le signe de la raison au comportement

Dans la formule du cours, prends a=0,8 et b=0,5. Trouve le point fixe et décris les écarts successifs.

Pour démarrer. Calcule séparément la valeur fixe et le nombre qui multiplie l’écart.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

La raison vaut 1 moins a moins b.

Indice 2 · Un pas de plus

Le point fixe de la première coordonnée est $$b/(a+b)$$ .

Voir l’explication

La somme $$a+b$$ vaut $$1{,}3$$ . Le point fixe est $$0{,}5/1{,}3=5/13$$ . La raison vaut $$1-0{,}8-0{,}5=-0{,}3$$ . Avec $$e_0=x_0-5/13$$ , la formule donne $x_n-5/13=(-0{,}3)^ne_0$ . Les premiers écarts sont $$e_0$$ , $-0{,}3e_0$ , $0{,}09e_0$ , $-0{,}027e_0$ . Si $e_0\ne0$ , leurs signes alternent et leurs modules sont multipliés par $$0{,}3<1$$ , donc tendent vers zéro. Si $$e_0=0$$ , tous les écarts restent nuls. Dans tous les cas la première probabilité tend vers $$5/13$$ .

Trois états : calcul, normalisation et exemple convergent

Exemple · Une transition et une distribution invariante

Prenons $P=\begin{pmatrix}1/2&1/2&0\\1/4&1/2&1/4\\0&1/2&1/2\end{pmatrix}$ . Les lignes totalisent $$1/2+1/2=1$$ , $$1/4+1/2+1/4=1$$ et $$1/2+1/2=1$$ , avec des coefficients positifs ou nuls.

Depuis $$(1,0,0)$$ , la première étape sélectionne la première ligne : $$(1/2,1/2,0)$$ . La deuxième donne

\begin{aligned}u_2 &= (1/2)(1/2)+(1/2)(1/4)\\[.35em] &= 1/4+1/8\\[.35em] &= 3/8,\end{aligned}

\begin{aligned}v_2 &= (1/2)(1/2)+(1/2)(1/2)\\[.35em] &= 1/2\end{aligned}

\begin{aligned}\text{et }w_2 &= (1/2)0+(1/2)(1/4)\\[.35em] &= 1/8.\end{aligned}

La somme vaut bien 1.

Pour l'invariance, les trois équations sont $$u=u/2+v/4$$ , $$v=u/2+v/2+w/2$$ , $$w=v/4+w/2$$ . La première donne $$u/2=v/4$$ , donc $$u=v/2$$ . La troisième donne de même $$w=v/2$$ . La normalisation devient $$v/2+v+v/2=1$$ , donc $$2v=1$$ et $$v=1/2$$ ; d'où

\begin{aligned}u &= w\\[.35em] &= 1/4.\end{aligned}

La deuxième équation est bien satisfaite : $$1/8+1/4+1/8=1/2$$ . Les première et troisième le sont par construction, et les trois nombres sont positifs de somme 1. Il existe donc une distribution invariante, $$(1/4,1/2,1/4)$$ ; la résolution montre qu'aucune autre n'est possible.

Pour étudier les distributions successives, le produit par $$P$$ donne $u_{n+1}=u_n/2+v_n/4$ ,

\begin{aligned}v_{n+1} &= (u_n+v_n+w_n)/2\\[.35em] &= 1/2\end{aligned}

et $w_{n+1}=v_n/4+w_n/2$ . Le total $$u_n+v_n+w_n$$ vaut 1 à chaque rang.

Posons $$s_n=u_n+w_n$$ . En additionnant les première et troisième formules,

\begin{aligned}s_{n+1} &= (u_n+w_n)/2+v_n/2\\[.35em] &= 1/2.\end{aligned}

Posons $$d_n=u_n-w_n$$ . En les soustrayant, les deux termes $$v_n/4$$ s'annulent :

\begin{aligned}d_{n+1} &= (u_n-w_n)/2\\[.35em] &= d_n/2.\end{aligned}

La suite $$d$$ est géométrique de raison $$1/2$$ , donc $$d_n=(u_0-w_0)/2^n$$ .

Pour $n\ge1$ , on connaît $$s_n=1/2$$ et $$d_n$$ . Leur somme vaut $$2u_n$$ , leur différence vaut $$2w_n$$ . En divisant par deux,

\begin{aligned}u_n &=\frac14+\frac{u_0-w_0}{2^{n+1}},\\v_n &=\frac12,\\w_n &=\frac14-\frac{u_0-w_0}{2^{n+1}}.\end{aligned}

La restriction $n\ge1$ est essentielle : $$v_0$$ n'est pas forcément $$1/2$$ . Comme $$u_0-w_0$$ est fixé et $2^{-(n+1)}\to0$ , les trois coordonnées convergent vers $$(1/4,1/2,1/4)$$ . C'est cette étude de l'écart qui prouve la convergence pour toute distribution initiale.

Exemple · Une autre puissance d'ordre 3

La matrice $$E$$ a tous ses coefficients égaux à $$1/3$$ . Dans son carré, chaque coefficient vaut

\begin{aligned}(1/3)(1/3)+(1/3)(1/3)+(1/3)(1/3) &= 3/9\\[.35em] &= 1/3.\end{aligned}

Donc $$E^2=E$$ .

Posons $$H=I-E$$ . Alors

\begin{aligned}EH &= E-E^2\\[.35em] &= 0,\end{aligned}

\begin{aligned}HE &= E-E^2\\[.35em] &= 0,\end{aligned}

\begin{aligned}\text{et }H^2 &= I-2E+E^2\\[.35em] &= I-E\\[.35em] &= H.\end{aligned}

La matrice $Q=\lambda I+(1-\lambda)E$ s'écrit $E+\lambda H$ .

Au rang 0,

\begin{aligned}E+H &= I\\[.35em] &= Q^0.\end{aligned}

Si $Q^n=E+\lambda^nH$ , multiplier par $$Q$$ donne $E^2+\lambda EH+\lambda^nHE+\lambda^{n+1}H^2=E+\lambda^{n+1}H$ . La formule est donc prouvée par récurrence. Pour $\lambda=0$ , on écrit séparément $$Q^0=I$$ et $$Q^n=E$$ pour $n\ge1$ .

Pour une distribution $\pi_0=(u,v,w)$ , chaque coordonnée de $\pi_0E$ est $$(u+v+w)/3=1/3$$ . Donc, avec $$e=(1/3,1/3,1/3)$$ , $\pi_0Q^n=e+\lambda^n(\pi_0-e)$ . Si $0<\lambda<1$ , la puissance tend vers zéro, donc la limite est $$e$$ . Si $\lambda=0$ , on atteint déjà $$e$$ après une étape. Cette formule démontre la convergence au lieu de la déduire du seul calcul de l'invariant.

À toi d’essayer

Une invariant unique ne suffit toujours pas

Dans un cycle déterministe à trois états, explique pourquoi la distribution uniforme est invariante et pourquoi un départ certain ne converge pas.

Pour démarrer. Écris trois étapes depuis $$(1,0,0)$$ et compare avec le départ uniforme.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le produit fait tourner les trois coordonnées.

Indice 2 · Un pas de plus

Compare les rangs de restes 0,1 et 2 modulo 3.

Voir l’explication

Le cycle déplace la masse du premier état vers le deuxième, du deuxième vers le troisième et du troisième vers le premier. La ligne uniforme $$(1/3,1/3,1/3)$$ est inchangée, car permuter trois coordonnées égales ne modifie rien. Plus généralement, l'invariance impose les trois coordonnées égales, donc cet invariant est unique. Depuis $$(1,0,0)$$ , les lignes deviennent $$(0,1,0)$$ , puis $$(0,0,1)$$ , puis $$(1,0,0)$$ . Aux rangs multiples de 3, la première coordonnée vaut 1 ; aux rangs suivants, elle vaut 0. Deux sous-suites ont des limites différentes : la suite entière ne converge pas, malgré l'unicité de l'invariant.

Simulation et calcul exact : deux usages distincts

Le produit $\pi_0P^n$ calcule une distribution théorique. Une simulation produit une trajectoire particulière. Les fréquences observées fluctuent ; elles ne sont pas une preuve de convergence générale.

def transition_distribution(pi, P):
    r = len(pi)
    return [sum(pi[i]*P[i][j] for i in range(r))
            for j in range(r)]

from random import random

def etape(etat, P):
    u = random()
    cumul = 0.0
    for j, proba in enumerate(P[etat]):
        cumul += proba
        if u < cumul:
            return j
    return len(P[etat]) - 1

Dans la première fonction, $$j$$ désigne l'état d'arrivée. La somme parcourt chaque départ $$i$$ , multiplie son poids initial pi[i] par sa transition P[i][j], puis additionne ces contributions. La liste finale contient une valeur par arrivée : c'est le produit $\pi P$ .

La seconde fonction simule un état, pas une distribution. Le nombre u est tiré uniformément dans $$[0,1[$$ . Pour une ligne $$(0{,}2,0{,}3,0{,}5)$$ , les cumuls deviennent $$0{,}2$$ , puis $$0{,}5$$ , puis 1. Si $$u<0{,}2$$ , on renvoie l'état 0 ; si $0{,}2\le u<0{,}5$ , l'état 1 ; sinon l'état 2. Les longueurs de ces intervalles sont précisément $$0{,}2$$ , $$0{,}3$$ , $$0{,}5$$ , donc les probabilités demandées. La boucle effectue automatiquement cette partition pour la ligne de l'état actuel.

Ces fonctions supposent une matrice de transition valide et des indices cohérents. La seconde partage l'intervalle $$[0,1[$$ selon les probabilités de la ligne de départ ; la dernière ligne protège contre un léger écart d'arrondi dans la somme. Avant une simulation, vérifie les coefficients et les sommes de lignes.

Boîte à outils : modéliser et interpréter

Ce que décrit une distribution de population

Exemple · Relier probabilités et effectifs attendus

La proportion initiale de vélos est $x_0=0{,}9$ . Dans la formule du modèle, l'écart initial vaut $$0{,}9-0{,}6=0{,}3$$ . Ainsi $x_n=0{,}6+0{,}3(0{,}5)^n$ et

\begin{aligned}x_2 &= 0{,}6+0{,}3\times0{,}25\\[.35em] &= 0{,}675.\end{aligned}

Pour 1 000 personnes, notons $$I_k$$ le nombre qui vaut 1 si la personne $$k$$ utilise un vélo, 0 sinon. Le nombre total de vélos est $N=I_1+\cdots+I_{1000}$ . L'espérance d'un indicateur vaut sa probabilité :

\begin{aligned}E(I_k) &= 1P(I_k=1)+0P(I_k=0)\\[.35em] &= P(I_k=1).\end{aligned}

L'addition des espérances donne donc

\begin{aligned}E(N) &= 1000\times0{,}675\\[.35em] &= 675,\end{aligned}

lorsque la proportion moyenne du modèle vaut $$0{,}675$$ .

Cette valeur est une moyenne théorique, pas une promesse sur chaque observation. Additionner les espérances ne nécessite pas l'indépendance des personnes. Une loi binomiale pour l'effectif demanderait, elle, des hypothèses supplémentaires ; nous n'en avons pas besoin ici.

Changer l'ordre des états sans changer le modèle

Pour la même chaîne, la convention V,B donne $P=\begin{pmatrix}0{,}8&0{,}2\\0{,}3&0{,}7\end{pmatrix}$ . La convention B,V donne $Q=\begin{pmatrix}0{,}7&0{,}3\\0{,}2&0{,}8\end{pmatrix}$ . Il faut échanger à la fois les lignes, les colonnes et les coordonnées de la distribution initiale.

Par exemple, $(0{,}9\,;\,0{,}1)$ dans l'ordre V,B devient $(0{,}1\,;\,0{,}9)$ dans l'ordre B,V. Après une étape, les deux descriptions donnent respectivement $(0{,}75\,;\,0{,}25)$ et $(0{,}25\,;\,0{,}75)$ . Les nombres sont les mêmes, affectés aux états dans un autre ordre. Échanger seulement les lignes produirait un modèle différent.

Temps d'attente avant une première sortie

Exemple · Rester plusieurs jours dans le même état

Depuis $$V$$ , rester à vélo pendant les $$n$$ transitions signifie suivre uniquement le chemin $V,V,\ldots,V$ . La probabilité de chaque maintien, sachant les maintiens précédents, vaut $$0{,}8$$ par la propriété de Markov. La règle du produit donne $$n$$ facteurs, soit $0{,}8^n$ . Pour $$n=0$$ , il n'y a aucune contrainte future : la probabilité vaut 1.

Une première sortie exactement à la transition $k\ge1$ impose $$k-1$$ maintiens, puis un passage vers $$B$$ : sa probabilité est $0{,}8^{k-1}\times0{,}2$ . Par exemple, au troisième pas, le chemin est $$V,V,V,B$$ et la probabilité $0{,}8\times0{,}8\times0{,}2=0{,}128$ .

« Au moins une sortie avant ou au temps $$n$$ » est le contraire de « aucun passage par $$B$$ pendant ces $$n$$ pas ». Sa probabilité est donc $1-0{,}8^n$ . En revanche, $x_n=0{,}6+0{,}4(0{,}5)^n$ mesure seulement la présence à vélo au dernier instant : elle autorise une sortie suivie d'un retour. Il faut lire la question avant de choisir la formule.

Tester la plausibilité d'un modèle homogène

Un modèle avec les mêmes probabilités chaque jour peut être cohérent pour une période donnée. Si les transitions diffèrent systématiquement entre semaine et week-end, il faut soit utiliser des matrices dépendant du jour, soit élargir la description des états. Dans le premier cas, la distribution après deux étapes s'écrit $\pi_0P_0P_1$ , et pas nécessairement $\pi_0P^2$ . L'hypothèse d'homogénéité explique précisément quand une seule puissance suffit.

À toi d’essayer

Lire une autre convention

Dans l'ordre B,V, quelle est la distribution invariante du modèle vélo/bus ?

Pour démarrer. Associe d’abord chaque probabilité au nom de son état, puis écris-les dans le nouvel ordre.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le modèle n'a pas changé, seul l'ordre change.

Indice 2 · Un pas de plus

Échange les coordonnées de $(0{,}6\,;\,0{,}4)$ donné dans l'ordre V,B.

Voir l’explication

L'invariant attribue probabilité $$0{,}6$$ au vélo et $$0{,}4$$ au bus. Dans l'ordre $$B,V$$ , il s'écrit donc $$(0{,}4,0{,}6)$$ . La matrice dans cet ordre est $Q=\begin{pmatrix}0{,}7&0{,}3\\0{,}2&0{,}8\end{pmatrix}$ . Le produit donne

\begin{aligned}0{,}4\times0{,}7+0{,}6\times0{,}2 &= 0{,}28+0{,}12\\[.35em] &= 0{,}4\end{aligned}

pour le bus, puis

\begin{aligned}0{,}4\times0{,}3+0{,}6\times0{,}8 &= 0{,}12+0{,}48\\[.35em] &= 0{,}6\end{aligned}

pour le vélo. La ligne est bien conservée. Changer l'ordre exige de permuter ensemble les lignes, les colonnes et les coordonnées.

À toi d’essayer

Une première sortie

Depuis V, calcule la probabilité de prendre le bus pour la première fois à la troisième transition.

Pour démarrer. Écris les états aux temps 0, 1, 2 et 3 en interdisant toute sortie avant le dernier.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Les deux premières transitions doivent conserver V.

Indice 2 · Un pas de plus

Le dernier facteur est la probabilité de sortir de V.

Voir l’explication

Le départ est $$V$$ . Une première sortie au troisième pas impose encore $$V$$ aux temps 1 et 2, puis $$B$$ au temps 3. Le seul chemin est $$V,V,V,B$$ . Les deux maintiens ont probabilité conditionnelle $$0{,}8$$ , et la sortie $$0{,}2$$ . Le produit vaut

\begin{aligned}0{,}8\times0{,}8\times0{,}2 &= 0{,}64\times0{,}2\\[.35em] &= 0{,}128.\end{aligned}

Une simple arrivée en $$B$$ au temps 3 compterait aussi, par exemple, $$V,B,B,B$$ , qui est exclu ici puisque la première sortie y a déjà lieu au temps 1.

Exercices progressifs

Les exercices 1 à 5 consolident les bases, 6 à 10 relient les notions et 11 à 15 demandent davantage d'initiative. Cherche d'abord, puis utilise un indice si tu en as besoin.

Exercice 1 : Matrice valide ★☆☆

Les matrices $\begin{pmatrix}0,7&0,3\\0,2&0,8\end{pmatrix}$ et $\begin{pmatrix}1,2&-0,2\\0,4&0,6\end{pmatrix}$ sont-elles des matrices de transition ?

Exercice 2 : Du texte au tableau ★☆☆

Un client fidèle le reste avec probabilité 0,9. Un client occasionnel devient fidèle avec probabilité 0,4. Écris P dans l’ordre F,O.

Exercice 3 : Une transition ★☆☆

Avec la matrice de l’exercice 2 et $\pi_0=(0{,}5\,;\,0{,}5)$ , calcule $\pi_1$ .

Exercice 4 : Départ certain ★☆☆

Avec P de l’exercice 2, donne la distribution après une étape depuis O avec certitude.

Exercice 5 : Compléter trois transitions ★☆☆

Une ligne de transition vers A,B,C vaut $(0{,}2\,;\,p\,;\,0{,}5)$ . Détermine p et vérifie les conditions.

Exercice 6 : Deux étapes ★★☆

Pour $P=\begin{pmatrix}0,8&0,2\\0,3&0,7\end{pmatrix}$ , calcule $P^{2}$ et interprète son coefficient (1,2).

Exercice 7 : Distribution invariante ★★☆

Trouve la distribution invariante de la matrice de l’exercice 2.

Exercice 8 : Formule explicite ★★☆

Pour P de l’exercice 2 et un départ certain dans O, exprime la probabilité $x_{n}$ d’être fidèle au temps n.

Exercice 9 : Un seuil de proximité ★★☆

Dans l’exercice 8, à partir de quel n a-t-on $|x_n-0,8|\le0,025$ ?

Exercice 10 : Alternance autour de l’équilibre ★★☆

Pour $P=\begin{pmatrix}0,1&0,9\\0,6&0,4\end{pmatrix}$ et $$x_0=1$$ , exprime $x_{n}$ et décris son comportement.

Exercice 11 : État absorbant ★★★

Étudie $P=\begin{pmatrix}1&0\\0,2&0,8\end{pmatrix}$ depuis le second état. Donne la limite.

Exercice 12 : Invariant sans convergence ★★★

Pour $P=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}$ , trouve la distribution invariante et étudie le départ $$(1,0,0)$$ .

Exercice 13 : Trois états symétriques ★★★

Pour $Q=\begin{pmatrix}1/2&1/4&1/4\\1/4&1/2&1/4\\1/4&1/4&1/2\end{pmatrix}$ et $\pi_0=(1,0,0)$ , calcule $\pi_n$ à l’aide de E, dont tous les coefficients valent 1/3.

Exercice 14 : Arrivée ou visite ★★★

Pour P de l’exercice 6 en partant de l’état 1, compare la probabilité d’être en 2 après deux étapes à celle d’avoir visité 2 au moins une fois pendant ces deux étapes.

Exercice 15 : Une limite doit être invariante ★★★

Suppose qu’une suite $\pi_n=\pi_0P^n$ converge vers une ligne L. Prouve que L est une distribution invariante. Explique ce que cette preuve ne garantit pas.

Problème : Pour aller plus loin

Ce prolongement est accessible à partir du cours : les résultats supplémentaires sont guidés, et leur mémorisation n'est pas un préalable. Tu peux répartir la recherche sur plusieurs séances.

Deux particules et un équilibre qui peut osciller

Deux particules sont réparties entre une boîte gauche et une boîte droite. À chaque étape, on choisit l'une des deux particules au hasard, de manière équiprobable, et on la change de boîte. L'état est le nombre de particules dans la boîte gauche, parmi 0,1,2. Durée indicative : 90 minutes.

Partie I : Construire le modèle

Décris les transitions depuis chacun des trois états. Écris la matrice P dans l'ordre 0,1,2 et le graphe pondéré.
Calcule $P^{2}$ et la distribution après deux étapes depuis l'état 0.
Trouve l'unique distribution invariante.

Partie II : Comprendre la périodicité

En partant de l'état 0, donne les distributions aux temps impairs puis aux temps pairs strictement positifs.
La distribution converge-t-elle ? Pourquoi cela ne contredit-il pas l'existence d'un invariant ?

Partie III : Introduire une pause aléatoire

Désormais, à chaque étape, on ne fait rien avec probabilité 1/2 ; sinon on effectue le déplacement précédent. La matrice devient $$Q=(I+P)/2$$ .

Écris Q. Vérifie que la distribution invariante précédente l'est encore pour Q.
Si $\pi_n=(u_n,v_n,w_n)$ , pose $$s_n=u_n+w_n$$ et $$d_n=u_n-w_n$$ . Montre $s_{n+1}=1/2$ et $d_{n+1}=d_n/2$ .
Déduis les trois coordonnées pour $n\ge1$ , puis leur limite pour toute distribution initiale.
Depuis l'état 0, à partir de quel rang chacune des trois coordonnées diffère-t-elle de celle de l'invariant d'au plus 1/64 ?

Pistes

Depuis l'état 1, les deux particules ne se trouvent pas dans la même boîte. La parité du nombre à gauche change à chaque déplacement. Pour Q, la pause permet aussi de conserver la parité.

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Démonstration · Solution expliquée

Chaque case de $$P^2$$ additionne les deux états intermédiaires possibles. On obtient

\begin{aligned}(P^2)_{11} &= 0{,}8\times0{,}8+0{,}2\times0{,}3\\[.35em]&= 0{,}64+0{,}06\\[.35em]&= 0{,}70,\\[.35em](P^2)_{12} &= 0{,}8\times0{,}2+0{,}2\times0{,}7\\[.35em]&= 0{,}16+0{,}14\\[.35em]&= 0{,}30,\\[.35em](P^2)_{21} &= 0{,}3\times0{,}8+0{,}7\times0{,}3\\[.35em]&= 0{,}24+0{,}21\\[.35em]&= 0{,}45,\\[.35em](P^2)_{22} &= 0{,}3\times0{,}2+0{,}7\times0{,}7\\[.35em]&= 0{,}06+0{,}49\\[.35em]&= 0{,}55.\end{aligned}

Donc $P^2=\begin{pmatrix}0{,}70&0{,}30\\0{,}45&0{,}55\end{pmatrix}$ , dont les lignes totalisent bien 1. La case $$(1,2)$$ décrit une arrivée en 2 après exactement deux pas depuis 1. Les chemins sont $$1,1,2$$ et $$1,2,2$$ . Le chemin $$1,2,1$$ visite 2 mais n'y termine pas : il n'est pas compté ici.

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Démonstration · Solution expliquée

Dans $Q=\lambda I+(1-\lambda)E$ , une case hors diagonale vaut $(1-\lambda)/3$ . On impose $(1-\lambda)/3=1/4$ , donc $1-\lambda=3/4$ et $\lambda=1/4$ . Une case diagonale vaut alors $$1/4+1/4=1/2$$ , comme dans l'énoncé.

Le cours a démontré, à partir de $$E^2=E$$ , que $Q^n=E+4^{-n}(I-E)$ . Le produit $\pi_0E$ vaut $$(1/3,1/3,1/3)$$ , car $\pi_0=(1,0,0)$ sélectionne la première ligne. La différence $\pi_0-\pi_0E$ vaut $$(2/3,-1/3,-1/3)$$ . Ainsi

\begin{aligned}&\pi_n\\&= \left(\frac13+\frac23\,4^{-n},\ \frac13-\frac13\,4^{-n},\ \frac13-\frac13\,4^{-n}\right).\end{aligned}

Au rang 0, cela donne $$(1,0,0)$$ ; au rang 1, $$(1/2,1/4,1/4)$$ . La somme vaut $1+(2/3-1/3-1/3)4^{-n}=1$ . La puissance tend vers zéro : la limite est donc la distribution uniforme.

Corrigé 14

Corrigé 15

Démonstration · Solution expliquée

Notons $L=(\ell_1,\ldots,\ell_r)$ . Chaque $(\pi_n)_j$ est positif ou nul ; sa limite $\ell_j$ l'est donc aussi. La somme $\sum_j(\pi_n)_j=1$ comporte un nombre fini de termes, donc on peut prendre la limite terme à terme : $\sum_j\ell_j=1$ . La ligne $$L$$ est bien une distribution.

Pour chaque $$j$$ , $(\pi_{n+1})_j=\sum_i(\pi_n)_ip_{ij}$ . La limite du membre gauche est $\ell_j$ , car décaler une suite convergente d'un rang ne change pas sa limite. Dans le membre droit, les $p_{ij}$ sont constants et la somme est finie : la limite vaut $\sum_i\ell_ip_{ij}$ . Donc $\ell_j=(LP)_j$ pour chaque $$j$$ , soit $$L=LP$$ .

La preuve suppose la convergence au départ : elle ne peut pas servir à la prouver. Le cycle à trois états a un invariant unique mais certains départs ne convergent pas. Avec $$P=I$$ , toutes les distributions sont invariantes, donc il n'y a pas unicité. Ces deux exemples distinguent les conclusions qui ont été démontrées de celles qui ne l'ont pas été.

Corrigé du problème

Partie I : Traduire chaque déplacement

1. L'état compte les particules à gauche. Depuis 0, les deux sont à droite : quelle que soit celle choisie, une passe à gauche, donc on arrive en 1 avec probabilité 1. Depuis 2, les deux sont à gauche : en déplacer une laisse exactement une particule à gauche, donc on arrive aussi en 1 avec probabilité 1.

Depuis 1, il y a une particule de chaque côté. Choisir celle de gauche, de probabilité $$1/2$$ , la fait partir et donne l'état 0. Choisir celle de droite, de probabilité $$1/2$$ , la fait entrer et donne l'état 2. On ne peut pas rester en 1. Dans l'ordre $$0,1,2$$ ,

P=\begin{pmatrix}0&1&0\\1/2&0&1/2\\0&1&0\end{pmatrix}.

Le graphe a les arcs $0\to1$ et $2\to1$ de poids 1, ainsi que $1\to0$ et $1\to2$ de poids $$1/2$$ . Aucun autre arc n'est nécessaire. Chaque ligne somme à 1.

2. La première ligne de $$P$$ est $$(0,1,0)$$ : son produit par $$P$$ sélectionne la deuxième ligne, $$(1/2,0,1/2)$$ . Pour la deuxième ligne, les trois produits sont $$(1/2)0+0(1/2)+(1/2)0=0$$ , $(1/2)1+0\times0+(1/2)1=1$ , et $$(1/2)0+0(1/2)+(1/2)0=0$$ . La troisième ligne est identique à la première. Donc

P^2=\begin{pmatrix}1/2&0&1/2\\0&1&0\\1/2&0&1/2\end{pmatrix}.

Depuis l'état 0, $\pi_0=(1,0,0)$ ; après deux pas, on lit la première ligne de $$P^2$$ , soit $$(1/2,0,1/2)$$ . Les chemins $$0,1,0$$ et $$0,1,2$$ ont chacun probabilité $1\times1/2$ .

3. Pour $\pi=(u,v,w)$ , le produit est $\pi P=(v/2,u+w,v/2)$ . L'invariance impose $$u=v/2$$ , $$v=u+w$$ , $$w=v/2$$ . Remplaçons $$u,w$$ dans la somme 1 :

\begin{aligned}v/2+v+v/2 &= 2v\\[.35em] &= 1.\end{aligned}

Donc $$v=1/2$$ et

\begin{aligned}u &= w\\[.35em] &= 1/4.\end{aligned}

La deuxième équation est vérifiée, car

\begin{aligned}u+w &= 1/4+1/4\\[.35em] &= 1/2\\[.35em] &= v.\end{aligned}

Les coefficients sont positifs de somme 1. Le candidat $\pi_*=(1/4,1/2,1/4)$ est donc un invariant, et les équations imposent ces valeurs de façon unique.

Partie II : Expliquer pourquoi l'équilibre n'est pas atteint

1. Depuis 0, $\pi_1=(0,1,0)$ et $\pi_2=(1/2,0,1/2)$ . Multiplier cette dernière ligne par $$P$$ donne $$(0,1/2+1/2,0)=(0,1,0)$$ . Puis multiplier $$(0,1,0)$$ redonne $$(1/2,0,1/2)$$ . Les deux lignes s'échangent donc à chaque pas. Par récurrence, $\pi_{2k+1}=(0,1,0)$ pour $k\ge0$ , et $\pi_{2k}=(1/2,0,1/2)$ pour $k\ge1$ . Le rang 0 est exclu de la seconde formule car $\pi_0=(1,0,0)$ .

2. La probabilité de l'état 1 vaut 1 aux rangs impairs et 0 aux rangs pairs. Les deux sous-suites constantes ont des limites différentes, donc la suite ne converge pas. Cela ne contredit pas $\pi_*P=\pi_*$ : cette égalité garantit la stabilité si l'on démarre en $\pi_*$ . Ici, le départ certain $$(1,0,0)$$ est différent. À chaque déplacement, le nombre à gauche change de 1 ; sa parité alterne obligatoirement, ce qui explique le phénomène.

Partie III : Calculer l'effet de la pause

1. Avec probabilité $$1/2$$ , on reste dans le même état : cela correspond à $$I/2$$ . Avec probabilité $$1/2$$ , on suit les transitions de $$P$$ : cela correspond à $$P/2$$ . On additionne les deux possibilités, donc

Q=\frac{I+P}{2}=\begin{pmatrix}1/2&1/2&0\\1/4&1/2&1/4\\0&1/2&1/2\end{pmatrix}.

Les probabilités diagonales viennent de la pause. L'invariant précédent vérifie

\begin{aligned}\pi_*Q &= (\pi_*I+\pi_*P)/2\\[.35em] &= (\pi_*+\pi_*)/2\\[.35em] &= \pi_*.\end{aligned}

Cette égalité utilise la distributivité du produit et l'invariance déjà prouvée pour $$P$$ .

2. Le produit $\pi_{n+1}=\pi_nQ$ donne

\begin{aligned}u_{n+1} &=\frac{u_n}{2}+\frac{v_n}{4},\\v_{n+1} &= \frac{u_n+v_n+w_n}{2}\\&= \frac12,\\w_{n+1} &=\frac{v_n}{4}+\frac{w_n}{2}.\end{aligned}

Pour $$s_n=u_n+w_n$$ , on additionne les première et troisième relations :

\begin{aligned}s_{n+1} &= u_n/2+v_n/2+w_n/2\\[.35em] &= 1/2,\end{aligned}

car la distribution somme à 1. Pour $$d_n=u_n-w_n$$ , on les soustrait : les deux termes $$v_n/4$$ se compensent et

\begin{aligned}d_{n+1} &= (u_n-w_n)/2\\[.35em] &= d_n/2.\end{aligned}

3. La suite $$d$$ est géométrique, de raison $$1/2$$ et de premier terme $$d_0=u_0-w_0$$ . Donc $$d_n=(u_0-w_0)/2^n$$ . Pour $n\ge1$ , $$s_n=1/2$$ et $$v_n=1/2$$ . En additionnant $$s_n=u_n+w_n$$ et $$d_n=u_n-w_n$$ , on obtient $$2u_n=s_n+d_n$$ ; en les soustrayant, $$2w_n=s_n-d_n$$ . Ainsi

\begin{aligned}u_n &=\frac14+\frac{u_0-w_0}{2^{n+1}},\\v_n &=\frac12,\\w_n &=\frac14-\frac{u_0-w_0}{2^{n+1}}.\end{aligned}

La valeur initiale $$u_0-w_0$$ est fixe ; la puissance $2^{-(n+1)}$ tend vers zéro. Donc les trois coordonnées tendent respectivement vers $$1/4,1/2,1/4$$ , pour toute distribution initiale. Nous avons démontré la convergence par des écarts explicites.

4. Depuis 0, $$u_0=1$$ ,

\begin{aligned}v_0 &= w_0\\[.35em] &= 0,\end{aligned}

donc $$u_0-w_0=1$$ . Pour $n\ge1$ , les écarts absolus sont $2^{-(n+1)}$ , 0 et $2^{-(n+1)}$ . Les trois sont au plus $1/64=2^{-6}$ exactement lorsque $n+1\ge6$ , c'est-à-dire $n\ge5$ .

Au rang 5, la distribution est $$(17/64,1/2,15/64)$$ : les deux écarts extrêmes valent bien $$1/64$$ . Au rang 4, ils valent $$1/32$$ , trop grand. Le rang 0 ne convient pas non plus, puisque son écart sur la première coordonnée vaut $$3/4$$ . Le premier rang est donc 5, et tous les suivants conviennent. Dans ce modèle, les pauses ont permis aux deux parités de se mélanger ; les formules quantifient cet effet.

Faire le point par une variante autonome

Essaie cette variante sans relire le corrigé précédent. Explique le choix de ta méthode, puis utilise les contrôles pour décider quelle notion retravailler.

À toi d’essayer

Un modèle à deux états de A à Z

Pour $P=\begin{pmatrix}0{,}7&0{,}3\\0{,}2&0{,}8\end{pmatrix}$ , pars du premier état. Donne la récurrence de sa probabilité, l’invariant et la limite.

Pour démarrer. Écris $x_{n+1}$ en distinguant maintien dans le premier état et retour depuis le second.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Pose la distribution au rang n égale à $$(x_n,1-x_n)$$ .

Indice 2 · Un pas de plus

La récurrence est $x_{n+1}=0{,}5x_n+0{,}2$ .

Voir l’explication

Les lignes totalisent $$0{,}7+0{,}3=1$$ et $$0{,}2+0{,}8=1$$ , donc $$P$$ est valide. Depuis le premier état certain, $$x_0=1$$ . Les probabilités totales donnent

\begin{aligned}x_{n+1} &= 0{,}7x_n+0{,}2(1-x_n)\\[.35em] &= 0{,}5x_n+0{,}2.\end{aligned}

Le point fixe satisfait $$x=0{,}5x+0{,}2$$ , donc $$0{,}5x=0{,}2$$ et $$x=0{,}4$$ . Soustraire cette valeur donne $x_{n+1}-0{,}4=0{,}5(x_n-0{,}4)$ ; l'écart initial étant $$0{,}6$$ , $x_n=0{,}4+0{,}6(0{,}5)^n$ . Au rang 1, on retrouve $$0{,}7$$ . La puissance tend vers zéro, donc la distribution tend vers $$(0{,}4,0{,}6)$$ . Enfin

\begin{aligned}(0{,}4,0{,}6)P &= (0{,}28+0{,}12,0{,}12+0{,}48)\\[.35em] &= (0{,}4,0{,}6)\end{aligned}

la limite calculée est bien invariante.

Fiche-mémoire

P est stochastique par lignes : coefficients positifs ou nuls, chaque somme de ligne égale à 1.
Convention du cours : distributions en ligne ; $\pi_{n+1}=\pi_nP$ et $\pi_n=\pi_0P^n$ .
$(P^n)_{ij}$ décrit une arrivée en j après n transitions depuis i.
Invariant : $\pi P=\pi$ avec normalisation et positivité.
Deux états : $x_{n+1}=(1-a-b)x_n+b$ ; si $$0<a+b<2$$ , convergence vers $$b/(a+b)$$ .
Une limite éventuelle est invariante ; un invariant ne garantit pas une limite.

Contrôle. Ai-je fixé l'ordre des états ? Multiplié du bon côté ? Distingué visite et arrivée ? Vérifié chaque somme ? Démontré la convergence dans le modèle étudié ?

Maîtrise du chapitre

Validation contrôlée

Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.

Avant le cours, vérifie tes bases

Pourquoi ce chapitre ?

Le problème fondamental : prévoir une évolution aléatoire

L'idée avant la formule

Une probabilité conditionnelle fixe le point de départ

Construire le calcul sur cent personnes

Un équilibre possible n'est pas une convergence prouvée

Le cours formel

États, propriété de Markov et homogénéité

Graphe pondéré et matrice de transition

Distribution initiale et une transition

Interpréter les puissances de transition

Distributions invariantes et limites

Chaîne à deux états : étude complète

Trois états : calcul, normalisation et exemple convergent

Simulation et calcul exact : deux usages distincts

Boîte à outils : modéliser et interpréter

Ce que décrit une distribution de population

Changer l'ordre des états sans changer le modèle

Temps d'attente avant une première sortie

Tester la plausibilité d'un modèle homogène

Exercices progressifs

Exercice 1 : Matrice valide ★☆☆

Exercice 2 : Du texte au tableau ★☆☆

Exercice 3 : Une transition ★☆☆

Exercice 4 : Départ certain ★☆☆

Exercice 5 : Compléter trois transitions ★☆☆

Exercice 6 : Deux étapes ★★☆

Exercice 7 : Distribution invariante ★★☆

Exercice 8 : Formule explicite ★★☆

Exercice 9 : Un seuil de proximité ★★☆

Exercice 10 : Alternance autour de l’équilibre ★★☆

Exercice 11 : État absorbant ★★★

Exercice 12 : Invariant sans convergence ★★★

Exercice 13 : Trois états symétriques ★★★

Exercice 14 : Arrivée ou visite ★★★

Exercice 15 : Une limite doit être invariante ★★★

Problème : Pour aller plus loin

Deux particules et un équilibre qui peut osciller

Partie I : Construire le modèle

Partie II : Comprendre la périodicité

Partie III : Introduire une pause aléatoire

Pistes

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Corrigé du problème

Partie I : Traduire chaque déplacement

Partie II : Expliquer pourquoi l'équilibre n'est pas atteint

Partie III : Calculer l'effet de la pause

Faire le point par une variante autonome

Fiche-mémoire

Maîtrise du chapitre

Pour relier les notions