Цепь Маркова как конечный автомат?


является ли конечный автомат просто реализацией цепи Маркова? В чем разница между ними?

6 61

6 ответов:

цепи Маркова могут быть представлены конечными автоматами. Идея состоит в том, что Марковская цепь описывает процесс, в котором переход в состояние в момент времени t+1 зависит только от состояния в момент времени t. главное иметь в виду, что переходы в Марковской цепи являются вероятностными, а не детерминированными, что означает, что вы не всегда можете с полной уверенностью сказать, что произойдет в момент времени t+1.

статьи Википедии о конечные автоматы имеет подраздел на конечные цепи Маркова процессы, Я бы рекомендовал прочитать это для получения дополнительной информации. Кроме того, статья Википедии о цепи Маркова имеет краткое предложение, описывающее использование конечных автоматов в представлении цепи Маркова. Это гласит:

конечный автомат можно использовать как представление цепи Маркова. Предполагая последовательность независимых и идентично распределенные входные сигналы (например, символы из двоичного файла алфавит выбирается подбрасыванием монет), если машина находится в состоянии y в момент времени n, тогда вероятность того, что он движется к состояние x в момент времени n + 1 зависит только от текущее состояние.

в то время как цепь Маркова является конечным автоматом, она отличается тем, что ее переходы являются стохастическими, т. е. случайными и описываются вероятностями.

Они похожи, но другие объяснения здесь немного неверны. Только конечные цепи Маркова могут быть представлены FSM. Цепи Маркова допускают бесконечное пространство состояний. Как было отмечено, переходы Марковской цепи описываются вероятностями, но также важно отметить, что вероятности перехода могут зависеть только от текущего состояния. Без этого ограничения его можно было бы назвать "дискретным временным стохастическим процессом".

пожалуйста, читайте эти статьи:

связи между вероятностными автоматами и скрытыми Марковскими моделями (Пьер Дюпон) http://www.info.ucl.ac.be/~pdupont / pdupont / pdf / HMM_PA_pres_n4. pdf

[Справочник по теории мозга и нейронных сетей] Скрытые Марковские модели и другие конечные автоматы для обработки последовательностей http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3344&rep=rep1&type=pdf

Я считаю, что это должно ответить на ваш вопрос:

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

и вы на правильном пути-они почти одинаковы, подмножества, надмножества и модификации в зависимости от того, какое прилагательное описывает цепочку или автомат. Автоматы обычно также принимают вход, но я уверен, что были документы, использующие "марковские цепи" с входами.

думаю, гауссово распределение против нормального распространение же идей в разных областях. Автоматы принадлежат информатике, Марков-вероятности и статистике.

Если оставить внутренние рабочие детали в стороне, конечный автомат похож на простое значение, в то время как цепь Маркова похожа на случайную величину (добавьте вероятность поверх простого значения). Поэтому ответ на исходный вопрос-нет, они не одинаковы. В вероятностном смысле цепь Маркова является продолжением конечного автомата.