Graphes probabilistes et chaînes de Markov

Situation. Chaque jour de classe, Inès vient au lycée à vélo ou en bus. Si elle est venue à vélo un jour, elle reprend le vélo le lendemain avec la probabilité $0,75$ ; si elle est venue en bus, elle prend le vélo le lendemain avec la probabilité $0,35$. Le jour $0$, elle vient en bus. On note $V_n$ l’événement « Inès vient à vélo le jour $n$ », $B_n$ son contraire et $v_n=p(V_n)$ ; ainsi $v_0=0$.

Premiers termes. Le jour $0$, Inès est en bus, donc $v_1=p_{B_0}(V_1)=0,35$. Avec l’arbre entre le jour $1$ et le jour $2$ : $v_2=0,35\times 0,75+0,65\times 0,35$ $=0,2625+0,2275$ $=0,49$.

Relation de récurrence. $V_n$ et $B_n$ forment une partition ; d’après la formule des probabilités totales, $v_{n+1}=p(V_n)p_{V_n}(V_{n+1})+p(B_n)p_{B_n}(V_{n+1})$ $=0,75v_n+0,35(1-v_n)$, soit $v_{n+1}=0,4v_n+0,35$. Contrôle : $0,4\times 0,35+0,35=0,49$, c’est bien $v_2$.

Forme explicite. $\ell =0,4\ell +0,35$ $⟺0,6\ell$ $=0,35⟺\ell$ $={\displaystyle \frac{7}{12}}$. La suite $(v_n-{\displaystyle \frac{7}{12}})$ est géométrique de raison $0,4$ et de premier terme $-{\displaystyle \frac{7}{12}}$, donc $v_n={\displaystyle \frac{7}{12}}(1-0,4^n)$. Comme $-1<0,4<1$, $lim{v}_n={\displaystyle \frac{7}{12}}\approx 0,583$ : à long terme, la probabilité qu’Inès vienne à vélo un jour donné se rapproche de ${\displaystyle \frac{7}{12}}$.

Deux états. Hugo tire des lancers francs. On admet que la réussite d’un lancer ne dépend que du lancer précédent : après un lancer réussi ($R$), il réussit le suivant avec la probabilité $0,85$ ; après un lancer raté ($E$), avec la probabilité $0,55$.

Dans l’ordre $(R;E)$ : $P=\left(\begin{array}{cc}0,85& 0,15\\ 0,55& 0,45\end{array}\right)$. La boucle en $E$ porte $0,45$, le complément à $1$ de $0,55$. Lecture : $p_{21}=0,55$ est la probabilité de passer de $E$ à $R$, c’est-à-dire de réussir un lancer juste après un échec.

Trois états, avec des zéros. Un robot aspirateur change de pièce chaque minute entre la cuisine $C$, le salon $S$ et le bureau $B$, selon le graphe ci-dessous.

Dans l’ordre $(C;S;B)$ : $P=\left(\begin{array}{ccc}0,5& 0,5& 0\\ 0,3& 0,2& 0,5\\ 0& 0,6& 0,4\end{array}\right)$. Il n’y a pas d’arc entre $C$ et $B$ : $p_{13}=p_{31}=0$. Chaque ligne somme à $1$ : $0,5+0,5+0=1$, $0,3+0,2+0,5=1$ et $0+0,6+0,4=1$. Les colonnes n’ont aucune raison de sommer à $1$ : la première donne $0,5+0,3+0=0,8$.

Pourquoi ${\pi }_{n+1}={\pi }_{n}P$ (trois états). Les événements $(X_n=1)$, $(X_n=2)$ et $(X_n=3)$ forment une partition. D’après la formule des probabilités totales, pour chaque état $j$ : $p(X_{n+1}=j)=p(X_n=1)p_{1j}$ $+p(X_n=2)p_{2j}$ $+p(X_n=3)p_{3j}$ (un terme où $p(X_n=i)=0$ est simplement nul). C’est le produit de la ligne ${\pi }_n$ par la colonne $j$ de $P$, donc le coefficient $j$ de ${\pi }_{n}P$.

Démonstration du théorème 1. Pour tout $n\in \mathbb{N}$, on note $𝒫(n)$ : « ${\pi }_n={\pi }_0{P}^n$ ». Initialisation : $P^0=I$ et ${\pi }_{0}I={\pi }_0$, donc $𝒫(0)$ est vraie. Hérédité : si ${\pi }_k={\pi }_0{P}^k$ pour un entier $k$, alors ${\pi }_{k+1}={\pi }_{k}P$ $=({\pi }_0{P}^k)P$ $={\pi }_0{P}^{k+1}$ par associativité du produit matriciel. Conclusion : par récurrence, ${\pi }_n={\pi }_0{P}^n$ pour tout $n\in \mathbb{N}$.

Démonstration du théorème 2. Supposons que la chaîne parte de l’état $i$ : la distribution initiale ${\pi }_0$ a un $1$ en position $i$ et des $0$ ailleurs. Le produit ${\pi }_0{P}^n$ est alors la ligne $i$ de $P^n$. D’après le théorème 1, c’est ${\pi }_n$ : son coefficient $j$ est la probabilité d’être en $j$ à l’étape $n$ sachant le départ en $i$, soit $(P^n{)}_{ij}=p_{(X_0=i)}(X_n=j)$. Comme ${\pi }_n$ est une distribution, chaque ligne de $P^n$ somme à $1$.

