3,094
个编辑
更改
跳到导航
跳到搜索
第9行：
第9行： + + + + + + + + + + + + + + + + + + + + 第15行：
第35行： + 第24行：
第45行： − 此外，当时间是连续的但状态空间仍是离散的且满足马尔科夫性质，称这类随机过程为连续时间马尔科夫链，具体定义为+
→离散（或连续）时间马尔科夫链的定义
==离散（或连续）时间马尔科夫链的定义==
==离散（或连续）时间马尔科夫链的定义==
===例子===
====流网络====
假设一个[[流网络]]模型，如图所示，其中节点代表不同的管道交汇处，连边代表不同的流管道，连边上的权重代表流量，方向代表水流的方向。
考虑一个水分子在此流网络中流动，在每一个节点处，它会以一定的概率顺不同的连边流向下一个节点。如果我们将粒子可能处于不同的节点看作是该粒子的不同状态，即定义状态空间[math]S=\{1,2,\cdots,N\}[/math]，同时假定每一时刻粒子必然处于某一个节点，且不会在连边处停留，则我们可以用从任意节点[math]i[/math]出发，到任意另外的节点[math]j[/math]的跳转概率[math]p_{ij}\equiv Pr(X_{t+1}=j|X_t=i)= f_{ij}/\sum_{j=1}^Nf_{ij}[/math]描述该粒子的行为，其中[math]f_{ij}[/math]为连边i到j上面的流量。显然，这个跳转概率与粒子在[math]<t[/math]的时间步位于哪一个节点无关，因此这是一个马尔可夫过程。
====高尔顿钉板====
这是英国科学家高尔顿（Francis Galton）发明的一种物理装置。如图所示，这个有趣的装置由一大堆钉子按照三角形形状规则排列而形成的一个钉板。钉板的上侧有一个开口，你可以从这个开口投放小钢球进来，下面则是由若干个柱状的凹槽构成，每个凹槽可以把钢球接住，并盛放起来。实验的时候，你可以从上面的开口投放小球，小球就会下落，从而碰撞到一些钉子，然后坠入底部的凹槽之内。由于小球每碰撞一次钉子，就可能从该钉子的左侧下落，或从右侧下落，进而再碰撞另一个钉子，如此循环。于是，最终落到槽中的小球就可能堆积出一个小球的分布，这个分布会形成一种中间凸起，两边凹陷的钟形曲线。这个装置是由英国科学家高尔顿发明的，用以说明概率论中的中心极限定理，因而人们就叫它“高尔顿钉板”。
小球的坠落过程实际上可以被看作是一个马尔科夫链，自然也能够用状态转移图来表示。为了方便起见，我们仅仅考虑由6颗钉子，4个底部凹槽构成的高尔顿钉板来作为示例。那么，一个小球在不同的钉子之间跳跃就可以由图b所示的状态转移图表示。其中，1-6号节点对应了6颗钉子，它表示了下落的小钢球所处的状态——即刚好下落到哪一颗钉子的位置。随着下落，小球就会从上面的状态进入到下面的状态。7~10号节点对应底部的4个凹槽。一旦进入这4个节点中的任意一个，小球就不动了，因此小球就停留在当前这个节点。
图b是一棵向下展开的树状结构，1号节点是树根，7、8、9、10号节点是树叶。随着小球一个时间步一个时间步的下落，它所处的树的深度也会相应的加深，并且，如果t=0时间步小球位于根节点的深度定义为0的话，那么，小球所处的深度就刚好对应了它下落的时间步t。
图b中每一条连边对应了从一个钉子落向另一颗钉子的跳转过程。由于随机波动，小球抵达每个钉子的时候可能稍稍偏左或者稍稍偏右，这就导致它有可能向左也可能向右继续下落。因此，从每个节点出发，向左或向右的跳转概率都是1/2。到了底层的叶节点之后，小球就落入了槽中，这样，由于小球不再运动，因此从这些叶节点出发的转移概率就只有一个指向自己的连边，且转移概率为1。
事实上，这张状态转移图完整表示了每一个小球下落以后的随机行为。虽然，小球在每一时刻与哪一颗钉子碰撞，最终落入哪一个凹槽是不确定的，但是每一时刻的概率行为却是确定的：从任意节点出发，它进一步往左或往右下落的概率都是1/2。
====Yahtzee的骰子游戏====
首先，介绍一个经典的骰子游戏——Yahtzee。在游戏中共有5个六面均匀的骰子，游戏参与者至多有三次投掷机会。为了简化，此处假设目标是使得所有骰子的结果相同（称为获得Yahtzee）。具体规则是在第一次和第二次投掷后，可以仅重新投掷部分数量骰子，而保持其他骰子不动。例如，第一次投掷结果为11234，由于有两个1，可以保持对应的两个骰子不动，重新投掷234对应的三个骰子。<ref name=":6">http://www.stat.yale.edu/~pollard/Courses/251.spring2013/Handouts/Chang-MarkovChains.pdf</ref>
首先，介绍一个经典的骰子游戏——Yahtzee。在游戏中共有5个六面均匀的骰子，游戏参与者至多有三次投掷机会。为了简化，此处假设目标是使得所有骰子的结果相同（称为获得Yahtzee）。具体规则是在第一次和第二次投掷后，可以仅重新投掷部分数量骰子，而保持其他骰子不动。例如，第一次投掷结果为11234，由于有两个1，可以保持对应的两个骰子不动，重新投掷234对应的三个骰子。<ref name=":6">http://www.stat.yale.edu/~pollard/Courses/251.spring2013/Handouts/Chang-MarkovChains.pdf</ref>
===定义===
Yahtzee例子中时间和状态空间均是离散的且满足马尔科夫性质，称这类随机过程为离散时间马尔科夫链（简称马尔科夫链，Markov chain），严格的数学定义如下：
Yahtzee例子中时间和状态空间均是离散的且满足马尔科夫性质，称这类随机过程为离散时间马尔科夫链（简称马尔科夫链，Markov chain），严格的数学定义如下：
此外，当时间是连续的但状态空间仍是离散的且满足马尔科夫性质，称这类随机过程为连续时间马尔科夫链，具体定义为：
称状态空间<math>S=\{1,2,\ldots\}</math>上的随机过程<math>\{X_t,\ t\geq 0\}</math>是'''连续时间马尔科夫链'''，若满足
称状态空间<math>S=\{1,2,\ldots\}</math>上的随机过程<math>\{X_t,\ t\geq 0\}</math>是'''连续时间马尔科夫链'''，若满足