Matrices, graphes et processus d'évolution : cours de maths · Terminale expertes

Compter des parcours avec une matrice

Fixer l'ordre des sommets. Dans la matrice d'adjacence $A=(a_{i,j})$ d'un graphe orienté, $a_{i,j}$ compte les arcs du sommet $i$ vers le sommet $j$ : départ en ligne, arrivée en colonne. Sans arcs multiples, les coefficients valent $0$ ou $1$ ; les boucles sont sur la diagonale.

Pour un graphe non orienté sans boucle, la matrice est symétrique et sa diagonale nulle.

Un chemin de longueur $n$ parcourt $n$ arcs dans leur sens ; sommets et arcs peuvent être répétés. Pour $n\geq1$, $(A^n)_{i,j}$ compte les chemins de longueur $n$ de $i$ à $j$. En non orienté, la même lecture compte les chaînes.

M=\begin{pmatrix}0&1&1\\1&0&1\\1&0&0\end{pmatrix}\qquad\text{dans l'ordre }A,B,C.

Chaque flèche correspond à un coefficient égal à $1$. L'ordre des sommets est le même pour les lignes et les colonnes.

Ici, $(M^3)_{A,C}=2$ : les deux chemins sont $A\to B\to A\to C$ et $A\to C\to A\to C$.

Comprendre pourquoi — Pourquoi A puissance n compte les chemins

À la longueur $1$, les coefficients comptent les arcs. Pour passer de $n$ à $n+1$, classer les chemins selon leur unique avant-dernier sommet $k$ donne $\sum_k(A^n)_{ik}a_{kj}=(A^{n+1})_{ij}$. Les groupes disjoints couvrent tous les chemins : le produit ligne-colonne établit la récurrence. Répétitions autorisées ; sans orientation, on compte les chaînes.

Chaînes de Markov et distributions

Une chaîne de Markov à deux ou trois états évolue par transitions aux instants entiers. Connaissant l'état présent, les probabilités du prochain état ne dépendent pas des états passés. On les suppose ici constantes au cours du temps.

Dans un ordre fixé des états, la matrice $P=(p_{i,j})$ donne la probabilité de passer de $i$ à $j$ en une transition. Chaque coefficient est dans $[0;1]$, chaque ligne somme à $1$.

Le graphe probabiliste a un sommet par état et un arc pour chaque transition de probabilité non nulle, pondéré par cette probabilité. Une boucle signifie rester dans le même état ; les poids sortant de chaque sommet somment à 1.

La distribution $\pi_n$ est la matrice ligne des probabilités après $n$ transitions, dans le même ordre. Ses coefficients sont positifs ou nuls et somment à $1$ ; $\pi_0$ est la distribution initiale. Une ligne $(1,0,0)$ représente un départ certain dans le premier état.

Calculer après plusieurs transitions

Pour $n\geq1$, $(P^n)_{i,j}$ est la probabilité d'arriver en $j$ après $n$ transitions en partant de $i$. Pour toute distribution initiale et $n\geq0$ :

\pi_{n+1}=\pi_nP,\qquad\pi_n=\pi_0P^n,\qquad P^0=I.

La distribution est une ligne : multiplier par P à droite. Elle décrit des probabilités, pas un trajet certain.

Comprendre pourquoi — Pourquoi P puissance n donne les probabilités

Pour une chaîne à deux ou trois états, soit $P$ la matrice de transition constante. Noter $q^{(n)}_{ij}$ la probabilité d'arriver en $j$ après $n$ transitions en partant de $i$. Pour $n=1$, $q^{(1)}_{ij}=p_{ij}$.

Pour passer de $n$ à $n+1$, distinguer l'état intermédiaire $k$. Les probabilités totales et la propriété de Markov donnent :

q^{(n+1)}_{ij}=\sum_k q^{(n)}_{ik}p_{kj}.

Si $q^{(n)}_{ik}=(P^n)_{ik}$, cette somme est $(P^{n+1})_{ij}$ par le produit ligne-colonne. La récurrence conclut pour tout $n\geq1$. Un état intermédiaire impossible contribue zéro ; aucun conditionnement sur cet événement n'est nécessaire.

Distribution invariante

Une distribution invariante est une ligne $\pi$ à coefficients positifs ou nuls, de somme $1$, vérifiant $\pi P=\pi$.

Pour la trouver, résoudre simultanément $\pi P=\pi$ et la condition de somme $1$, puis vérifier la positivité des coefficients. Si $\pi_0=\pi$, alors $\pi_n=\pi$ pour tout $n\geq0$. Les probabilités restent les mêmes, même si les états changent.

L'invariance ne garantit pas que les distributions issues d'un autre départ convergent vers elle.

Comprendre pourquoi — Une distribution invariante sans convergence

Pour $R=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, $\pi=(\frac12,\frac12)$ est une distribution et $\pi R=\pi$. Mais $(x,y)R=(y,x)$. Depuis $(1,0)$, $\pi_{2k}=(1,0)$ et $\pi_{2k+1}=(0,1)$ pour $k\ge0$. Le premier coefficient a des sous-suites de limites différentes : il ne converge pas, malgré l’existence d’une distribution invariante.

Un exemple à trois états

Q=\begin{pmatrix}\frac{1}{2}&\frac{1}{2}&0\\0&\frac{1}{2}&\frac{1}{2}\\\frac{1}{4}&0&\frac{3}{4}\end{pmatrix}\qquad\text{dans l'ordre }A,B,C.

Les boucles représentent le maintien dans un état. Les trois autres arcs forment le cycle $A\to B\to C\to A$.

Les lignes somment à $1$. Avec $\pi_0=(1,0,0)$ :

\pi_1=\left(\frac{1}{2},\frac{1}{2},0\right),\qquad\pi_2=\left(\frac{1}{4},\frac{1}{2},\frac{1}{4}\right).

Pour une distribution invariante $\pi=(x,y,z)$, $\pi Q=\pi$ donne $y=x$ et $z=2x$. Avec $x+y+z=1$, on obtient :

\pi=\left(\frac{1}{4},\frac{1}{4},\frac{1}{2}\right).

Ses coefficients sont positifs, leur somme vaut $1$, et le produit $\pi Q=\pi$ vérifie l'invariance.