87

有限状态机只是马尔可夫链的实现吗?两者有什么区别?

4

6 回答 6

69

马尔可夫链可以用有限状态机表示。这个想法是马尔可夫链描述了一个过程,其中在时间 t+1 的状态转换仅取决于时间 t 的状态。要记住的主要事情是,马尔可夫链中的转换是概率性的而不是确定性的,这意味着您不能总是完全确定在时间 t+1 会发生什么。

关于有限状态机的维基百科文章有一个关于有限马尔可夫链过程的小节,我建议阅读它以获取更多信息。此外,关于马尔可夫链的维基百科文章有一个简短的句子,描述了使用有限状态机来表示马尔可夫链。这说明:

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

于 2011-02-02T21:56:55.133 回答
31

虽然马尔可夫链是一个有限状态机,但它的特点是它的转变是随机的,即随机的,并且由概率描述。

于 2011-02-02T21:56:19.793 回答
19

两者相似,但这里的其他解释略有错误。只有有限马尔可夫链可以用 FSM 表示。马尔可夫链允许无限的状态空间。正如所指出的,马尔可夫链的转移是用概率来描述的,但同样重要的是要提到转移概率只能取决于当前状态。如果没有这个限制,它将被称为“离散时间随机过程”。

于 2011-08-05T16:55:58.227 回答
3

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

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

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

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

于 2018-07-03T16:21:48.067 回答
1

如果抛开内部工作细节,有限状态机就像一个普通值,而马尔可夫链就像一个随机变量(在普通值之上添加概率)。所以原始问题的答案是否定的,它们不一样。在概率意义上,马尔可夫链是有限状态机的扩展。

于 2013-12-11T11:59:24.857 回答
1

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

于 2019-07-06T22:45:17.140 回答