Matrice stochastique

En mathématiques, une matrice stochastique (aussi appelée matrice de Markov) est une matrice carrée (finie ou infinie) dont chaque élément est un réel positif et dont la somme des éléments de chaque ligne vaut 1. Cela correspond, en théorie des probabilités, à la matrice de transition d'une chaîne de Markov.

Définitions

Une matrice ${\displaystyle M\in {\mathcal {M}}_{n}(\mathbb {R} )}$ est dite stochastique si toutes ses entrées sont positives (ou nulles) et si, pour tout ${\displaystyle i=1,...,n}$, on a ${\displaystyle \sum _{j=1}^{n}m_{ij}=1}$, c'est-à-dire que la somme des coordonnées de chaque ligne vaut 1[1].

Une matrice stochastique est dite régulière s'il existe un entier ${\displaystyle k>0}$ tel que la matrice ${\displaystyle M^{k}}$ ne contient que des réels strictement positifs.

Une matrice est dite bistochastique (ou doublement stochastique) si la somme des éléments de chaque ligne et de chaque colonne vaut 1, autrement si ${\displaystyle M}$ et sa transposée ${\displaystyle M^{t}}$ sont stochastiques.

Propriétés

Une autre caractérisation des matrices stochastiques est donnée par :

• ${\displaystyle M}$ est une matrice stochastique si et seulement si ${\displaystyle M\geq 0}$ (ses coefficients sont positifs ou nuls) et ${\displaystyle Me=e}$, où ${\displaystyle e}$ désigne le vecteur de ${\displaystyle \mathbb {R} ^{n}}$ dont toutes les coordonnées valent 1.
• ${\displaystyle M}$ est bistochastique si ${\displaystyle M\geq 0}$, ${\displaystyle Me=e}$ et ${\displaystyle e^{*}M=e^{*}}$, où ${\displaystyle e^{*}}$ est le vecteur transposé de ${\displaystyle e}$.

D'après la propriété précédente, puisque 1 est une valeur propre de ${\displaystyle M}$ avec comme vecteur propre à droite le vecteur colonne dont toutes les coordonnées valent 1 :

• Si ${\displaystyle M}$ est une matrice stochastique, on appelle vecteur stable pour ${\displaystyle M}$ un vecteur ligne non nul ${\displaystyle v}$ tel que ${\displaystyle vM=v}$ , autrement dit : un vecteur propre à gauche pour la valeur propre 1 (et ${\displaystyle M}$ possède toujours au moins un vecteur stable).

Une caractérisation du rayon spectral d'une matrice stochastique est donnée par :

• Si ${\displaystyle M}$ est une matrice stochastique, alors ${\displaystyle ||Mx||_{\infty }\leq ||x||_{\infty }}$ pour tout ${\displaystyle x\in \mathbb {C} ^{n}}$, de sorte que le rayon spectral ${\displaystyle \rho (M)\leq 1}$. Or, comme ${\displaystyle Me=e}$, on a en fait ${\displaystyle \rho (M)=1}$. Ainsi, le rayon spectral d'une matrice stochastique vaut précisément 1.

D'autres résultats sont donnés par :

• Le produit de deux matrices stochastiques est stochastique.
• Toute matrice stochastique indexée par E×E opère sur l'espace des applications bornées de E dans ${\displaystyle \mathbb {R} }$ .
• Si ${\displaystyle M}$ est une matrice stochastique et si ${\displaystyle p}$ est une probabilité alors ${\displaystyle pM}$ est une probabilité.

Exemple

La matrice suivante est stochastique mais pas bistochastique :

${\displaystyle M={\begin{pmatrix}0{,}5&0{,}3&0{,}2\\0{,}2&0{,}8&0\\0{,}3&0{,}3&0{,}4\end{pmatrix}}.}$

Le vecteur ${\displaystyle {\begin{pmatrix}3&6&1\end{pmatrix}}}$ est stable pour M.

La matrice stochastique M est régulière car

${\displaystyle M^{2}={\begin{pmatrix}0{,}37&0{,}45&0{,}18\\0{,}26&0{,}70&0{,}04\\0{,}33&0{,}45&0{,}22\end{pmatrix}}.}$

Théorème des matrices stochastiques

Le théorème des matrices stochastiques stipule que, si A est une matrice stochastique régulière, alors

