马尔可夫链和有限状态机是一样的吗？

Question

马尔可夫链和有限状态机是一样的吗？

mathstatisticsstate-machinefsmmarkov-chains

97

有限状态机只是马尔可夫链的一种实现吗？两者之间有什么区别？

- Carson

32

马尔可夫链可以看作是一个以概率为驱动的有限状态机（FSM）。 - Dr. belisarius

1

请阅读以下论文：概率自动机和隐马尔可夫模型之间的联系（作者：Pierre Dupont） 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 - Juan Carlos Kuri Pinto

6个回答

34

尽管马尔可夫链是一个有限状态机，但它的转换是随机的，并且由概率描述。

- Oliver Charlesworth

6

我可以说随机有限状态自动机吗？ - Souradeep Nanda

19

这两者很相似，但是其他的解释在这里略微有误。只有有限的马尔可夫链可以被有限状态机表示。马尔可夫链允许无限状态空间。正如指出的那样，马尔可夫链的转移由概率描述，但是也很重要提到，转移概率只能依赖于当前状态。没有这个限制，它将被称为“离散时间随机过程”。

- Tim Seguine

实际上，我认为它应该被称为“非静态”。 - Michael Tamillow

@Michael 我可能错了，因为我已经有一段时间没有涉及这个话题了，但我认为“静止”是关于时间依赖性的。我可能错了，但那似乎是正交的。 - Tim Seguine

"Process" 通常用于表示“链”的连续时间版本（引用来源：概率论：简明课程，Rozanov），FSM 可以被表示为无限或事件驱动或非确定性。我能想象的除了状态之外唯一的依赖就是时间。 - Michael Tamillow

@Michael，“process”是一个通用术语。它可以是连续时间或离散时间。FSM无法被无限地表示，因为它的名称中有“有限”一词。您提供的链接甚至表明这不是有限状态机。您提出了时间依赖性问题，而在离散时间过程中，序列索引通常被认为是时间。从这个意义上讲，是的，离散时间随机过程将是非平稳的，但这并不足够描述，因为它也可能是连续时间的。我在命名时是在寻找超集，而不是互补。 - Tim Seguine

3

我相信这应该回答了你的问题：

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

而且，你已经有了正确的想法——它们几乎相同，取决于形容词描述链或自动机的子集、超集和修改。自动机通常也会接受输入，但我确信已经有使用“马尔可夫链”输入的论文。

想想高斯分布与正态分布——相同的思想不同的领域。自动机属于计算机科学，马尔可夫属于概率和统计。

- Michael Tamillow

2

我认为大多数答案都不太合适。马尔可夫过程是由一个（概率性的）有限状态机生成的，但并非每个由概率性有限状态机生成的过程都是马尔可夫过程。例如，隐马尔可夫过程基本上与由概率性有限状态机生成的过程相同，但并非每个隐马尔可夫过程都是马尔可夫过程。

- Radons

1

如果不考虑内部工作细节，有限状态机就像一个普通的值，而马尔可夫链就像一个随机变量（在普通值上增加了概率）。因此，对于原问题的答案是否定的，它们并不相同。从概率意义上讲，马尔可夫链是有限状态机的扩展。

- liang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James Thompson · Accepted Answer

马尔科夫链可以用有限状态机来表示。其思想是，马尔科夫链描述了一个过程，其中在时间t+1转移到状态的转移仅依赖于时间t的状态。需要记住的主要事情是，马尔科夫链中的转移是概率性的而不是确定性的，这意味着您不能总是准确地说出在时间t+1会发生什么。

维基百科关于“有限状态机”的文章中有一个关于“有限马尔可夫链过程”的子部分，我建议您阅读以获取更多信息。此外，“马尔可夫链”的维基百科文章简要描述了使用有限状态机来表示马尔可夫链的用途。该句话如下：

有限状态机可以用作马尔科夫链的表示。假设存在一系列独立且相同分布的输入信号（例如，通过抛硬币选择二进制字母符号），如果机器在时间n处于状态y，则它在时间n + 1 转移到状态x的概率仅取决于当前状态。