CADENA DE MARKOV

Una cadena de Markov ( tiempo discreto cadena de Markov o DTMC [ 1 ] ) el nombre de Andrey Markov , es un sistema matemático que sufre transiciones de un estado a otro en un espacio de estados . Se trata de un proceso aleatorio suele caracterizarse como sin memoria : el siguiente estado depende sólo del estado actual y no en la secuencia de los acontecimientos que la precedieron. Este tipo específico de "memorylessness" se llama la propiedad de Markov . Cadenas de Markov tienen muchas aplicaciones como modelos estadísticos de procesos del mundo real.

Una simple cadena de Markov de dos estados

Una cadena de Markov es un proceso estocástico con la propiedad de Markov . El término "cadena de Markov" se refiere a la secuencia de variables aleatorias tal proceso se mueve a través, con la propiedad de Markov definir la dependencia de serie sólo entre períodos adyacentes (como en una "cadena"). Por lo tanto, se puede utilizar para los sistemas que siguen una serie de eventos vinculados, donde lo que sucede después depende sólo del estado actual del sistema que describe.

En la literatura diferentes procesos de Markov se designan como "cadenas de Markov". Por lo general, sin embargo, el término se reserva para un proceso con un conjunto discreto de veces (es decir, un tiempo discreto cadena de Markov (DTMC)) [ 2 ] , aunque algunos autores utilizan la misma terminología para referirse a una cadena de Markov de tiempo continuo y sin mención explícita . [ 3 ] [ 4 ] Si bien la definición de parámetros de tiempo se acuerdan sobre todo en el sentido de tiempo discreto, la cadena de Markov espacio de estado no tiene una definición establecida:. el término puede referirse a un proceso en un espacio arbitrariamente general del Estado [ 5 ] Sin embargo, muchos usos de las cadenas de Markov emplean finito o contable (o discreta en la línea verdadera ) espacios de estados, que tienen un análisis estadístico más sencillo. Debido a que hay-aparte de índice de tiempo y espacio de estados parámetros-muchas otras variaciones, extensiones y generalizaciones (ver Variaciones ), el resto de este artículo se centra en el tiempo discreto simple, caso de espacio de estado discreto, a menos que se mencione lo contrario.

Los cambios de estado del sistema se denominan transiciones, y las probabilidades asociadas a diferentes cambios de estado se llaman probabilidades de transición. El proceso se caracteriza por un espacio de estados, una matriz de transición que describe las probabilidades de transiciones particulares, y un estado inicial (o distribución inicial) a través del espacio de estado. Por convención, asumimos todos los posibles estados y las transiciones se han incluido en la definición del proceso, por lo que siempre hay un próximo estado, y el proceso no termina.

Un proceso aleatorio de tiempo discreto implica un sistema que está en un cierto estado en cada etapa, con el estado cambiando al azar entre los pasos. Los pasos son a menudo considerados como momentos en el tiempo, pero pueden igualmente hacer referencia a la distancia física o cualquier otra medición discreta. Formalmente, los pasos son los números enteros o números naturales , y el proceso aleatorio es una cartografía de éstos a los estados. La propiedad de Markov afirma que la distribución de probabilidad condicional para el sistema en el paso siguiente (y de hecho en todas las etapas futuras) depende sólo del estado actual del sistema, y no, además, sobre el estado del sistema en los pasos anteriores.

Dado que el sistema cambia al azar, por lo general es imposible predecir con certeza el estado de una cadena de Markov en un punto dado en el futuro. Sin embargo, las propiedades estadísticas de futuro del sistema se pueden predecir. En muchas aplicaciones, es estas propiedades estadísticas que son importantes.

