随机过程
文章仅供理解和参考，更权威的解释请看相关书目
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}pn(1-p)n=\frac{(2n)!}{n!n!}(p(1-p))^n, n = 1,2,3... \] 利用Stirling的一个近似，即 \[ n! \sim n{n+½}e{-n}\sqrt{2\pi} \] 那么 \[ P_{00}{2n}=\sum_{n=1}{∞}\frac{(4p(1-p))^n}{\sqrt{\pi n}} \] 显然看分子的话,\((4p(1-p))n\)只有在p=½时整个式子才收敛，因此\(\sum_{n=1}∞P_{00}^{n}=∞\)当且仅当p=½时才成立，于是当p=½时，该链为常返，否则为暂态。 由此可以引出二维的时候p=½的上述过程为对称随机徘徊，是常返的。但是如果换做高维情况，则都是暂态的（证明暂不展开）。
极限定理¶
若j是暂态，则\(\forall i\),都有 \[ \sum_{n=1}^{∞}P_{ij}<∞ \] 其含义为，在状态i开始，转移到状态j的期望次数是有限的。因此，对于暂态的j，当\(n\rightarrow ∞\)时，\(P_{ij}^{n} \rightarrow 0\). 以\(μ_{jj}记为返回状态j所需要的期望转移次数，即\)