Matriz estocástica - Stochastic matrix

En matemáticas, una matriz estocástica es una matriz cuadrada que se usa para describir las transiciones de una cadena de Markov . Cada una de sus entradas es un número real no negativo que representa una probabilidad . También se le llama matriz de probabilidad , matriz de transición , matriz de sustitución o matriz de Markov . La matriz estocástica fue desarrollada por primera vez por Andrey Markov a principios del siglo XX y ha encontrado uso en una amplia variedad de campos científicos, incluida la teoría de la probabilidad , la estadística, las finanzas matemáticas y el álgebra lineal , así como la informática y la genética de poblaciones . Hay varias definiciones y tipos diferentes de matrices estocásticas:

Una matriz estocástica derecha es una matriz cuadrada real, con cada fila sumando 1.

Una matriz estocástica izquierda es una matriz cuadrada real, con cada columna sumando 1.

Una matriz doblemente estocástica es una matriz cuadrada de números reales no negativos con cada fila y columna sumando 1.

En la misma línea, se puede definir un vector estocástico (también llamado vector de probabilidad ) como un vector cuyos elementos son números reales no negativos que suman 1. Por lo tanto, cada fila de una matriz estocástica derecha (o columna de una matriz estocástica izquierda) es un vector estocástico. Una convención común en la literatura matemática en lengua inglesa es utilizar vectores de probabilidades de fila y matrices estocásticas derechas en lugar de vectores de probabilidades de columna y matrices estocásticas de izquierda; este artículo sigue esa convención.

Historia

Andrey Markov en 1886

La matriz estocástica fue desarrollada junto con la cadena de Markov por Andrey Markov , un matemático ruso y profesor de la Universidad de San Petersburgo que publicó por primera vez sobre el tema en 1906. Sus usos iniciales previstos fueron para el análisis lingüístico y otros temas matemáticos como el barajado de cartas , pero ambos Las cadenas y matrices de Markov encontraron rápidamente uso en otros campos.

Las matrices estocásticas fueron desarrolladas por estudiosos como Andrey Kolmogorov , que expandieron sus posibilidades al permitir procesos de Markov de tiempo continuo. En la década de 1950, habían aparecido artículos que utilizaban matrices estocásticas en los campos de la econometría y la teoría de circuitos . En la década de 1960, las matrices estocásticas aparecieron en una variedad aún más amplia de trabajos científicos, desde la ciencia del comportamiento hasta la geología y la planificación residencial . Además, también se realizó mucho trabajo matemático a lo largo de estas décadas para mejorar la gama de usos y la funcionalidad de la matriz estocástica y los procesos de Markov en general.

Desde la década de 1970 hasta el presente, las matrices estocásticas se han utilizado en casi todos los campos que requieren análisis formal, desde la ciencia estructural hasta el diagnóstico médico y la gestión de personal . Además, las matrices estocásticas han encontrado un amplio uso en la modelización del cambio de suelo , generalmente bajo el término matriz de Markov.

Definición y propiedades

Una matriz estocástica describe un Markov cadena X _t durante un finito espacio de estado S con cardinalidad S .

Si la probabilidad de moverse de i a j en un paso de tiempo es Pr ( j | i ) = P _{i , j} , la matriz estocástica P viene dada por el uso de P _{i , j} como el elemento i -ésima fila y j -ésima columna , p.ej,

${\ 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 {matrix}} \ right].}$

Dado que el total de la probabilidad de transición de un estado i a todos los demás estados debe ser 1,

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

por tanto, esta matriz es una matriz estocástica derecha.

La suma de elementos anterior en cada fila i de P puede escribirse de manera más concisa como P 1 = 1 , donde 1 es el vector S -dimensional de todos los unos. Usando esto, se puede ver que el producto de dos matrices estocásticas derechas P ′ y P ′ ′ también es estocástica derecha: P ′ P ′ ′ 1 = P ′ ( P ′ ′ 1 ) = P ′ 1 = 1 . En general, la k -ésima potencia P ^k de una matriz estocástica derecha P también es estocástica derecha. La probabilidad de pasar de i a j en dos pasos viene dada por el ( i , j ) -ésimo elemento del cuadrado de P :

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

