Cadena de Márkov

(Redirigido desde «Cadena de Markov»)

En la teoría de la probabilidad, se conoce como cadena de Márkov o modelo de Márkov a un tipo especial de proceso estocástico discreto en el que la probabilidad de que ocurra un evento depende solamente del evento inmediatamente anterior. Esta característica de incluir una memoria reciente recibe el nombre de propiedad de Markov en contraste con los eventos independientes que no tienen memoria de ningún evento anterior. En un primer artículo de 1906 A. A. Markov definió la "cadena simple" como "una secuencia infinita de variables conectadas de tal modo que para cualquier es independiente de , en el caso de que sea conocida”. Markov llamó a la cadena "homogénea" si la distribución condicional de dado fuese independiente de . También consideró cadenas "complejas (complex en inglés)" en las que "cada número está conectado directamente no sólo con uno, sino con varios números anteriores".[1]

Cadena simple biestable de Markov

Recibe su nombre del matemático ruso Andréi Márkov (1856-1922), que lo introdujo en 1906.[1]

Estos modelos estadísticos cuentan con un gran número de aplicaciones reales.

Definición

editar

En matemáticas, una Cadena de Markov es un proceso estocástico a tiempo discreto   con espacio de estados discreto   que para cualquier entero   y para cualesquiera   satisface

 

a esta propiedad se le conoce como propiedad de Markov.

Características

editar

Cadenas homogéneas y no homogéneas

editar

Se dice que una Cadena de Markov es homogénea si la probabilidad de ir del estado   al estado   en un paso no depende del tiempo en el que se encuentra la cadena, esto es:

 

para todo   y para cualquier  .

Si para alguna pareja de estados y para algún tiempo   la propiedad antes mencionada no se cumple entonces diremos que la Cadena de Markov es no homogénea.

Probabilidades de Transición

editar

Sean   y   dos estados de una Cadena de Markov. La probabilidad de ir del estado   en el tiempo   al estado   en el tiempo   se denota por

 .

Cuando la cadena es homogénea, esta probabilidad se denota por

 ,

que representa la probabilidad de pasar del estado   al estado   en una unidad de tiempo.

Las probabilidades de transición suelen venir dadas mediante números reales. Si estas probabilidades no se conocen de forma precisa, es necesario estimarlas de alguna manera con la incertidumbre que implica cualquier procedimiento de estimación.[2][3]​ Así, por ejemplo, se pueden estimar mediante intervalos modales[4]​ o por números borrosos.[5]

Matriz de Probabilidades de Transición

editar

Teniendo las probabilidades de transición en un paso , , si variamos los índices   sobre el espacio de estados   obtenemos la matriz   llamada matriz de probabilidades de transición en un paso, es decir:

 

donde la entrada   representa la probabilidad de pasar del estado   al estado   en un paso.

La matriz   es una matriz estocástica pues satisface

  •  
  •  

Similarmente se define la matriz de probabilidades de transición en   pasos, esta se denota por   y está dada por

 

donde la entrada   representa la probabilidad de pasar del estado   al estado   en   pasos.

Ecuación de Chapman-Kolmogorov

editar

Para cualesquiera   tales que   y para cualesquiera estados   se cumple

 

Como consecuencia de este resultado, la probabilidad de transición en   pasos,  , está dada por la entrada   de la  -ésima potencia de la matriz de probabilidades de transición en un paso, es decir

 

Con lo anterior, el problema de calcular las probabilidades de transición en   pasos se convierte en hallar la  -ésima potencia de la matriz de probabilidades de transición en un paso, esto es

 

Clases de comunicación

editar

Para dos estados   y   en el espacio de estados  , diremos que el estado   es accesible desde el estado   y escribiremos   si   tal que

 

si   y   entonces diremos que el estado   se comunica con el estado   y escribiremos  .

La propiedad " " es una relación de equivalencia. Esta relación induce una partición del espacio de estados. A estas clases de equivalencia las llamaremos clases de comunicación.

Dado un estado  , denotaremos a su clase de comunicación como  , por lo que   si y sólo si  .

Si   entonces se dice que la cadena es irreducible.

Periodicidad

editar

El periodo de un estado   se define como:

 

donde   denota el máximo común divisor.

  • Si   diremos que   es un estado aperiódico.
  • Si   diremos que   tiene periodo  .

Una cadena de Márkov se dice aperiódica si todos sus estados son aperiódicos, es decir, sí  .

Tiempos de Primera Visita

editar

Si  , definimos el tiempo de primera visita a   como la variable aleatoria

 

esto es,   denota la primera vez que la cadena entra al conjunto de estados  .

Probabilidad de Primera Visita

editar

Se define

 

como la probabilidad de que una cadena que inicia en el estado   llegue al estado   por primera vez en   pasos, donde  .

En particular, cuando  ,   denota la probabilidad de regresar por primera vez al estado   en   pasos.

Y se definen

 

como la probabilidad de una eventual visita a partir del estado   al estado   y

 

como la probabilidad de partir del estado   y regresar a él mismo en un tiempo finito.

