Matriz estocástica

Matriz utilizada para describir las transiciones de una cadena de Markov

En matemáticas, una matriz estocástica es una matriz cuadrada que se utiliza 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 . ^{[1] [2] : 10} También se denomina 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 se ha utilizado 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 . Existen varias definiciones y tipos diferentes de matrices estocásticas:

Una matriz estocástica derecha es una matriz cuadrada de números reales no negativos, donde cada fila suma 1.

Una matriz estocástica izquierda es una matriz cuadrada de números reales no negativos, donde cada columna suma 1.

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

En la misma línea, se puede definir un 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 de probabilidad. Las matrices estocásticas derechas actúan sobre los vectores fila de probabilidades mediante la multiplicación desde la derecha, y las matrices estocásticas izquierdas actúan sobre los vectores columna de probabilidades mediante la multiplicación desde la izquierda. Este artículo sigue la convención anterior. Además, una matriz subestocástica es una matriz cuadrada real cuyas sumas de filas son todas ${\displaystyle \leq 1.}$

Historia

Andrei 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. ^[3] Sus usos iniciales previstos eran para el análisis lingüístico y otros temas matemáticos como el barajado de cartas , pero tanto las cadenas de Markov como las matrices encontraron rápidamente uso en otros campos. ^{[3] [4]}

Las matrices estocásticas fueron desarrolladas aún más por académicos como Andrey Kolmogorov , quien expandió sus posibilidades al permitir procesos de Markov en tiempo continuo. ^[5] En la década de 1950, aparecieron artículos que utilizaban matrices estocásticas en los campos de la econometría ^[6] y la teoría de circuitos . ^[7] 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 ^[8] hasta la geología ^{[9] [10]} y la planificación residencial . ^[11] Además, también se realizó mucho trabajo matemático durante estas décadas para mejorar la gama de usos y la funcionalidad de la matriz estocástica y los procesos markovianos en general.

Desde la década de 1970 hasta la actualidad, las matrices estocásticas han encontrado uso en casi todos los campos que requieren análisis formal, desde la ciencia estructural ^[12] hasta el diagnóstico médico ^[13] y la gestión de personal . ^[14] Además, las matrices estocásticas han encontrado un amplio uso en el modelado de cambios en la tierra , generalmente bajo el término matriz de Markov. ^[15]

Definición y propiedades

Una matriz estocástica describe una cadena de Markov X _t sobre un espacio de estados finitos S con cardinalidad α .

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 se da utilizando P _{i , j} como el elemento de la fila i y la columna j , por ejemplo,

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

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

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

Por lo tanto, esta matriz es una matriz estocástica derecha.

La suma elemento por elemento anterior en cada fila i de P se puede escribir de forma más concisa como P 1 = 1 , donde 1 es el vector columna α -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ástico derecho: 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 transición de i a j en dos pasos está dada entonces por el ( i , j ) -ésimo elemento del cuadrado de P :

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

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

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

Un vector de probabilidad estacionario π se define como una distribución, escrita como un vector 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. Por 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 derecha tiene un vector propio de columna "obvio" asociado al valor propio 1: el vector 1 utilizado anteriormente, cuyas coordenadas son todas iguales a 1. Como los valores propios izquierdo y derecho de una matriz cuadrada son los mismos, 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 también es 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 otra parte, 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 dichas matrices porque no necesitan ser irreducibles.

En general, puede haber varios vectores de este tipo. 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, al tiempo que conserva su masa total. Si este proceso se aplica repetidamente, la distribución converge a una distribución estacionaria para la cadena de Markov. ^{[2] : 14–17  [16] : 116}

Las matrices estocásticas y su producto forman una categoría , que es a la vez una subcategoría de la categoría de matrices y de la de núcleos de Markov .

Ejemplo: El gato y el ratón

Supongamos que hay un cronómetro y una fila de cinco casillas adyacentes. En el momento cero, un gato está en la primera casilla y un ratón en la quinta. Tanto el gato como el ratón saltan a una casilla adyacente al azar cuando avanza el cronómetro. Por ejemplo, si el gato está en la segunda casilla y el ratón en la cuarta, la probabilidad de que el gato esté en la primera casilla y el ratón en la quinta después de que avance el cronómetro es de un cuarto. Si el gato está en la primera casilla y el ratón en la quinta, la probabilidad de que el gato esté en la casilla dos y el ratón en la casilla cuatro después de que avance el cronómetro es de uno. El gato se come al ratón si ambos terminan en la misma casilla, momento en el que termina el juego. Sea la variable aleatoria K el tiempo que el ratón 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). Nótese 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 menor que el gato (ya que eso significaría que el ratón ocupó la casilla 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).

Utilizamos 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 estados posibles enumerados arriba, con el estado anterior a la transición como la fila y el estado posterior a la transición como la columna). Por ejemplo, a partir del estado 1 (primera fila), es imposible que el sistema permanezca en este estado, por lo que ; el sistema tampoco puede pasar al estado 2 (porque el gato se habría quedado en la misma caja), por lo que , y por un argumento similar para el ratón, . Se permiten las transiciones a los estados 3 o 5, y por lo 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 acabará atrapando al ratón (con probabilidad 1) y se aproxima un estado estacionario π = (0,0,0,0,1) como límite. Para calcular el promedio a largo plazo o el valor esperado 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 superviviente 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 fase