En general, la probabilidad de transición de pasar de cualquier estado a otro en una cadena de Markov finita dada por la matriz P en k pasos viene dada por P ^k .

Una distribución de probabilidad inicial de estados, que especifica dónde podría estar el sistema inicialmente y con qué probabilidades, se da como un vector de fila .

Un vector de probabilidad estacionario π se define como una distribución, escrita como un vector de fila, que no cambia bajo la aplicación de la matriz de transición; es decir, se define como una distribución de probabilidad en el conjunto {1,…, n } que también es un vector propio de fila de la matriz de probabilidad, asociado con el valor propio 1:

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

Se puede demostrar que el radio espectral de cualquier matriz estocástica es uno. Según el teorema del círculo de Gershgorin , todos los valores propios de una matriz estocástica tienen valores absolutos menores o iguales a uno. Además, cada matriz estocástica derecho tiene una columna de "obvio" vector propio asociado al valor propio 1: el vector 1 , cuyas coordenadas son todos iguales a 1 (sólo observar que la multiplicación de una fila de A veces 1 es igual a la suma de las entradas de la fila y, por tanto, es igual a 1). Como los valores propios izquierdo y derecho de una matriz cuadrada son iguales, cada matriz estocástica tiene, al menos, un vector propio de fila asociado al valor propio 1 y el valor absoluto más grande de todos sus valores propios es también 1. Finalmente, el teorema del punto fijo de Brouwer ( aplicado al conjunto convexo compacto de todas las distribuciones de probabilidad del conjunto finito {1,…, n } ) implica que hay algún vector propio izquierdo que también es un vector de probabilidad estacionario.

Por otro lado, el teorema de Perron-Frobenius también asegura que cada matriz estocástica irreducible tiene un vector estacionario, y que el valor absoluto más grande de un valor propio es siempre 1. Sin embargo, este teorema no se puede aplicar directamente a tales matrices porque necesitan no ser irreductible.

En general, puede haber varios de estos vectores. Sin embargo, para una matriz con entradas estrictamente positivas (o, más generalmente, para una matriz estocástica aperiódica irreducible), este vector es único y se puede calcular observando que para cualquier i tenemos el siguiente límite,

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

donde π _j es el j -ésimo elemento del vector fila π . Entre otras cosas, esto dice que la probabilidad a largo plazo de estar en un estado j es independiente del estado inicial i . El hecho de que ambos cálculos den el mismo vector estacionario es una forma de teorema ergódico , que generalmente es cierto en una amplia variedad de sistemas dinámicos disipativos : el sistema evoluciona, con el tiempo, a un estado estacionario .

Intuitivamente, una matriz estocástica representa una cadena de Markov; la aplicación de la matriz estocástica a una distribución de probabilidad redistribuye la masa de probabilidad de la distribución original mientras se conserva su masa total. Si este proceso se aplica repetidamente, la distribución converge a una distribución estacionaria para la cadena de Markov.

Ejemplo: el gato y el ratón

Suponga que hay un temporizador y una fila de cinco casillas adyacentes, con un gato en la primera casilla y un ratón en la quinta casilla en el tiempo cero. Tanto el gato como el ratón saltan a un cuadro adyacente aleatorio cuando avanza el temporizador. Por ejemplo, si el gato está en el segundo cuadro y el ratón en el cuarto, la probabilidad es de un cuarto de que el gato esté en el primer cuadro y el ratón en el quinto después de que avance el temporizador . Si el gato está en la primera casilla y el ratón en la quinta, la probabilidad es una de que el gato esté en la casilla dos y el ratón en la casilla cuatro después de que avance el temporizador. El gato se come al ratón si ambos terminan en la misma caja, momento en el que finaliza el juego. La variable aleatoria K da el número de pasos de tiempo que el mouse permanece en el juego.

