Mixing
马尔可夫链
 |
本条目需要擴充。（2018年3月25日） |
本條目介紹的是离散时间马尔可夫链。關於连续时间马尔可夫链，請見“连续时间马尔可夫链”。
一个具有两个转换状态的马尔可夫链.
马尔可夫链（英语：Markov chain），又稱離散時間馬可夫鏈（discrete-time Markov chain，縮寫為DTMC[1]），因俄國數學家安德烈·马尔可夫（俄语：Андрей Андреевич Марков）得名，为狀態空間中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作馬可夫性質。马尔科夫链作为实际过程的统计模型具有许多应用。
在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态，也可以保持当前状态。状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的（无论之前漫步路径是如何的）。
目录
1 介绍
2 形式化定义
2.1 变种
3 瞬态演变
4 性质
4.1 可还原性
4.2 周期性
4.3 重现性
4.4 各态历遍性
4.5 律动性
4.6 平稳状态分析和极限分布
4.7 平稳状态分析和时齐马尔可夫链
5 有限状态空间
5.1 稳定分布与特征向量和单纯形的关系
5.2 有限状态空间内的时齐马尔可夫链
5.3 趋向稳定分布的收敛速度
6 可反转马尔可夫链
7 伯努利方案
8 一般的状态空间
8.1 Harris链
8.2 局部交互的马尔可夫链
9 应用
9.1 物理
9.2 化学
9.3 测试
9.4 语音识别
9.5 信息科学
9.6 排队理论
9.7 互联网应用
9.8 统计
9.9 经济和金融
9.10 社会科学
9.11 生物数学
9.12 遗传学
9.13 游戏
9.14 音乐
9.15 棒球
9.16 马尔可夫文本生成器
9.17 信息论
10 Fitting
11 历史
12 隱馬可夫模型
13 参看
14 参考文献
14.1 引用
14.2 来源
15 外部連結
介绍
马尔可夫链是满足马尔可夫性质的随机过程。
形式化定义
马尔可夫链是满足马尔可夫性质的随机变量序列X1, X2, X3, ...，即给出当前状态，将来状态和过去状态是相互独立的。从形式上看，
- 如果两边的条件分布有定义（即如果Pr(X1=x1,...,Xn=xn)>0{displaystyle Pr(X_{1}=x_{1},...,X_{n}=x_{n})>0}
），则Pr(Xn+1=x∣X1=x1,X2=x2,…,Xn=xn)=Pr(Xn+1=x∣Xn=xn){displaystyle Pr(X_{n+1}=xmid X_{1}=x_{1},X_{2}=x_{2},ldots ,X_{n}=x_{n})=Pr(X_{n+1}=xmid X_{n}=x_{n})}
。
Xi的可能值构成的可数集S叫做该链的“状态空间”。
通常用一系列有向图来描述马尔可夫链，其中图n的边用从时刻n的状态到时刻n+1的状态的概率Pr(Xn+1=x∣Xn=xn){displaystyle Pr(X_{n+1}=xmid X_{n}=x_{n})}
这些描述强调了马尔可夫链与初始分布Pr(X1=x1){displaystyle Pr(X_{1}=x_{1})}
![Pr(X_{1}=y)=[x_{1}=y]](https://wikimedia.org/api/rest_v1/media/math/render/svg/f630bd6c1d1563504ad0817cfaa48a0ebe2be938)
![[P]](https://wikimedia.org/api/rest_v1/media/math/render/svg/25d78ad4ad13872df07ac9b02a2574250a0e54fd)
一些状态序列可能会有零概率的事件，对应多连通的图，而我们禁止转移概率为0的边。例如，若a到b的概率非零，但a到x位于图的不同连通分量，那么Pr(Xn+1=b|Xn=a){displaystyle Pr(X_{n+1}=b|X_{n}=a)}
变种
连续时间马尔可夫过程具有连续索引。
时齐马尔可夫链（或静态马尔可夫链）是对于所有n
- Pr(Xn+1=x∣Xn=y)=Pr(Xn=x∣Xn−1=y){displaystyle Pr(X_{n+1}=xmid X_{n}=y)=Pr(X_{n}=xmid X_{n-1}=y),}
- Pr(Xn+1=x∣Xn=y)=Pr(Xn=x∣Xn−1=y){displaystyle Pr(X_{n+1}=xmid X_{n}=y)=Pr(X_{n}=xmid X_{n-1}=y),}
- 的过程。转移概率与n无关。
m阶马尔可夫链（或记忆为m的马尔可夫链），其中m有限，为满足
- Pr(Xn=xn∣Xn−1=xn−1,Xn−2=xn−2,…,X1=x1)=Pr(Xn=xn∣Xn−1=xn−1,Xn−2=xn−2,…,Xn−m=xn−m) for n>m{displaystyle {begin{aligned}{}&Pr(X_{n}=x_{n}mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},dots ,X_{1}=x_{1})\=&Pr(X_{n}=x_{n}mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},dots ,X_{n-m}=x_{n-m}){text{ for }}n>mend{aligned}}}
- Pr(Xn=xn∣Xn−1=xn−1,Xn−2=xn−2,…,X1=x1)=Pr(Xn=xn∣Xn−1=xn−1,Xn−2=xn−2,…,Xn−m=xn−m) for n>m{displaystyle {begin{aligned}{}&Pr(X_{n}=x_{n}mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},dots ,X_{1}=x_{1})\=&Pr(X_{n}=x_{n}mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},dots ,X_{n-m}=x_{n-m}){text{ for }}n>mend{aligned}}}
- 的过程。换句话说，未来状态取决于其前m个状态。It is possible to construct a chain（Yn）from (Xn) which has the 'classical' Markov property by taking as state space the ordered m-tuples of X values, ie. Yn =(Xn, Xn−1, ..., Xn−m+1)。
瞬态演变
用n步从状态i到状态j的概率为
- pij(n)=Pr(Xn=j∣X0=i){displaystyle p_{ij}^{(n)}=Pr(X_{n}=jmid X_{0}=i),}
而单步转移是
- pij=Pr(X1=j∣X0=i).{displaystyle p_{ij}=Pr(X_{1}=jmid X_{0}=i).,}
对于一个时齐马尔可夫链来说：
- pij(n)=Pr(Xk+n=j∣Xk=i){displaystyle p_{ij}^{(n)}=Pr(X_{k+n}=jmid X_{k}=i),}
而
- pij=Pr(Xk+1=j∣Xk=i).{displaystyle p_{ij}=Pr(X_{k+1}=jmid X_{k}=i).,}
n步转移概率满足Chapman-Kolmogorov等式，对任意k使得0 < k < n，
- pij(n)=∑r∈Spir(k)prj(n−k){displaystyle p_{ij}^{(n)}=sum _{rin S}p_{ir}^{(k)}p_{rj}^{(n-k)}}
其中S为此马尔可夫链的状态空间。
边缘分布Pr(Xn = x)为第n次状态的分布。初始分布为Pr(X0 = x)。用一步转移把过程演变描述为
Pr(Xn=j)=∑r∈SprjPr(Xn−1=r)=∑r∈Sprj(n)Pr(X0=r){displaystyle Pr(X_{n}=j)=sum _{rin S}p_{rj}Pr(X_{n-1}=r)=sum _{rin S}p_{rj}^{(n)}Pr(X_{0}=r)}。
注意：上标（n）是索引而非指数。
性质
可还原性
马尔可夫链是由一个条件分布来表示的
- P(Xn+1|Xn){displaystyle P(X_{n+1}|X_{n}),}
这被称为是随机过程中的“转移概率”。这有时也被称作是“一步转移概率”。二、三，以及更多步的转移概率可以导自一步转移概率和马尔可夫性质：
- P(Xn+2|Xn)=∫P(Xn+2,Xn+1|Xn)dXn+1=∫P(Xn+2|Xn+1)P(Xn+1|Xn)dXn+1{displaystyle P(X_{n+2}|X_{n})=int P(X_{n+2},X_{n+1}|X_{n}),dX_{n+1}=int P(X_{n+2}|X_{n+1}),P(X_{n+1}|X_{n}),dX_{n+1}}
同样，
- P(Xn+3|Xn)=∫P(Xn+3|Xn+2)∫P(Xn+2|Xn+1)P(Xn+1|Xn)dXn+1dXn+2{displaystyle P(X_{n+3}|X_{n})=int P(X_{n+3}|X_{n+2})int P(X_{n+2}|X_{n+1}),P(X_{n+1}|X_{n}),dX_{n+1},dX_{n+2}}
这些式子可以通过乘以转移概率并求k−1{displaystyle k-1}
周期性
边缘分布P(Xn){displaystyle P(X_{n})}
- P(Xn+1)=∫P(Xn+1|Xn)P(Xn)dXn{displaystyle P(X_{n+1})=int P(X_{n+1}|X_{n}),P(X_{n}),dX_{n}}
这是Frobenius-Perron equation的一个版本。这时可能存在一个或多个状态分布π{displaystyle pi }
- π(X)=∫P(X|Y)π(Y)dY{displaystyle pi (X)=int P(X|Y),pi (Y),dY}
其中Y{displaystyle Y}
平稳分布是否存在，以及如果存在是否唯一，这是由过程的特定性质决定的。“不可约”是指每一个状态都可来自任意的其它状态。当存在至少一个状态经过一个固定的时间段后连续返回，则这个过程被称为是“周期的”。
重现性
各态历遍性
具有重现性而不具有周期性叫做遍历的。重现性包括局部重现性。
律动性
平稳状态分析和极限分布
平稳状态分析和时齐马尔可夫链
有限状态空间
若状态空间是有限的，则转移概率分布可以矩阵表示，该矩阵称为转移矩阵，记为P。其中处于(i,j){displaystyle (i,j)}
- pij=Pr(Xn+1=j∣Xn=i).{displaystyle p_{ij}=Pr(X_{n+1}=jmid X_{n}=i).,}
由于P的每一行各元素之和为1，且P中所有的元素都是非负的，因此P是一个右随机矩阵。
稳定分布与特征向量和单纯形的关系
稳定分布π是一个（行）向量，它的元素都非负且和为1，不随施加P操作而改变，定义为
- πP=π.{displaystyle pi mathbf {P} =pi .,}
通过将这个定义与特征向量进行比较，我们看到，这两个概念是相关的，并且
- π=e∑iei{displaystyle pi ={frac {e}{sum _{i}{e_{i}}}}}
是由（∑iπi=1{displaystyle textstyle sum _{i}pi _{i}=1}
稳定分布πi{displaystyle textstyle pi _{i}}
有限状态空间内的时齐马尔可夫链
对于一个离散状态空间，k{displaystyle k}
如果转移矩阵P{displaystyle mathbf {P} }
limk→∞Pk=π∗{displaystyle lim _{krightarrow infty }mathbf {P} ^{k}=pi ^{*}},
独立于初始分布π{displaystyle pi }
正的转移矩阵（即矩阵的每一个元素都是正的）是不可约和非周期的。矩阵被称为是一个随机矩阵，当且仅当这是某个马尔可夫链中转移概率的矩阵。
注意：在上面的定式化中，元素(i,j){displaystyle (i,j)}
转移概率独立于过去的特殊况为熟知的Bernoulli scheme。仅有两个可能状态的Bernoulli scheme被熟知为伯努利过程
趋向稳定分布的收敛速度
可反转马尔可夫链
可反转马尔可夫链类似于应用贝叶斯定理来反转一个条件概率：
- Pr(Xn=i∣Xn+1=j)=Pr(Xn=i,Xn+1=j)Pr(Xn+1=j)=Pr(Xn=i)Pr(Xn+1=j∣Xn=i)Pr(Xn+1=j).{displaystyle {begin{aligned}Pr(X_{n}=imid X_{n+1}=j)&={frac {Pr(X_{n}=i,X_{n+1}=j)}{Pr(X_{n+1}=j)}}\&={frac {Pr(X_{n}=i)Pr(X_{n+1}=jmid X_{n}=i)}{Pr(X_{n+1}=j)}}.end{aligned}}}
以上就是反转的马尔可夫链。因而，如果存在一个π，使得：
- πipij=πjpji.{displaystyle pi _{i}p_{ij}=pi _{j}p_{ji}.,}
那么这个马尔可夫链就是可反转的。
这个条件也被称为细致平衡（detailed balance）条件。
对于所有的i求和：
- ∑iπipij=πj{displaystyle sum _{i}pi _{i}p_{ij}=pi _{j},}
所以，对于可反转马尔可夫链，π总是一个平稳分布。
伯努利方案
伯努利方案是马尔可夫链的一种特殊情形，其转移概率矩阵有相同的行，即下一状态均匀独立于当前状态（除了独立于过往状态以外）。 仅有两个可能状态的伯努利方案是伯努利过程。
一般的状态空间
对于一般状态空间上的马尔可夫链的概述，详见文章状态空间可测的马尔可夫链。
Harris链
局部交互的马尔可夫链
应用
物理
马尔可夫系统广泛出现在热力学和统计力学中，
化学
测试
语音识别
隐马尔科夫模型是大多数现代自动语音识别系统的基础。
信息科学
排队理论
互联网应用
谷歌所使用的网页排序算法（PageRank）就是由马尔可夫链定义的。如果N{displaystyle N}
马尔可夫模型也被应用于分析用户浏览网页的行为。一阶或者二阶的马尔可夫模型可以用于对一个用户从某一网络链接转移到另一链接的行为进行建模，然后这些模型可以用于对用户之后的浏览行为进行预测。
统计
经济和金融
马尔科夫链可以应用于金融与经济中一系列现象的建模，包括资产价值与市场冲击。1974年Prasad等人第一次应用马尔科夫链于金融模型[2]，另一个是James D. Hamilton 1989年应用的机制转换模型[3]，其中马尔科夫链用来对高GDP增长速度时期与低GDP增长速度时期（换言之，经济扩张与紧缩）的转换进行建模[4]。
社会科学
生物数学
马尔可夫链也有众多的生物学应用，特别是增殖过程，可以帮助模拟生物增殖过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测（見哈代-溫伯格定律。）
遗传学
游戏
音乐
棒球
马尔可夫文本生成器
马尔可夫过程，能为给定样品文本，生成粗略，但看似真实的文本：他们被用于众多供消遣的“模仿生成器”软件。马尔可夫链还被用于谱曲。
信息论
用于计算马尔可夫信源的极限熵
Fitting
历史
俄国数学家安德雷·安德耶维齐·马尔可夫.
马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由俄國數學家柯尔莫果洛夫（俄语：Андре́й Никола́евич Колмого́ров）在1936年给出的。马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。
隱馬可夫模型
- 語音辨識
参看
- 马尔可夫性质
- 马尔可夫
- 隐马尔可夫模型
- 马尔科夫蒙特卡洛
参考文献
引用
^ Norris, James R. Markov chains. Cambridge University Press. 1998.
^ Prasad, NR; RC Ender; ST Reilly; G Nesgos. Allocation of resources on a minimized cost basis. 1974 IEEE Conference on Decision and Control including the 13th Symposium on Adaptive Processes. 1974, 13: 402–3. doi:10.1109/CDC.1974.270470. （原始内容存档于2015-02-12）.
^ Hamilton, James . A new approach to the economic analysis of nonstationary time series and the business cycle. Econometrica (Econometrica, Vol. 57, No. 2). 1989, 57 (2): 357–84. JSTOR 1912559. doi:10.2307/1912559.
^ Hamilton, James . A new approach to the economic analysis of nonstationary time series and the business cycle. Econometrica (Econometrica, Vol. 57, No. 2). 1989, 57 (2): 357–84. JSTOR 1912559. doi:10.2307/1912559.
来源
.mw-parser-output .refbegin{font-size:90%;margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{list-style-type:none;margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li,.mw-parser-output .refbegin-hanging-indents>dl>dd{margin-left:0;padding-left:3.2em;text-indent:-3.2em;list-style:none}.mw-parser-output .refbegin-100{font-size:100%}
- A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135-156, 1906.
- A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
- Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 978-0-89871-296-4. （See Chapter 7.）
- J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 978-0-471-52369-7.
外部連結
- 免费的《概率论入门》书中有关马尔可夫链的章节
世界上最大的矩阵计算（Google's PageRank as the stationary distribution of a random walk through the Web.）[永久失效連結]
Disassociated Press in Emacs approximates a Markov process
[1] Markov chains used to produce semi-coherent English.
有关马尔可夫链的资源列表[永久失效連結]
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
分类
|
Comments
Post a Comment