Matrice stochastique - Stochastic matrix

En mathématiques, une matrice stochastique est une matrice carrée utilisée pour décrire les transitions d'une chaîne de Markov . Chacune de ses entrées est un nombre réel non négatif représentant une probabilité . Il est aussi appelé une matrice de probabilité , la matrice de transition , la matrice de substitution , ou matrice de Markov . La matrice stochastique a été développée pour la première fois par Andrey Markov au début du XXe siècle et a été utilisée dans une grande variété de domaines scientifiques, notamment la théorie des probabilités , les statistiques, la finance mathématique et l'algèbre linéaire , ainsi que l' informatique et la génétique des populations . Il existe plusieurs définitions et types de matrices stochastiques :

Une matrice stochastique droite est une vraie matrice carrée, avec chaque ligne sommant à 1.

Une matrice stochastique gauche est une vraie matrice carrée, avec chaque colonne sommant à 1.

Une matrice doublement stochastique est une matrice carrée de nombres réels non négatifs avec chaque ligne et colonne sommant à 1.

Dans le même ordre d'idées, on peut définir un vecteur stochastique (appelé aussi vecteur de probabilité ) comme un vecteur dont les éléments sont des nombres réels non négatifs dont la somme est égale à 1. Ainsi, chaque ligne d'une matrice stochastique droite (ou colonne d'une matrice stochastique gauche) est un vecteur stochastique. Une convention courante dans la littérature mathématique de langue anglaise consiste à utiliser des vecteurs lignes de probabilités et des matrices stochastiques droites plutôt que des vecteurs colonnes de probabilités et des matrices stochastiques gauches ; cet article suit cette convention.

Histoire

Andreï Markov en 1886

La matrice stochastique a été développée parallèlement à la chaîne de Markov par Andrey Markov , un mathématicien russe et professeur à l' Université de Saint-Pétersbourg qui a publié pour la première fois sur le sujet en 1906. Ses utilisations initiales étaient l'analyse linguistique et d'autres sujets mathématiques comme le brassage de cartes , mais les deux Les chaînes et matrices de Markov ont rapidement trouvé une utilisation dans d'autres domaines.

Les matrices stochastiques ont été développées plus avant par des chercheurs comme Andrey Kolmogorov , qui ont élargi leurs possibilités en permettant des processus de Markov en temps continu. Dans les années 1950, des articles utilisant des matrices stochastiques sont apparus dans les domaines de l' économétrie et de la théorie des circuits . Dans les années 1960, les matrices stochastiques sont apparues dans une variété encore plus large d'ouvrages scientifiques, des sciences du comportement à la géologie en passant par la planification résidentielle . En outre, de nombreux travaux mathématiques ont également été effectués au cours de ces décennies pour améliorer la gamme d'utilisations et de fonctionnalités de la matrice stochastique et des processus markoviens plus généralement.

Des années 1970 à nos jours, les matrices stochastiques ont trouvé une utilisation dans presque tous les domaines qui nécessitent une analyse formelle, de la science structurelle au diagnostic médical à la gestion du personnel . De plus, les matrices stochastiques ont trouvé une large utilisation dans la modélisation des changements de terres , généralement sous le terme de matrice de Markov.

Définition et propriétés

Une matrice stochastique décrit une chaîne de Markov X _t sur un espace d' état fini S de cardinal S .

Si la probabilité de passer de i à j en un pas de temps est Pr( j | i ) = P _{i , j} , la matrice stochastique P est donnée en utilisant P _{i , j} comme élément de i -ième ligne et j -ème colonne , par exemple,

${\displaystyle P=\left[{\begin{matrix}P_{1,1}&P_{1,2}&\dots &P_{1,j}&\dots &P_{1,S}\\P_{2, 1}&P_{2,2}&\dots &P_{2,j}&\dots &P_{2,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{i ,1}&P_{i,2}&\dots &P_{i,j}&\dots &P_{i,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{ S,1}&P_{S,2}&\dots &P_{S,j}&\dots &P_{S,S}\\\end{matrice}}\right].}$

Étant donné que le total de la probabilité de transition d'un état i à tous les autres états doit être 1,

${\displaystyle \sum _{j=1}^{S}P_{i,j}=1;\,}$

donc cette matrice est une matrice stochastique droite.

La somme par élément ci-dessus sur chaque ligne i de P peut être écrite de manière plus concise comme P 1 = 1 , où 1 est le vecteur S -dimensionnel de tous les uns. Avec cela, on peut voir que le produit de deux matrices stochastiques droite P ' et P ' ' est aussi droite stochastique: P ' P '' 1 = P '( P ' ' 1 ) = P ' 1 = 1 . En général, la puissance k- ième P ^k d'une matrice stochastique droite P est également stochastique droite. La probabilité de passer de i à j en deux étapes est alors donnée par le ( i , j ) -ième élément du carré de P :

${\displaystyle \left(P^{2}\right)_{i,j}.}$

En général, la probabilité de passage de n'importe quel état à un autre état dans une chaîne de Markov finie donnée par la matrice P en k pas est donnée par P ^k .

Une distribution de probabilité initiale des états, spécifiant où le système pourrait être initialement et avec quelles probabilités, est donnée sous forme de vecteur ligne .

Un stationnaire vecteur de probabilité π est définie comme étant une distribution, écrite en tant que vecteur de ligne, qui ne change pas sous l' application de la matrice de transition; c'est-à-dire qu'elle est définie comme une distribution de probabilité sur l'ensemble {1, …, n } qui est également un vecteur propre ligne de la matrice de probabilité, associé à la valeur propre 1 :

${\displaystyle {\boldsymbol {\pi }}P={\boldsymbol {\pi }}.}$

On peut montrer que le rayon spectral de toute matrice stochastique est un. Par le théorème du cercle de Gershgorin , toutes les valeurs propres d'une matrice stochastique ont des valeurs absolues inférieures ou égales à un. En outre, chaque matrice stochastique droite a une « évidente » colonne vecteur propre associé à la valeur propre 1: le vecteur 1 , dont les coordonnées sont tous égaux à 1 ( il suffit d' observer que la multiplication d' une rangée de A fois 1 est égale à la somme des entrées de la rangée et, par conséquent, il est égal à 1). Comme les valeurs propres gauche et droite d'une matrice carrée sont les mêmes, chaque matrice stochastique a, au moins, un vecteur propre ligne associé à la valeur propre 1 et la plus grande valeur absolue de toutes ses valeurs propres est également 1. Enfin, le théorème du point fixe de Brouwer ( appliqué à l'ensemble convexe compact de toutes les distributions de probabilité de l'ensemble fini {1, …, n } ) implique qu'il existe un vecteur propre gauche qui est également un vecteur de probabilité stationnaire.

D'autre part, le théorème de Perron-Frobenius garantit également que chaque matrice stochastique irréductible a un tel vecteur stationnaire, et que la plus grande valeur absolue d'une valeur propre est toujours 1. Cependant, ce théorème ne peut pas être appliqué directement à de telles matrices car elles ont besoin pas être irréductible.

En général, il peut y avoir plusieurs de ces vecteurs. Cependant, pour une matrice à entrées strictement positives (ou, plus généralement, pour une matrice stochastique apériodique irréductible), ce vecteur est unique et peut être calculé en observant que pour tout i on a la limite suivante,

${\displaystyle \lim _{k\rightarrow \infty }\left(P^{k}\right)_{i,j}={\boldsymbol {\pi }}_{j},}$

où π _j est le j -ième élément du vecteur ligne π . Entre autres choses, cela dit que la probabilité à long terme d'être dans un état j est indépendante de l'état initial i . Que ces deux calculs donnent le même vecteur stationnaire est une forme d'un théorème ergodique , ce qui est généralement vrai dans une grande variété de systèmes dynamiques dissipatifs : le système évolue, au fil du temps, vers un état stationnaire .

Intuitivement, une matrice stochastique représente une chaîne de Markov ; l'application de la matrice stochastique à une distribution de probabilité redistribue la masse de probabilité de la distribution d'origine tout en préservant sa masse totale. Si ce processus est appliqué à plusieurs reprises, la distribution converge vers une distribution stationnaire pour la chaîne de Markov.

Exemple : le chat et la souris

Supposons qu'il y ait une minuterie et une rangée de cinq cases adjacentes, avec un chat dans la première case et une souris dans la cinquième case au temps zéro. Le chat et la souris sautent tous les deux vers une case adjacente aléatoire lorsque le chronomètre avance. Par exemple, si le chat est dans la deuxième case et la souris dans la quatrième, la probabilité est d'un quart que le chat soit dans la première case et la souris dans la cinquième une fois le chronomètre avancé . Si le chat est dans la première case et la souris dans la cinquième, la probabilité est que le chat soit dans la case deux et que la souris soit dans la case quatre une fois le chronomètre avancé. Le chat mange la souris si les deux se retrouvent dans la même boîte, moment auquel le jeu se termine. La variable aléatoire K donne le nombre de pas de temps pendant lesquels la souris reste dans le jeu.

La chaîne de Markov qui représente ce jeu contient les cinq états suivants spécifiés par la combinaison de positions (chat, souris). Notez que bien qu'une énumération naïve d'états répertorie 25 états, beaucoup sont impossibles soit parce que la souris ne peut jamais avoir un indice inférieur à celui du chat (car cela signifierait que la souris a occupé la boîte du chat et a survécu pour la dépasser), soit parce que la somme des deux indices aura toujours une parité paire . De plus, les 3 états possibles qui conduisent à la mort de la souris sont combinés en un seul :

• État 1 : (1,3)
• État 2: (1,5)
• État 3 : (2,4)
• État 4: (3,5)
• Etat 5 : jeu terminé : (2,2), (3,3) & (4,4).

Nous utilisons une matrice stochastique (ci-dessous) pour représenter les probabilités de transition de ce système (les lignes et les colonnes de cette matrice sont indexées par les états possibles énumérés ci-dessus, avec l'état pré-transition comme ligne et l'état post-transition comme colonne). Par exemple, à partir de l'état 1 – 1ère ligne – il est impossible que le système reste dans cet état, donc ; le système ne peut pas non plus passer à l'état 2 - car le chat serait resté dans la même boîte - donc , et par un argument similaire pour la souris, . Les transitions vers les états 3 ou 5 sont autorisées, et donc . ${\style d'affichage P}$${\style d'affichage P_{11}=0}$${\style d'affichage P_{12}=0}$${\style d'affichage P_{14}=0}$${\style d'affichage P_{13},P_{15}\neq 0}$

${\displaystyle P={\begin{bmatrix}0&0&1/2&0&1/2\\0&0&1&0&0\\1/4&1/4&0&1/4&1/4\\0&0&1/2&0&1/2\\0&0&0&0&1\end{bmatrix}}.}$

Moyennes à long terme

Quel que soit l'état initial, le chat finira par attraper la souris (avec probabilité 1) et un état stationnaire π = (0,0,0,0,1) est approché comme limite. Pour calculer la valeur moyenne ou attendue à long terme d'une variable stochastique , pour chaque état et temps, il y a une contribution de . La survie peut être traitée comme une variable binaire avec pour un état de survie et pour l'état terminé. Les états avec ne contribuent pas à la moyenne à long terme. ${\style d'affichage Y}$${\style d'affichage S_{j}}$${\style d'affichage t_{k}}$${\displaystyle Y_{j,k}\cdot P(S=S_{j},t=t_{k})}$${\style d'affichage Y=1}$${\style d'affichage Y=0}$${\style d'affichage Y=0}$

Représentation de type phase

La fonction de survie de la souris. La souris survivra au moins au premier pas de temps.

Comme l'état 5 est un état absorbant, la distribution du temps jusqu'à l'absorption est distribuée de type phase discrète . Supposons que le système démarre à l'état 2, représenté par le vecteur . Les états où la souris a péri ne contribuent pas à la moyenne de survie, donc l'état cinq peut être ignoré. L'état initial et la matrice de transition peuvent être réduits à, ${\style d'affichage [0,1,0,0,0]}$

${\displaystyle {\boldsymbol {\tau }}=[0,1,0,0],\qquad T={\begin{bmatrix}0&0&{\frac {1}{2}}&0\\0&0&1&0\\{ \frac {1}{4}}&{\frac {1}{4}}&0&{\frac {1}{4}}\\0&0&{\frac {1}{2}}&0\end{bmatrix} },}$

et

${\displaystyle (IT)^{-1}{\boldsymbol {1}}={\begin{bmatrix}2.75\\4.5\\3.5\\2.75\end{bmatrix}},}$

où est la matrice d'identité et représente une matrice de colonnes de tous les uns qui agit comme une somme sur les états. ${\style d'affichage I}$${\displaystyle \mathbf {1} }$

Étant donné que chaque état est occupé pendant un pas de temps, le temps attendu de la survie de la souris n'est que la somme de la probabilité d'occupation sur tous les états survivants et les pas de temps,

${\displaystyle E[K]={\boldsymbol {\tau }}\left(I+T+T^{2}+\cdots \right){\boldsymbol {1}}={\boldsymbol {\tau }} (IT)^{-1}{\boldsymbol {1}}=4.5.}$

Les moments d'ordre supérieur sont donnés par

${\displaystyle E[K(K-1)\dots (K-n+1)]=n!{\boldsymbol {\tau }}(I-{T})^{-n}{T}^{n -1}\mathbf {1} \,.}$

Voir également

• Matrice de densité
• Noyau de Markov , l'équivalent d'une matrice stochastique sur un espace d'état continu
• Équation de différence matricielle
• Modèles d'évolution de l'ADN
• L'inégalité de Muirhead
• Automate probabiliste

Les références