Una famosa cadena de Markov es el llamado "pie de borracho", una caminata al azar en la recta numérica , donde, en cada paso, la posición puede cambiar en +1 o -1 con igual probabilidad. Desde cualquier posición hay dos posibles transiciones, a la siguiente o anterior entero. Las probabilidades de transición dependen sólo de la situación actual, no en la forma en que se llegó a la posición. Por ejemplo, las probabilidades de transición de 5 a 4 y 5 a 6 son ambos 0,5, y todas las demás probabilidades de transición de 5 son 0. Estas probabilidades son independientes de si el sistema estaba previamente en 4 o 6.

Otro ejemplo son los hábitos alimenticios de una criatura que sólo come las uvas, el queso o lechuga, y cuyos hábitos dietéticos ajustarse a las siguientes reglas:

Se alimenta de una sola vez al día. Si se comió el queso hoy, mañana se va a comer lechuga o las uvas con la misma probabilidad. Si se comió las uvas hoy, mañana se va a comer las uvas con una probabilidad de 1/10, el queso con una 

probabilidad 4/10 y la lechuga con una probabilidad 5/10. Si comió lechuga hoy, no va a comer lechuga de nuevo mañana, pero va a comer las uvas con una 

probabilidad de 4/10 o el queso con una probabilidad de 6/10.

Los hábitos alimenticios de esta criatura se pueden modelar con una cadena de Markov ya que su elección de mañana depende exclusivamente de lo que comió hoy, no lo que comió ayer o incluso más lejos en el pasado. Una propiedad estadística que podría ser calculado es el porcentaje esperado, durante un largo período, de los días en que la criatura va a comer uvas.

Una serie de eventos independientes (por ejemplo, una serie de lanzamientos de moneda) satisface la definición formal de una cadena de Markov. Sin embargo, la teoría se aplica por lo general sólo cuando la distribución de probabilidad de la siguiente paso depende no trivialmente sobre el estado actual.

Definición formal [ editar ]

Una cadena de Markov es una secuencia de variables aleatorias X 1 , X 2 , X 3 , ... con la propiedad de Markov, a saber, que, dada la situación actual, el futuro y estados pasados son independientes. Formalmente,

, Si ambos lados de la ecuación están bien definidos.

Los valores posibles de X i formar un conjunto numerable S llamado el espacio de estados de la cadena.

Las cadenas de Markov se describen a menudo por un grafo dirigido , donde los bordes están marcados por las probabilidades de pasar de un estado a los otros estados.

Variaciones [ editar ]

Procesos de Markov en tiempo continuo    tienen un índice continuo. Cadenas de Markov en tiempo homogénea (o cadenas de Markov estacionario ) son procesos en los que

para toda n . La probabilidad de la transición es independiente de n .

Una cadena de Markov de orden m (o una cadena de Markov con memoria m ), donde m es finito, es un proceso de satisfacer

En otras palabras, el estado futuro depende de los últimos metros estados. Es posible construir una cadena ( Y n ) a partir de ( X n ) que tiene la propiedad de Markov "clásico" tomando como espacio de estados las ordenadas m -tuplas de X los valores, es decir. Y n = ( X n , X n - 1 , ..., X n - m 1 ).

Ejemplo [ editar ]Artículo principal: Ejemplos de cadenas de Markov

Un diagrama de estados para un sencillo ejemplo se muestra en la figura de la derecha, mediante un grafo dirigido de imaginar las transiciones de estado . Los estados representan ya sea una bolsa de valores hipotética está exhibiendo unmercado en alza , mercado a la baja , o se ha estancado la tendencia del mercado durante una semana determinada.Según la figura, una semana toro es seguida por otra semana toro 90% de las veces, una semana oso 7,5% del tiempo, y una semana estancada, el 2,5% del tiempo. Distintivo del espacio de estados {1 = toro, 2 = oso, 3 = estancada} lamatriz de transición para este ejemplo es

La distribución en estados puede ser escrita como una fila estocástico vector x con la relación x ( n  + 1)  =  x ( n ) P . Así que si en el momento n el sistema está en el estado 2 (oso), a continuación, tres períodos de tiempo más tarde, en el tiempo n  + 3 la distribución es

