¿Qué son las cadenas de Markov?

9

Actualmente estoy leyendo algunos documentos sobre el agrupamiento de la cadena de Markov y no puedo ver la diferencia entre una cadena de Markov y un gráfico ponderado dirigido simple.

Por ejemplo, en el artículo Optimización óptima del espacio de estado en las cadenas de Markov , proporcionan la siguiente definición de un CTMC (cadena de Markov de tiempo continuo):

Consideramos un CTMC finito con espacio de estado por una matriz de tasa de transición .S = { x 1 , x 2 , , x n } Q : S × SR +(S,Q)S={X1,X2,...,Xnorte}Q:S×SR+

No mencionan en absoluto la propiedad de Markov y, de hecho, si el peso en los bordes representa una probabilidad, creo que la propiedad de Markov es trivial, ya que la probabilidad depende solo del estado actual de la cadena y no de la ruta que conduce lo.

En otro artículo sobre las propiedades relacionales de la capacidad de iluminación, las cadenas de Markov se definen de manera similar:

Una cadena de Markov se representará como un triplete donde es el conjunto finito de estados de , la matriz de probabilidad de transición que indica la probabilidad de pasar de un estado a otro, y es el distribución de probabilidad inicial que representa la probabilidad de que el sistema comience en un determinado estado.( S , P , π ) S M P πMETRO(S,PAGS,π)SMETROPAGSπ

Nuevamente, no se menciona el pasado, el futuro o la independencia.

Hay un tercer papel Simple O (m logn) Time Markov Chain Lumping donde no solo nunca afirman que los pesos en los bordes son probabilidades, sino que incluso dicen:

En muchas aplicaciones, los valores no son negativos. Sin embargo, no hacemos esta suposición, porque también hay aplicaciones en las que se elige deliberadamente como , por lo que generalmente es negativo.W ( s , s ) - W ( s , S { s } )W(s,s)W(s,s)-W(s,S{s})

Además, se afirma que el agrupamiento debería ser una forma de reducir el número de estados al tiempo que se mantiene la propiedad de Markov (agregando el estado "equivalente" en un estado más grande). Sin embargo, para mí, parece que se trata simplemente de sumar probabilidades y ni siquiera debería garantizar que las peobabilidades resultantes de las transiciones a / desde los estados agregados estén en el rango . Entonces, ¿qué preserva realmente el bulto?[0 0,1]

Entonces, hay dos posibilidades que veo:

  • No entendí qué es una cadena de Markov, o
  • El uso del término cadena de Markov en esos documentos es falso

¿Alguien podría aclarar la situación?

Realmente parece que hay diferentes comunidades que usan ese término y significan cosas muy diferentes. De estos 3 artículos que estoy considerando parece que la propiedad de Markov es trivial o inútil, mientras que mirando un tipo diferente de documentos parece fundamental.

Bakuriu
fuente
Hay toneladas de libros de texto y recursos en Internet que explican (a) qué es una cadena de Markov y (b) cuál es la definición matemática precisa. Esperamos que haga una gran cantidad de investigación y autoestudio antes de preguntar. Entonces, ¿ha consultado alguno de esos recursos? ¿Qué encontraste allí? PD: Supongo que los documentos de la literatura supondrían que conoces la definición de una cadena de Markov, y esas oraciones no necesariamente tienen la intención de ser una definición formal precisa de una cadena de Markov, sino simplemente establecer la notación que usan cuando hablan sobre uno.
DW
Pasado, futuro o independencia son propiedades que siguen, iirc. Sin embargo, debería haber algunas restricciones en el peso; quizás algunas cosas pueden permanecer implícitas, por ejemplo, asignar un peso saliente faltante a un borde que conduce a un estado de hundimiento (ver diferentes definiciones de DFA).
Raphael
44
@DW Sí, lo hice. Lo que encontré es que la noción de la cadena de Markov en el libro de texto parece no tener nada que ver con su concepto tal como se utiliza en dichos documentos. Esto es exactamente por qué estoy preguntando esto.
Bakuriu
44
De nuevo, hay una tercera posibilidad. Creo que el error que está cometiendo es interpretar la declaración en esos documentos como una definición de una cadena de Markov. Supongo que probablemente esa no sea la intención de esas declaraciones. Supongo que los autores suponen que ya está familiarizado con la definición de una cadena de Markov, y solo están tratando de establecer alguna notación (hay varios tipos de notación que puede usar para el mismo concepto). Entonces, eche otro vistazo desde ese punto de vista y vea si encuentra algo que lo contradiga en los documentos (si encuentra alguno, agréguelo a la pregunta).
DW
44
@DW Parece que el OP hizo una investigación decente y estructuró su pregunta de manera aceptable. Sí, podemos usar google para aprender. Pero, ¿has notado cuán altamente clasificados están los sitios de SE en google? Es porque condensamos la información en (generalmente) preguntas simples y bien definidas. Los esfuerzos de colaboración de nuestra comunidad crean contenido muy rico y valioso que, muchas veces, es más útil que las páginas y páginas de información que existen, lo que resulta en un aprendizaje más eficiente.
BAR