Calcul. Avec la matrice des lancers de Hugo, $P=\left(\begin{array}{cc}0,85& 0,15\\ 0,55& 0,45\end{array}\right)$, et un premier lancer réussi, ${\pi }_0=\left(\begin{array}{cc}1& 0\end{array}\right)$ : ${\pi }_1=\left(\begin{array}{cc}0,85& 0,15\end{array}\right)$, puis ${\pi }_2={\pi }_{1}P$, de premier coefficient $0,85\times 0,85+0,15\times 0,55$ $=0,7225+0,0825$ $=0,805$ : ${\pi }_2=\left(\begin{array}{cc}0,805& 0,195\end{array}\right)$.

$P^2=\left(\begin{array}{cc}0,805& 0,195\\ 0,715& 0,285\end{array}\right)$ : sa première ligne redonne ${\pi }_2$ (départ en $R$). Son coefficient $(2;1)$, $0,55\times 0,85+0,45\times 0,55$ $=0,4675+0,2475$ $=0,715$, est la probabilité de réussir un lancer sachant que le lancer tiré deux coups plus tôt a été raté.

Démonstration (deux états). On pose $\pi =\left(\begin{array}{cc}x& 1-x\end{array}\right)$, ce qui intègre la condition de somme. Le premier coefficient de $\pi P$ vaut $(1-a)x+b(1-x)$. L’égalité $\pi P=\pi$ équivaut à $(1-a)x+b(1-x)=x$, soit $b=(a+b)x$ (le second coefficient donne la même équation, car les deux coefficients de $\pi P$ somment à $1$). Comme $a+b>0$ : $x={\displaystyle \frac{b}{a+b}}$ et $1-x={\displaystyle \frac{a}{a+b}}$.

Lancers de Hugo. $a=0,15$ et $b=0,55$, donc $a+b=0,7$ et $\pi =\left(\begin{array}{cc}{\displaystyle \frac{11}{14}}& {\displaystyle \frac{3}{14}}\end{array}\right)$ $\approx \left(\begin{array}{cc}0,786& 0,214\end{array}\right)$. Vérification : ${\displaystyle \frac{11}{14}}\times 0,85+{\displaystyle \frac{3}{14}}\times 0,55$ $={\displaystyle \frac{9,35+1,65}{14}}$ $={\displaystyle \frac{11}{14}}$.

Robot aspirateur (trois états). Avec $P=\left(\begin{array}{ccc}0,5& 0,5& 0\\ 0,3& 0,2& 0,5\\ 0& 0,6& 0,4\end{array}\right)$ et $\pi =\left(\begin{array}{ccc}x& y& z\end{array}\right)$, la première équation s’écrit $0,5x+0,3y=x$, donc $x=0,6y$ ; la troisième s’écrit $0,5y+0,4z=z$, donc $z={\displaystyle \frac{5}{6}}y$. Avec $x+y+z=1$ : $(0,6+1+{\displaystyle \frac{5}{6}})y$ $={\displaystyle \frac{73}{30}}y$ $=1$, d’où $y={\displaystyle \frac{30}{73}}$, $x={\displaystyle \frac{18}{73}}$ et $z={\displaystyle \frac{25}{73}}$. Vérification sur la deuxième équation, non utilisée : $0,5\times {\displaystyle \frac{18}{73}}+0,2\times {\displaystyle \frac{30}{73}}+0,6\times {\displaystyle \frac{25}{73}}$ $={\displaystyle \frac{9+6+15}{73}}$ $={\displaystyle \frac{30}{73}}$, c’est bien $y$.

Lancers de Hugo. $a=0,15$ et $b=0,55$, donc $x_{n+1}=0,3x_n+0,55$, de point fixe $\ell ={\displaystyle \frac{0,55}{0,7}}$ $={\displaystyle \frac{11}{14}}$. Premier lancer réussi : $x_0=1$ et $x_0-\ell ={\displaystyle \frac{3}{14}}$, d’où $x_n={\displaystyle \frac{11}{14}}+{\displaystyle \frac{3}{14}}\times 0,3^n$. Contrôle : $x_2={\displaystyle \frac{11}{14}}+{\displaystyle \frac{3}{14}}\times 0,09$ $={\displaystyle \frac{11,27}{14}}$ $=0,805$. Comme $-1<0,3<1$, $lim{x}_n={\displaystyle \frac{11}{14}}$ : $({\pi }_n)$ converge vers $\left(\begin{array}{cc}{\displaystyle \frac{11}{14}}& {\displaystyle \frac{3}{14}}\end{array}\right)$ et les deux lignes de $P^n$ tendent vers cette distribution. Au bout de nombreux lancers, l’issue du premier n’a plus d’influence.

Seuil. Premier rang $n$ tel que $x_n<0,79$ : ${\displaystyle \frac{3}{14}}\times 0,3^n$ $<0,79-{\displaystyle \frac{11}{14}}$ $={\displaystyle \frac{0,06}{14}}$, soit $0,3^n<0,02$. Or $0,3^3=0,027$ et $0,3^4=0,0081$ ; comme la suite $(0,3^n)$ est décroissante, le premier rang est $n=4$. Le programme ci-dessous donne le même résultat :

def seuil(s):
    n = 0
    x = 1
    while x >= s:
        x = 0.3 * x + 0.55
        n = n + 1
    return n

L’appel seuil(0.79) renvoie $4$.

Sans convergence. Avec $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ et ${\pi }_0=\left(\begin{array}{cc}0,2& 0,8\end{array}\right)$ : ${\pi }_1=\left(\begin{array}{cc}0,8& 0,2\end{array}\right)$, ${\pi }_2={\pi }_0$, et ainsi de suite. La distribution $\left(\begin{array}{cc}0,5& 0,5\end{array}\right)$ est invariante, mais $({\pi }_n)$ ne converge pas.