Une chaîne de Markov est-elle identique à une machine à états finis?

Question

Une machine à états finis est-elle simplement une implémentation d'une chaîne de Markov? Quelles sont les différences entre les deux?

Answer 1

Chaînes de Markov peuvent être représentés par des machines à états finis. L'idée est que la chaîne de Markov décrit un processus dans lequel le passage d'un état à l'instant t+1 ne dépend que de l'état au temps t. La principale chose à garder à l'esprit est que les transitions dans une chaîne de Markov sont probabilistes plutôt que déterministe, ce qui signifie que vous ne pouvez pas toujours dire avec certitude ce qui va se passer à l'instant t+1.

Les articles de Wikipédia sur les états Finis de machines a un paragraphe sur les Finis de Markov processus de la chaîne, je vous recommande la lecture de ce pour plus d'informations. Aussi, l'article de Wikipedia sur les chaînes de Markov a une brève phrase décrivant l'utilisation des machines à états finis dans la représentation d'une chaîne de Markov. Que les états:

Une machine à états finis peut être utilisé comme une représentation d'une chaîne de Markov. En supposant une séquence d'indépendants et de identiquement distribuées signaux d'entrée (par exemple, des symboles à partir d'un fichier binaire alphabet choisi par tirage au lance), si la machine est dans un état y au temps n, alors la probabilité qu'il se déplace à l'état x à l'instant n + 1 ne dépend que de la l'état actuel.

Answer 2

Si une chaîne de Markov est une machine à états finis, elle se distingue par ses transitions stochastiques, c'est-à-dire aléatoires, et décrites par des probabilités.

Answer 3

Les deux sont similaires, mais les autres explications ici sont légèrement fausses. Seules les chaînes de Markov FINITE peuvent être représentées par un FSM. Les chaînes de Markov permettent un espace d'états infini. Comme il a été souligné, les transitions d'une chaîne de Markov sont décrites par des probabilités, mais il est également important de mentionner que les probabilités de transition ne peuvent dépendre que de l'état actuel. Sans cette restriction, cela s'appellerait un "processus stochastique temporel discret".

Answer 4

Veuillez lire ces articles:

Les liens entre Probabiliste des Automates et des Modèles de Markov Cachés (Par Pierre Dupont) http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/HMM_PA_pres_n4.pdf

[Le Manuel de Théorie du Cerveau et des Réseaux de Neurones] Les Modèles de Markov cachés et autres Automates d'états Finis pour la Séquence de Traitement http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3344&rep=rep1&type=pdf

Answer 5

En fait, ce que vous prétendez ici à propos d'une chaîne de Markov n'est pas exact à 100%. Vous avez évoqué ici le "processus de Markov de premier ordre". Pour un processus de Markov de second ordre, le prochain état dépendra des états les plus récents des 2 pas de temps, ...... Une machine à états est le cas particulier d'une chaîne de Markov; depuis une chaîne de Markov est de nature stochastique. Une machine d'état, à ma connaissance, est déterministe.