El uso de la matriz de transición es posible calcular, por ejemplo, la fracción de largo plazo de la semana durante la cual el mercado está estancado, o el número promedio de semanas que tardará en pasar de un estancamiento a un mercado alcista. El uso de las probabilidades de transición, las probabilidades de estado estable indican que el 62,5% de semana estará en un mercado alcista, 31.25% de semana estará en un mercado bajista y 6,25% de semanas estará estancada, ya que:

Un desarrollo minucioso y muchos ejemplos se pueden encontrar en la monografía en línea Meyn y Tweedie 2005. [ 6 ]

El apéndice de Meyn 2007, [ 7 ] También disponible en línea, contiene un Meyn abreviada y Tweedie.

Una máquina de estado finito se puede utilizar como una representación de una cadena de Markov. Suponiendo una secuencia de independientes e idénticamente distribuidos señales de entrada (por ejemplo, símbolos de un alfabeto binario elegido por sacudidas de la moneda), si la máquina está en el estado y en el momento n , entonces la probabilidad de que se traslada al estado x en el tiempo n  + 1 depende sólo del estado actual.

Aplicaciones [ edit ]

Las investigaciones han reportado la aplicación y utilidad de las cadenas de Markov en una amplia gama de temas tales como la física, la química, la medicina, la música, teoría de juegos y deportes.

Física [ edit ]

Sistemas de Markov aparecen ampliamente en la termodinámica y la mecánica estadística , siempre que se utilicen probabilidades para representar detalles desconocidos o no modeladas del sistema, si se puede suponer que la dinámica es invariante en el tiempo, y que es necesario tener en cuenta que sin antecedentes de interés no esté ya incluido en la descripción del estado. [ cita requerida ]

Química [ edit ]

La cinética de Michaelis-Menten. La enzima (E) se une a un sustrato (S) y produce un producto (P). Cada reacción es un estado de transición en una cadena de Markov.

La química es a menudo un lugar en el que las cadenas de Markov y procesos de Markov de tiempo continuo son especialmente útiles debido a que estos sistemas físicos simples tienden a satisfacer la propiedad de Markov bastante bien. El modelo clásico de la actividad enzimática, la cinética de Michaelis-Menten , se puede ver como una cadena de Markov, donde en cada paso de tiempo la reacción procede en una cierta dirección. Mientras Michaelis-Menten es bastante sencillo, redes de reacción mucho más complicada también se pueden modelar con cadenas de Markov.

Un algoritmo basado en una cadena de Markov también se utiliza para enfocar el crecimiento basado en el fragmento de los productos químicos en silico hacia una clase deseada de compuestos tales como medicamentos o productos naturales. [ 14 ] Como se cultiva una molécula, un fragmento se selecciona del naciente molécula como el estado "actual". No es consciente de su pasado (es decir, no es consciente de lo que ya está unido a ella). A continuación, pasa al siguiente estado cuando un fragmento se une a él. Las probabilidades de transición son entrenados en bases de datos de auténticas clases de compuestos.

También, el crecimiento (y composición) de los copolímeros se pueden modelar utilizando cadenas de Markov. Sobre la base de las relaciones de reactividad de los monómeros que componen la cadena de polímero en crecimiento, composición de la cadena puede ser calculada (por ejemplo, si monómeros tienden a añadir en forma alternada o en tramos largos de la misma monómero). Debido a efectos estéricos , de segundo orden efectos de Markov también pueden desempeñar un papel en el crecimiento de algunas cadenas de polímero.

Del mismo modo, se ha sugerido que la cristalización y el crecimiento de algunos epitaxiales superpuesta materiales de óxido se pueden describir con precisión por cadenas de Markov. [ 15 ]

Testing [ edit ]