La cadena de Markov que representa este juego contiene los siguientes cinco estados especificados por la combinación de posiciones (gato, ratón). Tenga en cuenta que si bien una enumeración ingenua de estados enumeraría 25 estados, muchos son imposibles, ya sea porque el ratón nunca puede tener un índice más bajo que el gato (ya que eso significaría que el ratón ocupó la caja del gato y sobrevivió para pasarla), o porque la suma de los dos índices siempre tendrá paridad par . Además, los 3 estados posibles que conducen a la muerte del ratón se combinan en uno:

• Estado 1: (1,3)
• Estado 2: (1,5)
• Estado 3: (2,4)
• Estado 4: (3,5)
• Estado 5: juego terminado: (2,2), (3,3) y (4,4).

Usamos una matriz estocástica, (abajo), para representar las probabilidades de transición de este sistema (las filas y columnas de esta matriz están indexadas por los posibles estados enumerados anteriormente, con el estado previo a la transición como la fila y el estado posterior a la transición como el columna). Por ejemplo, a partir del estado 1 - 1ª fila - es imposible que el sistema permanezca en este estado, entonces ; el sistema también no puede la transición al estado 2 - porque el gato se habría quedado en la misma caja - así , y por un argumento similar para el ratón, . Se permiten las transiciones a los estados 3 o 5, y por tanto . ${\ Displaystyle P}$${\ Displaystyle P_ {11} = 0}$${\ Displaystyle P_ {12} = 0}$${\ Displaystyle P_ {14} = 0}$${\ Displaystyle 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}}.}$

Promedios a largo plazo

No importa cuál sea el estado inicial, el gato eventualmente atrapará al ratón (con probabilidad 1) y un estado estacionario π = (0,0,0,0,1) se aproxima como límite. Calcular el valor promedio o esperado a largo plazo de una variable estocástica , para cada estado y tiempo hay una contribución de . La supervivencia se puede tratar como una variable binaria con para un estado de supervivencia y para el estado terminado. Los estados con no contribuyen al promedio a largo plazo. ${\ Displaystyle Y}$${\ Displaystyle S_ {j}}$${\ Displaystyle t_ {k}}$${\ Displaystyle Y_ {j, k} \ cdot P (S = S_ {j}, t = t_ {k})}$${\ Displaystyle Y = 1}$${\ Displaystyle Y = 0}$${\ Displaystyle Y = 0}$

Representación de tipo de fase

La función de supervivencia del ratón. El ratón sobrevivirá al menos al primer paso de tiempo.

Como el estado 5 es un estado absorbente, la distribución del tiempo hasta la absorción se distribuye de forma discreta por tipo de fase . Suponga que el sistema comienza en el estado 2, representado por el vector . Los estados donde murió el ratón no contribuyen al promedio de supervivencia, por lo que el estado cinco puede ignorarse. El estado inicial y la matriz de transición se pueden reducir a, ${\ Displaystyle [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} },}$

y

${\ displaystyle (IT) ^ {- 1} {\ boldsymbol {1}} = {\ begin {bmatrix} 2,75 \\ 4,5 \\ 3,5 \\ 2,75 \ end {bmatrix}},}$

donde es la matriz de identidad , y representa una matriz de columnas de todos los que actúa como una suma de estados. ${\ Displaystyle I}$${\ Displaystyle \ mathbf {1}}$

Dado que cada estado está ocupado por un paso de tiempo, el tiempo esperado de supervivencia del ratón es solo la suma de la probabilidad de ocupación sobre todos los estados y pasos supervivientes en el tiempo,

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

Los momentos de orden superior están dados por

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

Ver también

• Matriz de densidad
• Núcleo de Markov , el equivalente de una matriz estocástica sobre un espacio de estado continuo
• Ecuación de diferencias matriciales
• Modelos de evolución del ADN
• La desigualdad de Muirhead
• Autómata probabilístico

Referencias