Recurrencia

editar

En una cadena de Markov con espacio de estados  , diremos que:

  •   es un estado recurrente si  .
  •   es transitorio si  .

o utilizando las probabilidades de transición en   pasos:

  •   es recurrente si  
  •   es transitorio si  

La recurrencia es una propiedad de clase pues

  • Si   es recurrente e   entonces   es recurrente.
  • Si   es transitorio e   entonces   es transitorio.

Tiempo Medio de Recurrencia

editar

Se define como el tiempo medio de recurrencia de un estado recurrente   a partir del estado   como la esperanza de

 

y se denota por  

 ,

Esta esperanza representa el número de pasos promedio que a la cadena le toma regresar al estado recurrente  .

En particular, cuando   escribimos   en lugar de  .

Se dice que un estado recurrente   es

  • recurrente nulo si  .
  • recurrente positivo si  .

La recurrencia positiva es una propiedad de clase pues

  • Si   es recurrente positivo e   entonces   es recurrente positivo.
  • Si   es recurrente nulo e   entonces   es recurrente nulo.

Distribuciones Estacionarias

editar

Se dice que el vector   es una distribución de probabilidad si

  •  
  •  

Se dice que una distribución de probabilidad   es estacionaria para una Cadena de Markov con matriz de probabilidades de transición   si

 

En forma matricial lo anterior es equivalente a   y significa que si una variable aleatoria inicial   tiene una distribución   entonces la distribución de   también es  , es decir, esta distribución no cambia con el paso del tiempo.

Para encontrar una posible distribución estacionaria de una cadena con matriz  , un método consiste en resolver el sistema de ecuaciones

 

La distribución estacionaria puede no ser única o incluso no existir.

Existencia y Unicidad

editar

Si una Cadena de Markov es irreducible y recurrente positiva entonces tiene una única distribución estacionaria y esta está dada por

 

donde   es el tiempo medio de recurrencia del estado  .

Convergencia a la distribución estacionaria

editar

Si una cadena de Markov es

  • Irreducible
  • Aperiódica
  • Con distribución estacionaria  

entonces para cualesquiera  

 

Convergencia para Cadenas de Markov

editar

Si una cadena de Markov es

  • Irreducible
  • Recurrente positiva
  • Aperiódica

entonces las probabilidades límite

 

existen, están dadas por

 

y constituyen la única solución al sistema de ecuaciones

 

Tipos de Cadenas de Markov

editar

Cadenas irreducibles

editar

Una cadena de Markov se dice irreducible si se cumple cualquiera de las siguientes condiciones (equivalentes entre sí):

  1. Desde cualquier estado de   se puede acceder a cualquier otro.
  2. Todos los estados se comunican entre sí.
  3.   para algún  .
  4.   para todo  .
  5. El único conjunto cerrado es el total.

La cadena de Ehrenfest o la caminata aleatoria sin barreras absorbentes son ejemplos de cadenas de Márkov irreducibles.

Cadenas Recurrentes Positivas

editar

Una cadena de Markov se dice recurrente positiva si todos sus estados son recurrentes positivos. Si la cadena es además irreducible es posible demostrar que existe un único vector de probabilidad invariante y está dado por:

 

Cadenas Regulares

editar

Una cadena de Márkov se dice regular (también primitiva o ergódica) si existe alguna potencia positiva de la matriz de transición cuyas entradas sean todas estrictamente mayores que cero.

Cuando el espacio de estados   es finito, si   denota la matriz de transición de la cadena se tiene que:

 

donde   es una matriz con todos sus renglones iguales a un mismo vector de probabilidad w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas regulares, este vector invariante es único.

Cadenas Absorbentes

editar

Una cadena de Márkov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones siguientes:

  1. La cadena tiene al menos un estado absorbente.
  2. De cualquier estado no absorbente se accede a algún estado absorbente.

Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos los siguientes resultados:

  • Su matriz de transición siempre se puede llevar a una de la forma
 

donde la submatriz Q corresponde a los estados del conjunto  ,   es la matriz identidad,   es la matriz nula y   alguna submatriz.

  •  , esto es, no importa en donde se encuentre la cadena, finalmente terminará en un estado absorbente.

Cadenas de Markov a tiempo continuo

editar

Si en lugar de considerar una secuencia discreta   con   indexado en el conjunto   de números naturales, se consideran las variables aleatorias   con   que varía en un intervalo continuo del conjunto   de números reales, tendremos una cadena en tiempo continuo. Para este tipo de cadenas en tiempo continuo la propiedad de Márkov se expresa de la siguiente manera:

  tal que  

Para una cadena de Márkov continua con un número finito de estados puede definirse una matriz estocástica dada por:

 

La cadena se denomina homogénea si  . Para una cadena de Márkov en tiempo continuo homogénea y con un número finito de estados puede definirse el llamado generador infinitesimal como:[6]

 

Y puede demostrarse que la matriz estocástica viene dada por:

 

Aplicaciones

editar

Meteorología

editar