Varios teóricos han propuesto la idea de la prueba estadística de la cadena de Markov (MCST), un método para que conjunta a las cadenas de Markov para formar una " manta de Markov", la organización de estas cadenas en varias capas recursivas (" fabricación de obleas ") y la producción de la prueba de conjuntos-muestras más eficientes -como un reemplazo para la prueba exhaustiva. MCSTs también tienen usos en las redes basadas en el estado temporal; Chilukuri et al 's. Documento titulado "Redes temporales Razonamiento Incertidumbre de Evidencia Fusión con aplicaciones para la detección de objetos y Seguimiento" (ScienceDirect) da un fondo y estudio de caso para la aplicación de MCSTs a una gama más amplia de aplicaciones.

Ciencias de la Información [ edit ]

Las cadenas de Markov se utilizan en todo el procesamiento de información. Claude Shannon famoso artículo 1948 Una Teoría Matemática de la Comunicación , que en un solo paso creado el campo de la teoría de la información , se abre al introducir el concepto de entropía a través de Markov modelado del idioma Inglés. Tales modelos idealizados pueden capturar muchas de las regularidades estadísticas de los sistemas. Incluso sin describir la estructura completa del sistema perfectamente, tales modelos de señal pueden hacer posible muy efectivade compresión de datos a través de codificación de entropía técnicas tales como la codificación aritmética . También permiten efectiva estimación de estado y reconocimiento de patrones .Cadenas de Markov también juegan un papel importante en el aprendizaje por refuerzo .

Las cadenas de Markov son también la base de modelos ocultos de Markov , que son una herramienta importante en campos tan diversos como las redes telefónicas (que utilizar elalgoritmo de Viterbi para corrección de errores), reconocimiento de voz y la bioinformática .

La teoría de colas [ edit ]

Las cadenas de Markov son la base para el tratamiento analítico de colas ( teoría de colas ). Agner Krarup Erlang inició el tema en 1917. [ 16 ] Esto hace que sean críticos para optimizar el rendimiento de las redes de telecomunicaciones, donde los mensajes a menudo tienen que competir por los recursos limitados (como como ancho de banda). [ 7 ]

Aplicaciones de Internet [ editar ]

El PageRank de una página web tal como se utiliza por Google se define por una cadena de Markov. [ 17 ] Es la probabilidad de estar en la página  en la distribución estacionaria en la siguiente cadena de Markov en todas las páginas web (conocidos). Si  es el número de páginas conocidas, y una página  tiene  enlaces a ella entonces 

tiene probabilidad de transición  para todas las páginas que están vinculados a ellos y  para todas las páginas que no están vinculados a. El parámetro  se toma para ser alrededor de 0,85. [ 18 ]

Modelos de Markov también se han utilizado para analizar el comportamiento de navegación web de los usuarios. Enlace web transición de un usuario en un sitio web en particular puede ser modelado utilizando modelos de Markov de primer o segundo orden y se puede utilizar para hacer predicciones respecto a la navegación futuro y para personalizar la página web para un usuario individual.

Estadísticas [ editar ]

Métodos de la cadena de Markov también se han convertido en muy importante para la generación de secuencias de números aleatorios para reflejar con precisión muy complicadas distribuciones de probabilidad deseados, a través de un proceso llamado cadena de Markov Monte Carlo (MCMC). En los últimos años este ha revolucionado la viabilidad de inferencia bayesiana métodos, lo que permite una amplia gama de distribuciones posteriores que se desea simular y sus parámetros encontrado numéricamente.

Economía y finanzas [ edit ]

Las cadenas de Markov se utilizan en finanzas y economía para modelar una variedad de diferentes fenómenos, incluyendo los precios de los activos y caídas de los mercados. La primera modelo financiero para utilizar una cadena de Markov era de Prasad et al. en 1974. [ 19 ] Otra fue el modelo de cambio de régimen James D. Hamilton (1989), en el que se utiliza una cadena de Markov para modelar interruptores entre períodos de alta volatilidad y la baja volatilidad de los rendimientos de los activos. [ 20 ] Un ejemplo más reciente es el de Markov Switching Multifractal modelo de precios de activos, que se basa en la comodidad de los modelos de cambio de régimen anteriores. [ 21 ] Se utiliza un arbitrariamente grande cadena de Markov para impulsar el nivel de volatilidad de los rendimientos de los activos.