Respuestas:

10

nortenorte×norte

Pero el primer artículo define una notación consistente con una cadena de Markov de tiempo continuo, a veces llamada proceso de Markov , mientras que el segundo artículo define una notación consistente con una cadena de Markov de tiempo discreto . Ellos dicen

PAGSπ

[0 0,1]PAGS1π1

No puedo leer el tercer documento, está pagado. Si se requiere que las entradas en cada columna de la matriz sumen 1, entonces son probabilidades y están hablando de cadenas de Markov de tiempo discreto. Si las entradas en cada columna pueden sumar un número arbitrario, las entradas representan tasas, no probabilidades, y están hablando de cadenas de Markov de tiempo continuo.

1

Con las cadenas de Markov de tiempo continuo y de tiempo discreto, la propiedad de Markov está implícita en los pesos de borde constantes (o de manera equivalente, las entradas constantes en la matriz de transición).

Lógica Errante
fuente
8

Las cadenas de Markov vienen en dos sabores: tiempo continuo y tiempo discreto.

Tanto las cadenas de Markov de tiempo continuo (CTMC) como las cadenas de Markov de tiempo discreto (DTMC) se representan como gráficos ponderados dirigidos.

Para los DTMC, las transiciones siempre toman una unidad de "tiempo". Como resultado, no hay elección sobre cuál debería ser su peso en un arco: usted pone la probabilidad de ir a "j" dado que está en "i".

Para los CTMC, el tiempo de transición entre dos estados es necesariamente dado por una variable aleatoria exponencial. Esta es la diferencia clave entre los CTMC y los DTMC: los DTMC siempre tienen un tiempo de transición de unidad. Los CTMC tienen un tiempo de transición aleatorio.

Para un CTMC, la convención generalmente consiste en poner pesos en un arco de acuerdo con la tasa de la variable aleatoria exponencial que va desde el origen hasta el destino. Es decir, la convención es poner tasas en los arcos, no probabilidades.

Tasas negativas

Aunque todos los CTMC que recuerdo estaban representados con tasas positivas en los bordes, las tasas negativas aparecen en el análisis de CTMC.

Digamos que estamos en el estado A, que está conectado a B, C y D como se muestra a continuación.

A -> B (la tasa en A desde B es negativa) A -> C (la tasa en A desde C es negativa) D -> A (la tasa en A desde D es positiva)

Es probable que esto no sea exactamente a lo que se refiere su trabajo; Lo menciono para mostrar que los pesos negativos no son necesariamente ridículos si alguien estaba trabajando con una convención adecuada.

Propiedad Markov

Para DTMC, tienes razón. La propiedad markov se satisface trivialmente. Para los CTMC, la propiedad markov se satisface porque las transiciones están dadas por variables aleatorias exponenciales (que son "sin memoria"). Si las transiciones no fueran dadas por variables aleatorias exponenciales (digamos que eran uniformes), entonces estaríamos hablando de "Cadenas Semi-Markov" o "Procesos Semi-Markov".

Riley
fuente
W(s,s)-W(s,S{s})s
W(s,s)=-W(s,S{s})