• la chaîne de Markov de matrice de transition A est irréductible ;
• A possède un unique vecteur stable t dont la somme des coordonnées vaut 1 (autrement dit : le sous-espace vectoriel des vecteurs stables est de dimension 1 — les vecteurs stables sont tous colinéaires) ;
• les coordonnées de t sont toutes strictement positives.

De plus, si x₀ est une loi initiale quelconque (i.e. est un vecteur à coordonnées positives ou nulles et de somme 1), et si x_k+1 = x_kA pour k = 0, 1, 2, … alors la chaîne de Markov {x_k} converge vers t quand ${\displaystyle k\to \infty }$. C’est-à-dire :

${\displaystyle \lim _{k\to \infty }\mathbf {x} _{0}A^{k}={\textbf {t}}.}$

Quelques autres résultats

Le rôle des matrices stochastiques est important, notamment dans l'étude des chaînes de Markov. Une caractéristique importante des matrices doublement stochastiques (ou bistochastiques) est fourni par les matrices de permutation ${\displaystyle P(\sigma )}$, ${\displaystyle \sigma \in {\mathcal {S}}^{n}}$, dont les coefficients valent ${\displaystyle p_{ij}=\delta _{\sigma (i)}^{j}}$, avec ${\displaystyle \delta }$ le symbole de Kronecker.

Le théorème de Birkhoff montre ce rôle central qu'ont les matrices de permutations dans la caractérisation des matrices bistochastiques :

Théorème de Birkhoff — Une matrice ${\displaystyle M\in {\mathcal {M}}_{n}(\mathbb {R} )}$ est doublement stochastique si et seulement si elle est barycentre de matrices de permutations.

Une conséquence de théorème est donnée par le résultat suivant[2] :

Corollaire — Soit ${\displaystyle ||.||}$ une norme sur ${\displaystyle \mathbb {R} ^{n}}$, invariante par permutation des coordonnées. Alors ${\displaystyle ||M||=1}$ pour toute matrice doublement stochastique.

Deux autres résultats sur les matrices bistochastiques utilisent la relation décrite par le symbole ${\displaystyle \prec }$, défini par : Soient ${\displaystyle a=(a_{1},...,a_{n})}$ et ${\displaystyle b=(b_{1},...,b_{n})}$ deux suites de ${\displaystyle n}$ nombres réels. On dit que b majore a, et on note ${\displaystyle a\prec b}$ si :

• ${\displaystyle a_{1}+...+a_{k}\leq b_{1}+...+b_{k}}$ pour tout ${\displaystyle k=1,...,n-1}$ ;
• ${\displaystyle a_{1}+...+a_{n}=b_{1}+...+b_{n}}$.

Il s'agit d'une relation d'ordre partielle.

Les deux théorèmes sont :

Théorème — Une matrice ${\displaystyle M}$ est doublement stochastique si et seulement si ${\displaystyle x\prec Mx}$ pour tout ${\displaystyle x\in \mathbb {R} ^{n}}$.

Théorème — Soient ${\displaystyle x,y\in \mathbb {R} ^{n}}$. ALors ${\displaystyle x\prec y}$ si et seulement s'il existe une matrice ${\displaystyle M}$, doublement stochastique, telle que ${\displaystyle y=Mx}$.

Voir aussi

Bibliographie

Denis Serre, Les Matrices : Théorie et pratique, Paris, Dunod, 2001, 176 p. (ISBN 2-10-005515-1).

Sur l'application des matrices de transition de Markov en musicologie[3],[4]

Notes et références

1. Certains auteurs parlent de matrice stochastique à droite, la transposée d'une telle matrice (dont la somme des coordonnées de chaque colonne vaut 1) est alors dite stochastique à gauche.
2. (en) F. L. Bauer, J. Stoer et C. Witzgall, « Absolute and monotonic norms », Numerische Mathematik, vol. 3, n^o 1,‎ décembre 1961, p. 257–264 (ISSN 0029-599X et 0945-3245, DOI 10.1007/bf01386026, lire en ligne, consulté le 2 février 2020)
3. Acuma, « Algorithmic Composition: Markov Chains in PureData » (consulté le 3 juillet 2024)
4. « Un algorithme de composition musicale » [PDF]

Articles connexes

• Matrice bistochastique
• Chaîne de Markov
• Matrice