Macroeconomía dinámica fuertemente utiliza cadenas de Markov. Un ejemplo es utilizar las cadenas de Markov a precios exógenamente modelo de participación (acciones) en un equilibrio general de ajuste. [ 22 ]

Ciencias sociales [ editar ]

Las cadenas de Markov se utilizan generalmente para describir dependientes de la trayectoria argumentos, en los que las configuraciones estructurales actuales condicionan los resultados futuros. Un ejemplo es la reformulación de la idea, originalmente por Karl Marx 's Das Kapital , empatando el desarrollo económico a la subida de capitalismo . En la investigación actual, es común el uso de una cadena de Markov para modelar cómo una vez que un país alcanza un determinado nivel de desarrollo económico, la configuración de los factores estructurales, como el tamaño del comercial burguesía , la relación de las zonas urbanas a la residencia rural, la tasa de de política de movilización, etc, va a generar una mayor probabilidad de transición deautoritario al democrático régimen. [ 23 ]

Biología matemática [ edit ]

Cadenas de Markov también tienen muchas aplicaciones en modelos biológicos, en particular los procesos de población , que son útiles en los procesos de modelado que son (por lo menos) análoga a las poblaciones biológicas. La matriz de Leslie es un ejemplo de ello, aunque algunas de sus entradas no son probabilidades (que puede ser mayor que 1). Otro ejemplo es el modelado de la forma celular en la división de láminas de células epiteliales . [ 24 ] Sin embargo, otro ejemplo es el estado de los canales iónicos en membranas celulares.

Cadenas de Markov se utilizan también en las simulaciones de la función cerebral, tales como la simulación de la neocorteza del mamífero. [ 25 ]

Genética [ editar ]

Las cadenas de Markov se han utilizado en la genética de poblaciones con el fin de describir el cambio en la frecuencia de los genes en las pequeñas poblaciones afectadas por la deriva genética , por ejemplo, en la ecuación de difusión método descrito por Motoo Kimura . [ cita requerida ]

Juegos [ editar ]

Cadenas de Markov se pueden utilizar para modelar muchos juegos de azar. Juegos de los niños de la oca y " Hi Ho! Cherry-O ", por ejemplo, se representan exactamente por cadenas de Markov. En cada turno, el jugador comienza en un estado determinado (en un cuadrado dado) y desde allí ha fijado probabilidades de trasladarse a otros estados (cuadrados).

Música [ editar ]

Las cadenas de Markov se emplean en la composición de música algorítmica , sobre todo en el software de programas como CSound , Max o SuperCollider . En una cadena de primer orden, los estados del sistema se convierten en valores de nota o tono, y un vector de probabilidad para cada nota se construye, completando una matriz de probabilidad de transición (ver más abajo). Un algoritmo se construye para producir y valores de las notas de salida basado en los coeficientes de la matriz de transición, que podrían ser MIDI valores de las notas, la frecuencia ( Hz ), o cualquier otra deseable métrica. [ 26 ]

Matriz de primera orden

Nota La C ♯ E ♭

La 0.1 0,6 0,3

C ♯ 0.25 ,05 0.7

E ♭ 0.7 0,3 0

Matriz de segundo orden

Nota La D T

AA ,18 0,6 0,22

AD 0.5 0.5 0

AG 0.15 0.75 0.1

DD 0 0 1

DA 0.25 0 0.75

DG 0.9 0.1 0

GG ,4 ,4 0.2

Georgia 0.5 0.25 0.25

GD 1 0 0

