Markov链学习记录
前言
博主最近在学习随机过程,深感随机过程之精妙,感想就是,这种普遍规律的发现和数学系统性的总结真的是人类智慧的一大体现,自己心想着要把它学好,于是也尝试着写一下总结一下。
但这篇文章有序性并不是很好,主要是自己总结用的,而且博主个人的知识水平有限,如若不介意,可继续往下看。
文章仅供理解和参考,更权威的解释请看相关书目
Markov链的一步转移概率
\[ P \lbrace X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, … , X_1 = i_1, X_0 = i_0 \rbrace = P_{ij} \]
通俗来讲,公式可方便理解为\(P(将来|现在和过去) = P(将来|现在)\),即过去的状态\(X_0, …, X_{n-1}\)和现在的状态\(X_{n}\)给定的情况下,任意未来状态\(X_{n+1}\)只依赖于现在的状态,这点性质可称为马尔可夫性,可引申为事件的将来和过去互相独立。
其中,
\[ P_{ij} \geq 0, \qquad i,j \geq 0; \qquad \sum_{j=0}^{n}P_{ij}=1, \qquad i=0,1,… \]
以\(P\)记为转移概率\(P_{ij}\)的矩阵,
其中列表示到达的状态,行表示出发的状态,可重复演算推出\(P\)矩阵。
首达概率、有限步到达概率与到达概率
\[ f_{ij}(n):表示从i状态的进行n步后到达状态j的首次到达概率 \] \[ f_{ij}:从i状态转移到j状态不限定步数的首达概率 \] \[ p_{ij}(n):从i状态转移到j状态进行n步后到达的概率 \] 大小关系:\(p_{ij}(n)\)>\(f_{ij}\)>\(f_{ij}(n)\)
常返状态、瞬过状态、互通
\[ 瞬过状态:f_{ii}<1
\] 此时可称i为暂态 \[ 常返状态方程: f_{ii} = 1 = \sum_{n=1}^{∞}f_{ii}(n) \] 在常返状态中,步数\[E(n)=\sum_{n=1}^{∞}nf_{ii}(n)=μ_{i}\] \[ 当μ_{i}<+∞时,称i为正常返, 当μ_{i}=+∞时,称i为零常返
\] 互通概念: \[ 符号表示:i \leftrightarrow j \] 意味着可从i状态迁移到j状态或者相反。
赌徒模型/醉汉模型(简单随机徘徊)
简单随机徘徊:状态空间是一切整数的集合且具有转移概率 \[ P_{i,i+1}=p=1-p, i =0, \pm1,…
\] 用形象的解释的就是一个赌徒参与赌局,以p的概率获胜,1-p的概率失败,其中获胜奖励和失败惩罚相同,比如都为1元。或者是一个醉汉在1条路上前后走动,以p的概率向前1个单位,1-p个单位后退1个单位。试图去理解该模型的状态。 解: 首先,各个状态显然互通,我们试图去求\(\sum_{n=1}^∞P_{00}^{n}\)是否有限,那么就可以知道\(0\)是否为常返状态,也就知道了该模型的普遍意义。
若n为奇数,表示为\(P_{00}^{2n+1}\)时,显然是不可能等于0的,那么就只需要考虑\(P_{00}^{2n}\),即n为偶数的时候。 当n为偶数时,从0状态回到0状态当且仅当在2n局中输赢各一半,那么可得到: \[ P_{00}^{2n}={2n \choose n}p^n(1-p)^n=\frac{(2n)!}{n!n!}(p(1-p))^n, n = 1,2,3… \] 利用Stirling的一个近似,即 \[ n! \sim n^{n+1/2}e^{-n}\sqrt{2\pi} \] 那么 \[ P_{00}^{2n}=\sum_{n=1}^{∞}\frac{(4p(1-p))^n}{\sqrt{\pi n}} \] 显然看分子的话,\((4p(1-p))^n\)只有在p=1/2时整个式子才收敛,因此\(\sum_{n=1}^∞P_{00}^{n}=∞\)当且仅当p=1/2时才成立,于是当p=1/2时,该链为常返,否则为暂态。 由此可以引出二维的时候p=1/2的上述过程为对称随机徘徊,是常返的。但是如果换做高维情况,则都是暂态的(证明暂不展开)。
极限定理
若j是暂态,则\(\forall i\),都有 \[ \sum_{n=1}^{∞}P_{ij}<∞ \] 其含义为,在状态i开始,转移到状态j的期望次数是有限的。因此,对于暂态的j,当\(n\rightarrow ∞\)时,\(P_{ij}^{n} \rightarrow 0\). 以\(μ_{jj}记为返回状态j所需要的期望转移次数,即\)