¿Es una cadena de Markov la misma que una máquina de estado finito?

Question

¿Es una máquina de estado finito solo una implementación de una cadena de Markov? ¿Cuáles son las diferencias entre los dos?

Answer 1

Las cadenas de Markov pueden estar representadas por máquinas estatales finitas. La idea es que una cadena de Markov describe un proceso en el que la transición a un estado en el tiempo t+1 depende solo del estado en el momento t. Lo principal a tener en cuenta es que las transiciones en una cadena de Markov son probabilísticas más que deterministas, lo que significa que no siempre se puede decir con perfecta certeza lo que sucederá en el tiempo T+1.

Los artículos de Wikipedia en Máquinas de estado finito tiene una subsección en Procesos de cadena de Markov finitos, Recomendaría leer eso para más información. Además, el artículo de Wikipedia en Cadenas de Markov tiene una breve oración que describe el uso de máquinas de estado finitas para representar una cadena de Markov. Que dice:

Una máquina de estado finita se puede usar como representación de una cadena de Markov. Suponiendo una secuencia de señales de entrada independientes e idénticamente distribuidas (por ejemplo, símbolos de un alfabeto binario elegido por lanzamientos de monedas), si la máquina está en estado y en el tiempo n, entonces la probabilidad de que se mueva a estado X en el tiempo n + 1 depende solo del estado actual.

Answer 2

Si bien una cadena de Markov es una máquina de estado finita, se distingue por sus transiciones que son estocásticas, es decir, aleatorias y descrita por las probabilidades.

Answer 3

Los dos son similares, pero las otras explicaciones aquí están un poco incorrectas. Solo las cadenas finitas de Markov pueden estar representadas por un FSM. Las cadenas de Markov permiten un espacio de estado infinito. Como se señaló, las transiciones de una cadena de Markov se describen por probabilidades, pero también es importante mencionar que las probabilidades de transición solo pueden depender del estado actual. Sin esta restricción, se llamaría un "proceso estocástico de tiempo discreto".

Answer 4

Lea estos documentos:

Enlaces entre autómatas probabilísticos y modelos ocultos de Markov (por Pierre DuPont)http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/hmm_pa_pres_n4.pdf

El manual de teoría del cerebro y redes neuronales] modelos ocultos de Markov y otros autómatas de estado finito para el procesamiento de secuenciashttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.85.3344&rep=rep1&type=pdf

Answer 5

Creo que esto debería responder a tu pregunta:

https://en.wikipedia.org/wiki/probabilistic_automaton

Y, está en la idea correcta: son casi los mismos, subconjuntos, superconjuntos y modificaciones dependiendo de qué adjetivo describe la cadena o el autómata. Los autómatas generalmente también toman una entrada, pero estoy seguro de que ha habido documentos que utilizan 'cadenas de Markov' con entradas.

Piense en distribución gaussiana versus distribución normal: mismas ideas diferentes campos. Los autómatas pertenecen a la informática, Markov pertenece a la probabilidad y las estadísticas.

Answer 6

Si deja a un lado los detalles internos de trabajo, la máquina de estado finito es como un valor simple, mientras que la cadena de Markov es como una variable aleatoria (agregue la probabilidad además del valor simple). Entonces, la respuesta a la pregunta original es no, no son lo mismo. En el sentido probabilístico, la cadena de Markov es una extensión de la máquina de estado finito.

Answer 7

Creo que la mayoría de las respuestas no son apropiadas. Un proceso de Markov es generado por una máquina de estado finito (probable), pero no todos los procesos generados por una máquina de estado finito probable son un proceso de Markov. Por ejemplo, los procesos ocultos de Markov son básicamente los mismos que los procesos generados por las máquinas de estado finitas probabilísticas, pero no todos los procesos de Markov ocultos son un proceso de Markov.