Si consideramos el tiempo atmosférico de una región a través de distintos días, es posible asumir que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos. Por ejemplo, se han desarrollado modelos de recurrencia de las lluvias basados en cadenas de Markov.[7]

Modelos epidemiológicos

editar

Una importante aplicación de las cadenas de Markov se encuentra en el proceso Galton-Watson. Este es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una epidemia (véase modelaje matemático de epidemias).

Internet

editar

El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través de una cadena de Markov, donde la posición que tendrá una página en el buscador será determinada por su peso en la distribución estacionaria de la cadena.

Simulación

editar

Las cadenas de Márkov son utilizadas para proveer una solución analítica a ciertos problemas de simulación, por ejemplo en teoría de colas el Modelo M/M/1[8]​ es de hecho un modelo de cadenas de Markov.

Juegos de azar

editar

Son muchos los juegos de azar que se pueden modelar a través de una cadena de Márkov. El modelo de la ruina del jugador (Gambler's ruin), que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero, es una de las aplicaciones de las cadenas de Márkov en este rubro.

Economía y finanzas

editar

Las cadenas de Márkov se pueden utilizar en modelos simples de valuación de opciones para determinar cuándo existe oportunidad de arbitraje, así como en el modelo de colapsos de una bolsa de valores o para determinar la volatilidad de los precios. En los negocios, las cadenas de Márkov se han utilizado para analizar los patrones de compra de los deudores morosos, para planear las necesidades de personal y para analizar el reemplazo de equipo.

Genética

editar

Se emplean cadenas de Márkov en teoría de genética de poblaciones, para describir el cambio de frecuencias génicas en una población pequeña con generaciones discretas, sometida a deriva genética. Ha sido empleada en la construcción del modelo de difusión de Motō Kimura.

Música

editar

Diversos algoritmos de composición musical usan cadenas de Márkov, por ejemplo el software Csound o Max. Uno de los compositores que usó esta técnica en sus composiciones fue Iannis Xenakis con su obra Analoguique A et B (1958–59).

Operaciones

editar

Se emplean cadenas de Márkov en inventarios, mantenimiento y flujo de proceso.

Redes neuronales

editar

Se utilizan en las máquinas de Boltzmann.

Referencias

editar
  1. a b Basharin, Gely P.; Langville, Amy N.; Naumov, Valeriy A. (2004). «The Life and Work of A. A. Markov». Linear Algebra and its Applications (en inglés) 386: 3-26. Consultado el 31 de marzo de 2010. 
  2. Buckley, J.J.; Eslami, E. (2002). Fuzzy Markov Chains: Uncertain Probabilities. Mathware and Soft Computing 9, 33–41.
  3. Villacorta, P.J.; Verdegay, J.L. FuzzyStatProb: An R Package for the Estimation of Fuzzy Stationary Probabilities from a Sequence of Observations of an Unknown Markov Chain. Journal of Statistical Software 2016, 71, 1–27, https://doi.org/10.18637/jss.v071.i08
  4. Adillon, R.; Lambert, J.; Mármol, M. (2020). Modal interval probability: Application to Bonus-Malus Systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 28, 837–851, https://doi.org.10.1142/S0218488520500361
  5. Villacorta Iglesias, P.J.; González-Vila Puchades, L. and Andrés-Sánchez, J. de. (2021). Fuzzy Markovian Bonus-Malus Systems in Non-Life Insurance. Mathematics, 9(4), 347, https://doi.org/10.3390/math9040347
  6. Masaki Kijima, 1997, p. 175
  7. R. Gabriel & J. Neumann (2006): A Markov chain model for daily rainfall occurrence at Tel Aviv
  8. Masaki Kijima, 1997, pp. 287-290.

Bibliografía

editar
  • A.A. Márkov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp. 135–156, 1906.
  • A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
  • Classical Text in Translation: A. A. Markov, An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains, trans. David Link. Science in Context 19.4 (2006): 591–600. Online: http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=637500
  • Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. (See Chapter 7.)
  • J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.
  • S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability. London: Springer-Verlag, 1993. ISBN 0-387-19832-6. en línea: [1] . Second edition to appear, Cambridge University Press, 2009.
  • S. P. Meyn. Control Techniques for Complex Networks. Cambridge University Press, 2007. ISBN 978-0-521-88441-9. Appendix contains abridged Meyn & Tweedie. en línea: https://web.archive.org/web/20100619011046/https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html
  • Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st edición). Nueva York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.  Extensive, wide-ranging book meant for specialists, written for both theoretical computer scientists as well as electrical engineers. With detailed explanations of state minimization techniques, FSMs, Turing machines, Markov processes, and undecidability. Excellent treatment of Markov processes pp. 449ff. Discusses Z-transforms, D transforms in their context.
  • Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Finite Mathematical Structures (1st edición). Englewood Cliffs, N.J.: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841.  Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.
  • Kijima, Masaaki (1997). Markov Processes for Stochastic Modeling (1st edición). Cambridge: Chapman & Hall. ISBN 0 412 60660 7. 
  • E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X

Enlaces externos

editar

a