Función de supervivencia del ratón. El ratón sobrevivirá al menos el 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 fases . Supongamos que el sistema comienza en el estado 2, representado por el vector . Los estados en los que el ratón ha muerto no contribuyen al promedio de supervivencia, por lo que se puede ignorar el estado cinco. La matriz de estado inicial y de transición se puede 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 (I-T)^{-1}{\boldsymbol {1}}={\begin{bmatrix}2.75\\4.5\\3.5\\2.75\end{bmatrix}},}$

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

Dado que cada estado está ocupado durante un paso de tiempo, el tiempo esperado de supervivencia del ratón es simplemente la suma de la probabilidad de ocupación sobre todos los estados y pasos de tiempo sobrevivientes.

${\displaystyle E[K]={\boldsymbol {\tau }}\left(I+T+T^{2}+\cdots \right){\boldsymbol {1}}={\boldsymbol {\tau }}(I-T)^{-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} \,.}$

Véase también

• Matriz de densidad
• Núcleo de Markov , el equivalente de una matriz estocástica sobre un espacio de estados continuo
• Ecuación diferencial de matrices
• Modelos de evolución del ADN
• Desigualdad de Muirhead
• Autómata probabilístico
• Matriz de tasa de transición , utilizada para generalizar la matriz estocástica al tiempo continuo

Referencias

1. Asmussen, SR (2003). "Cadenas de Markov". Probabilidad aplicada y colas . Modelado estocástico y probabilidad aplicada. Vol. 51. págs. 3–8. doi :10.1007/0-387-21525-5_1. ISBN 978-0-387-00211-8.
2. Lawler, Gregory F. (2006). Introducción a los procesos estocásticos (2.ª ed.). CRC Press. ISBN 1-58488-651-X.
3. Hayes, Brian (2013). "Primeros eslabones de la cadena de Markov". American Scientist . 101 (2): 92–96. doi :10.1511/2013.101.92.
4. Charles Miller Grinstead; James Laurie Snell (1997). Introducción a la probabilidad. American Mathematical Soc. págs. 464–466. ISBN 978-0-8218-0749-1 . 
5. Kendall, DG; Batchelor, GK; Bingham, NH; Hayman, WK; Hyland, JME; Lorentz, GG; Moffatt, HK; Parry, W.; Razborov, AA; Robinson, CA; Whittle, P. (1990). "Andrei Nikolaevich Kolmogorov (1903–1987)". Boletín de la Sociedad Matemática de Londres . 22 (1): 33. doi :10.1112/blms/22.1.31.
6. Solow, Robert (1 de enero de 1952). "Sobre la estructura de los modelos lineales". Econometrica . 20 (1): 29–46. doi :10.2307/1907805. JSTOR  1907805.
7. Sittler, R. (1 de diciembre de 1956). "Análisis de sistemas de procesos discretos de Markov". IRE Transactions on Circuit Theory . 3 (4): 257–266. doi :10.1109/TCT.1956.1086324. ISSN  0096-2007.
8. Evans, Selby (1 de julio de 1967). "Vargus 7: patrones computados a partir de procesos de Markov". Ciencias del comportamiento . 12 (4): 323–328. doi :10.1002/bs.3830120407. ISSN  1099-1743.
9. Gingerich, PD (1 de enero de 1969). "Análisis de Markov de sedimentos aluviales cíclicos". Revista de investigación sedimentaria . 39 (1): 330–332. Código Bibliográfico :1969JSedR..39..330G. doi :10.1306/74d71c4e-2b21-11d7-8648000102c1865d. ISSN  1527-1404.
10. Krumbein, WC; Dacey, Michael F. (1 de marzo de 1969). "Cadenas de Markov y cadenas de Markov incrustadas en geología". Revista de la Asociación Internacional de Geología Matemática . 1 (1): 79–96. doi :10.1007/BF02047072. ISSN  0020-5958.
11. Wolfe, Harry B. (1 de mayo de 1967). "Modelos para condicionar el envejecimiento de las estructuras residenciales". Revista del Instituto Americano de Planificadores . 33 (3): 192–196. doi :10.1080/01944366708977915. ISSN  0002-8991.
12. Krenk, S. (noviembre de 1989). "Una matriz de Markov para la simulación de cargas de fatiga y la evaluación del rango de flujo de lluvia". Seguridad estructural . 6 (2–4): 247–258. doi :10.1016/0167-4730(89)90025-8.
13. Beck, J. Robert; Pauker, Stephen G. (1 de diciembre de 1983). "El proceso de Markov en el pronóstico médico". Toma de decisiones médicas . 3 (4): 419–458. doi :10.1177/0272989X8300300403. ISSN  0272-989X. PMID  6668990.
14. Gotz, Glenn A.; McCall, John J. (1 de marzo de 1983). "Análisis secuencial de la decisión de quedarse o irse: oficiales de la Fuerza Aérea de Estados Unidos". Management Science . 29 (3): 335–351. doi :10.1287/mnsc.29.3.335. ISSN  0025-1909.
15. Kamusoko, Courage; Aniya, Masamu; Adi, Bongo; Manjoro, Munyaradzi (1 de julio de 2009). "La sostenibilidad rural bajo amenaza en Zimbabwe: simulación de futuros cambios en el uso y la cobertura de la tierra en el distrito de Bindura con base en el modelo de autómatas celulares de Markov". Applied Geography . 29 (3): 435–447. doi :10.1016/j.apgeog.2008.10.002.
16. Kardar, Mehran (2007). Física estadística de campos . Cambridge University Press . ISBN 978-0-521-87341-3.OCLC 920137477  .