Una cadena de Markov de segundo orden puede ser introducido al considerar el estado actual y también al estado anterior, como se indica en la segunda tabla. Superior, n º de pedido cadenas tienden a "agrupar" notas particulares juntos, mientras que 'romper' en otros patrones y secuencias de vez en cuando. Estas cadenas de orden superior tienden a generar resultados con un sentido de frasal estructura, en lugar de la "vagar sin rumbo 'producida por un sistema de primer orden. [ 27 ]

Cadenas de Markov se pueden utilizar estructuralmente, como en el de Xenakis Analogique A y B. [ 28 ] cadenas de Markov se utilizan también en los sistemas que utilizan un modelo de Markov para reaccionar de forma interactiva a la entrada de la música. [ 29 ]

Por lo general, los sistemas musicales necesitan para hacer cumplir las restricciones específicas de control sobre las secuencias de longitud finita que generan, pero las limitaciones de control no son compatibles con los modelos de Markov, ya que inducen dependencias de largo alcance que violan la hipótesis de Markov de memoria limitada. Con el fin de superar esta limitación, se ha propuesto un nuevo enfoque. [ 30 ]

Béisbol [ edit ]

Modelos de cadena de Markov se han utilizado en el análisis de béisbol avanzado desde 1960, aunque su uso es todavía escasa. Cada mitad de la entrada de un partido de béisbol se ajusta al estado de la cadena de Markov cuando se considera el número de corredores y salidas. Durante cualquier turno al bate, hay 24 posibles combinaciones de número de salidas y la posición de los corredores. Marcos Pankin muestra que los modelos de 

cadena de Markov se pueden utilizar para evaluar carreras creadas para ambos jugadores individuales, así como un equipo. [ 31 ] Él también discute varios tipos de estrategias y jugar condiciones: cómo se han utilizado los modelos de cadena de Markov para analizar estadísticas de juego situaciones comoBunting y robo de base y las diferencias cuando se juega en el césped frente a césped artificial . [ 32 ]

Generadores de textos de Markov [ edit ]

Procesos de Markov también se pueden utilizar para generar texto superficialmente real mirando dado un documento de muestra: se utilizan en una variedad de actividades recreativas "generador de parodia de software "(ver prensa disociada , Jeff Harrison, [ 33 ] Mark V Shaney [ 34 ] [ 35 ] ).

Estos procesos también son utilizados por los spammers para inyectar párrafos ocultos de apariencia real al correo electrónico no solicitado y enviar comentarios en un intento de obtener estos mensajes pasado los filtros de spam .

Montaje [ edit ]

Durante el montaje de una cadena de Markov a los datos, las situaciones en que los parámetros de mal describen la situación pueden destacar las tendencias interesantes. [ 36 ] [ 37 ] [1]

Historia [ edit ]

Andrey Markov produjo los primeros resultados (1906) para estos procesos, puramente teórica. Una generalización de los espacios estatales contable infinito fue dada por Kolmogorov(1936). Las cadenas de Markov se relacionan con el movimiento browniano y la hipótesis ergódica , dos temas de física que son importantes en los primeros años del siglo XX. Sin embargo, Markov primero persiguió este en 1906 como parte de su argumento en contra de Pavel Nekrasov, en particular, para hacer el caso de que la ley de los grandes números se puede extender a eventos dependientes. [ 38 ] En 1913, aplicó sus conclusiones a la primera 20.000 cartas de Pushkin Eugene Onegin . [ 38 ] En 1917, la aplicación más práctica de su trabajo fue hecho por Erlang para obtener fórmulas de pérdida de llamada y tiempo de espera en las redes telefónicas. [ 16 ]

Seneta da cuenta de las motivaciones de Markov y el desarrollo temprano de la teoría. [ 39 ] El término "cadena" fue utilizado por Markov (1906) a sugerir una serie de variables dependientes por parejas. [ 40 ]