文章目录

• 随机过程 Markov 链（上）
• • 基本概念
  • • n 步转移概率 C-K 方程
  • 状态的分类及性质

随机过程 Markov 链（上）

基本概念

有一类过程，具备所谓的 ”无后效性“（Markov 性），即要确定过程将来的状态，只要知道它此刻的情况就足够了，并不需要对它以往状况的认识，这类过程称为 Markov 过程。这里我们将介绍 Markov 过程最简单的两种类型：离散时间的 Markov 链和连续时间的 Markov 链。

Markov 链：随机过程 {Xn,n=0,1,2⋯}\{X_n,\,n=0,\,1,\,2\cdots\}{Xn​,n=0,1,2⋯} 称为 Markov 链，若它只取有限个或可列个值（一般以自然数集来表示），并且对任意的 $n\ge 0$ ，及任意状态 i,j,i0,i1,⋯,in−1i,\,j,\,i_0,\,i_1,\,\cdots,\,i_{n-1}i,j,i0​,i1​,⋯,in−1​ ，有：
P(Xn+1=j∣Xn=in,Xn−1=in−1,⋯,X0=i0)=P(Xn+1=j∣Xn=in)P(X_{n+1}=j\,|\,X_{n}=i_{n},\,X_{n-1}=i_{n-1},\,\cdots,\,X_0=i_0) \\ =P(X_{n+1}=j\,|\,X_{n}=i_{n}) P(Xn+1​=j∣Xn​=in​,Xn−1​=in−1​,⋯,X0​=i0​)=P(Xn+1​=j∣Xn​=in​)
称 {0,1,2,⋯}\{0,\,1,\,2,\,\cdots\}{0,1,2,⋯} 为该过程的状态空间，将来的状态 Xn+1X_{n+1}Xn+1​ 只与当前的状态 XiX_iXi​ 有关

转移概率：称条件概率 P(Xn+1=j∣Xn=in)P(X_{n+1}=j\,|\,X_{n}=i_{n})P(Xn+1​=j∣Xn​=in​) 为 Markov 链的一步转移概率，简称转移概率，记为 p0p_0p0​ ；

时齐 Markov 链：当 Markov 链的转移概率 pij=P(Xn+1=j∣Xn=in)p_{ij}=P(X_{n+1}=j\,|\,X_{n}=i_{n})pij​=P(Xn+1​=j∣Xn​=in​) 只与 $i$ 和 $j$ 有关，而与 $n$ 无关时，称为时齐 Markov 链，我们后边讨论的都是时齐 Markov 链，简称为 Markov 链。

转移矩阵：当 Markov 的状态有限时，称为有限链，否则称为无限链；但不论状态有限还是无限，我们都可以将转移概率写成矩阵的形式，称为转移概率矩阵，一般简称为转移矩阵：
P=pij=[p00p01p02⋯p10p11p12⋯⋮⋮⋮pi0pi1pi2⋯⋮⋮⋮]\boldsymbol{P}=p_{ij}=\begin{bmatrix} p_{00} & p_{01} & p_{02} & \cdots \\ p_{10} & p_{11} & p_{12} & \cdots \\ \vdots & \vdots & \vdots & \\ p_{i0} & p_{i1} & p_{i2} & \cdots \\ \vdots & \vdots & \vdots & \\ \end{bmatrix} P=pij​=​p00​p10​⋮pi0​⋮​p01​p11​⋮pi1​⋮​p02​p12​⋮pi2​⋮​⋯⋯⋯​​

• pij≥0p_{ij}\ge 0pij​≥0 ，$\forall i,j\in S$ ；
• ∑j∈Spij=1\sum\limits_{j\in S}p_{ij}=1j∈S∑​pij​=1 ，每一行的和为 1，即每个状态转移到其他状态（包括自己）的概率之和为 1；

随机矩阵：具有以上两条性质的矩阵称为随机矩阵

下面是几个经典 的 Markov 链的例子：

例：（带吸收壁的随机游动）系统状态为 $0\sim n$ ，代表赌徒在赌博期间所拥有的金钱数量，当他输光或者获得金钱为 $n$ 时，赌博停止，否则他将继续赌博。设每次赌博赌徒将以 $p$ 的概率获得一个金钱，以 $q=1-p$ 的概率失去一个金钱，则转移矩阵为：
P=[1000⋯000q0p0⋯0000q0p⋯000⋮⋮⋮⋮⋮⋮⋮0000⋯q0p0000⋯001](n+1)×(n+1)\boldsymbol{P}=\begin{bmatrix} 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 \\ q & 0 & p & 0 & \cdots & 0 & 0 & 0 \\ 0 & q & 0 & p & \cdots & 0 & 0 & 0 \\ \vdots & \vdots &\vdots & \vdots & & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & q & 0 & p \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ \end{bmatrix}_{(n+1)\times(n+1)} P=​1q0⋮00​00q⋮00​0p0⋮00​00p⋮00​⋯⋯⋯⋯⋯​000⋮q0​000⋮00​000⋮p1​​(n+1)×(n+1)​
例：（带反射壁的随机游动）在上例的基础上，若赌徒输光以后就立刻获得一个金钱的赞助，就好像在一个一侧有壁的直线上做随机游动，则转移矩阵为：
P=[0100⋯000q0p0⋯0000q0p⋯000⋮⋮⋮⋮⋮⋮⋮0000⋯q0p0000⋯001](n+1)×(n+1)\boldsymbol{P}=\begin{bmatrix} 0 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ q & 0 & p & 0 & \cdots & 0 & 0 & 0 \\ 0 & q & 0 & p & \cdots & 0 & 0 & 0 \\ \vdots & \vdots &\vdots & \vdots & & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & q & 0 & p \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ \end{bmatrix}_{(n+1)\times(n+1)} P=​0q0⋮00​10q⋮00​0p0⋮00​00p⋮00​⋯⋯⋯⋯⋯​000⋮q0​000⋮00​000⋮p1​​(n+1)×(n+1)​
例：（自由随机游动）设一个球在全直线上做无限制的随机游动，它的状态为 $0$ ，$\pm 1$ ，$\pm 2$ ，$\cdots$ ，则它仍是一个 Markov 链，并且转移矩阵为：
P=[⋮⋮⋮⋮⋮⋮⋮⋮⋯q0p0⋯0000⋯⋯0q0p⋯0000⋯⋮⋮⋮⋮⋮⋮⋮⋮⋯0000⋯q0p0⋯⋯0000⋯0q0p⋯⋮⋮⋮⋮⋮⋮⋮⋮]\boldsymbol{P}=\begin{bmatrix} & \vdots & \vdots &\vdots & \vdots & & \vdots & \vdots & \vdots & \vdots \\ \cdots & q & 0 & p & 0 & \cdots & 0 & 0 & 0 & 0 & \cdots \\ \cdots & 0 & q & 0 & p & \cdots & 0 & 0 & 0 & 0 & \cdots \\ & \vdots & \vdots &\vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \\ \cdots & 0 & 0 & 0 & 0 & \cdots & q & 0 & p & 0 & \cdots \\ \cdots & 0 & 0 & 0 & 0 & \cdots & 0 & q & 0 & p & \cdots \\ & \vdots & \vdots &\vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \\ \end{bmatrix} P=​⋯⋯⋯⋯​⋮q0⋮00⋮​⋮0q⋮00⋮​⋮p0⋮00⋮​⋮0p⋮00⋮​⋯⋯⋯⋯​⋮00⋮q0⋮​⋮00⋮0q⋮​⋮00⋮p0⋮​⋮00⋮0p⋮​⋯⋯⋯⋯​​
下面是几个”嵌入 Markov 链“ 的例子，在以下情况中模型的 Markov 性不明显，感觉都是一些比较怪的量

例：（ $(s,S)$ 订货策略）设某商店采用 $(s,S)$ 订货策略，每天早上检查某商品的剩余量，设为 $x$ ，则订购量为：（保证每天开门营业时存货量在 $[s,S]$ 范围内）
{0x≥sS−xx<s\left\{ \begin{array}{ll} 0 & x\geq s \\ S-x & x\lt s \end{array} \right. {0S−x​x≥sx<s​
设订货、进货不需要时间，每天的需求量为 YnY_nYn​ 独立同分布且 P(Yn=j)=ajP(Y_n=j)=a_jP(Yn​=j)=aj​ （$j=0,1,2,\cdots$） ，现在我们要从上述问题中找到一个 Markov 链

解：设 XnX_nXn​ 为第 $n$ 天结束时的存货量，则：
Xn+1={Xn−YnXn≥sS−YnXn<sX_{n+1}=\left\{ \begin{array}{ll} X_n-Y_n & X_n \ge s \\ S – Y_n & X_n \lt s \end{array} \right. Xn+1​={Xn​−Yn​S−Yn​​Xn​≥sXn​<s​
则 XnX_nXn​ 构成 Markov 链，转移概率为：
pij={ai−ji≥saS−ji<sp_{ij}=\left\{ \begin{array}{ll} a_{i-j} & i \geq s \\ a_{S-j} & i \lt s \end{array} \right. pij​={ai−j​aS−j​​i≥si<s​
例：（$M/G/1$ 排队系统）假设顾客按照参数为 $\lambda$ 的 Poisson 过程来到一个只有一个服务员的服务站：

• 若服务员空闲，则立马能得到服务
• 若服务员忙碌，则顾客排队等待直到轮到他

设每名顾客接受服务的时间是独立的随机变量，分布为 $G$ ，而且与到达过程独立。这个系统被称为$M/G/1$ 排队系统，其中 $M$ 代表顾客来的时间间隔服从指数分布。现在我们要从上述问题中找到一个 Markov 链

解：若以 $X(t)$ 表示时刻 $t$ 时系统中顾客的数目，则 $X(t)$ 并不具备 Markov 性，因为已知此时的状态，要推断下一时刻的状态，在不知道 $G$ 是否具有无记忆性的情况下，需要知道当前正在接受服务的顾客已经接受了多长时间的服务，所以不具备 Markov 性。

那我们可以不考虑正在接受服务的顾客，令 XnX_nXn​ 表示第 $n$ 位顾客走后剩下的顾客数，$n\ge 1$ 。再令 YnY_nYn​ 为第 $n+1$ 位顾客接受服务期间到来的顾客数，则：
Xn+1={Xn−1+YnXn>0YnXn=0X_{n+1}=\left\{ \begin{array}{ll} X_n-1+Y_n & X_n\gt 0 \\ Y_n & X_n=0 \end{array} \right. Xn+1​={Xn​−1+Yn​Yn​​Xn​>0Xn​=0​
事实上，因为 YnY_nYn​ （$n\ge 1$）代表的是在不相重叠的服务时间内来到的人数，来到的过程又是 Poisson 过程，所以 YnY_nYn​ 是相互独立的，并且是同分布的：
P(Yn=j)=∫0∞e−λx(λx)jj!dG(x)j≥0P(Y_n=j)=\int_0^{\infty}e^{-\lambda x}\frac{(\lambda x)^j}{j!}\,dG(x) \quad j\geq 0 P(Yn​=j)=∫0∞​e−λxj!(λx)j​dG(x)j≥0
因此 XnX_nXn​ 是 Markov 链，转移概率为：
{p0j=∫0∞e−λx(λx)jj!dG(x)j≥0pij=∫0∞e−λx(λx)j−i+1(j−i+1)!dG(x)j≥i−1;i≥1pij=0else\left\{ \begin{array}{ll} p_{0j}=\int_0^{\infty}e^{-\lambda x}\frac{(\lambda x)^j}{j!}\,dG(x) & j\geq 0\\ p_{ij}=\int_0^{\infty}e^{-\lambda x}\frac{(\lambda x)^{j-i+1}}{(j-i+1)!}\,dG(x) & j\geq i – 1;\, i\geq 1 \\ p_{ij}=0 & else \end{array} \right. ⎩⎨⎧​p0j​=∫0∞​e−λxj!(λx)j​dG(x)pij​=∫0∞​e−λx(j−i+1)!(λx)j−i+1​dG(x)pij​=0​j≥0j≥i−1;i≥1else​

n 步转移概率 C-K 方程

$n$ 步转移概率：称条件概率：
pij(n)=P(Xm+n=j∣Xm=i)p_{ij}^{(n)}=P(X_{m+n}=j\,|\,X_{m}=i) pij(n)​=P(Xm+n​=j∣Xm​=i)
为 Markov 链的 $n$ 步转移概率，相应地称 P(n)=(pij(n))\boldsymbol{P}^{(n)}=(p_{ij}^{(n)})P(n)=(pij(n)​) 为 $n$ 步转移矩阵；对于 $n=0$ ，规定：
pij(0)={0i≠j1i=jp_{ij}^{(0)}=\left\{ \begin{array}{ll} 0 & i\not=j \\ 1 & i=j \end{array} \right. pij(0)​={01​i=ji=j​
Chapman-Kolmogorov 方程：对一起 $n,m\ge 0$ ，$i,j\in S$ ，有：

• pijm+n=∑k∈Spik(m)pkj(n)p_{ij}^{m+n}=\sum\limits_{k\in S}p_{ik}^{(m)}p_{kj}^{(n)}pijm+n​=k∈S∑​pik(m)​pkj(n)​ ；
• P(n)=PP(n−1)=⋯=PnP^{(n)}=PP^{(n-1)}=\cdots=P^nP(n)=PP(n−1)=⋯=Pn ；

感觉显然成立欸hhh，有点像是 Bellman-Floyd 算法，第二个式子就是第一个式子的矩阵形式

注意：pij(n)p^{(n)}_{ij}pij(n)​ 理解成从状态 $i$ 转移 $n$ 步正好转移到状态 $j$ 的概率， 而对中间的 $n-1$ 步转移没有要求

例：甲乙两人进行某种游戏，设每局甲胜利的概率为 $p$ ，乙胜利的概率为 $q$ ，平局的概率为 $r$ ，胜者加一分，负者减一分，平局则不加不减，且当其中有一人获得两分时结束比赛，以 XnX_nXn​ 代表比赛至 $n$ 局时甲获得的分数，则 XnX_nXn​ 为时齐 Markov 链。求甲在获得一分的情况下，不超过两局可结束比赛的概率。

解：XnX_nXn​ 的一步转移矩阵为：
P=[10000qrp000qrp000qrp00001]\boldsymbol{P}=\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ q & r & p & 0 & 0 \\ 0 & q & r & p & 0 \\ 0 & 0 & q & r & p \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} P=​1q000​0rq00​0prq0​00pr0​000p1​​
其中每一行分别代表获得 -2、-1、0、1、2 分时的转移概率；两步转移矩阵为：
P2=[10000q+rqr2+pq2prp20q2q+rqr2+pq2prp20q2q+rqr2+pq2pr00001]P^2=\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ q+rq & r^2+pq & 2pr & p^2 & 0 \\ q^2 & q+rq & r^2+pq & 2pr & p^2 \\ 0 & q^2 & q+rq & r^2+pq & 2pr\\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} P2=​1q+rqq200​0r2+pqq+rqq20​02prr2+pqq+rq0​0p22prr2+pq0​00p22pr1​​
故甲在获得一分的情况下，不超过两局可结束比赛的概率为：
p1,2(2)+p1,−2(2)=p+prp^{(2)}_{1,\,2}+p^{(2)}_{1,\,-2}=p+pr p1,2(2)​+p1,−2(2)​=p+pr
注意这里比较特殊，虽然甲再来一局就有可能得到 2 分，但是得到两分后转移概率只有到 2 为 1，因此 p1,2(2)p^{(2)}_{1,\,2}p1,2(2)​ 是包括了一局甲就获胜的概率；但是并不意味着 p1,2(2)p^{(2)}_{1,\,2}p1,2(2)​ 就包括了所有两步以内的转移概率，只是这里比较特殊。

例：（广告效益的推算）某种啤酒 $A$ 的广告改变了广告方式，经调查发现四种啤酒的顾客每两个月的平均转换率如下：（假设市场中只有这四种啤酒）：
A→A(0.95)B(0.02)C(0.02)D(0.01)B→A(0.30)B(0.60)C(0.06)D(0.04)C→A(0.20)B(0.10)C(0.70)D(0.00)D→A(0.20)B(0.20)C(0.10)D(0.50)\begin{array}{c} A\to A(0.95) \quad B(0.02) \quad C(0.02) \quad D(0.01) \\ B\to A(0.30) \quad B(0.60) \quad C(0.06) \quad D(0.04) \\ C\to A(0.20) \quad B(0.10) \quad C(0.70) \quad D(0.00) \\ D\to A(0.20) \quad B(0.20) \quad C(0.10) \quad D(0.50) \\ \end{array} A→A(0.95)B(0.02)C(0.02)D(0.01)B→A(0.30)B(0.60)C(0.06)D(0.04)C→A(0.20)B(0.10)C(0.70)D(0.00)D→A(0.20)B(0.20)C(0.10)D(0.50)​
目前购买 $A$ 、$B$ 、$C$ 和 $D$ 四种啤酒的顾客的分布为：$(25\%,30\%,35\%,10\%)$ ，试求半年以后啤酒 $A$ 的市场份额。

解：显然一步转移矩阵就是：
P=[0.950.020.020.010.300.600.060.040.200.100.700.000.200.200.100.50]P=\begin{bmatrix} 0.95 & 0.02 & 0.02 & 0.01 \\ 0.30 & 0.60 & 0.06 & 0.04 \\ 0.20 & 0.10 & 0.70 & 0.00 \\ 0.20 & 0.20 & 0.10 & 0.50 \\ \end{bmatrix} P=​0.950.300.200.20​0.020.600.100.20​0.020.060.700.10​0.010.040.000.50​​
半年就是三步转移矩阵：
P3=[0.88940.04580.04660.018200.601750.25590.09880.044550.48340.13880.365840.011960.50090.21340.142640.14306]P^3=\begin{bmatrix} 0.8894 & 0.0458 & 0.0466 & 0.01820 \\ 0.60175 & 0.2559 & 0.0988 & 0.04455 \\ 0.4834 & 0.1388 & 0.36584 & 0.01196 \\ 0.5009 & 0.2134 & 0.14264 & 0.14306 \\ \end{bmatrix} P3=​0.88940.601750.48340.5009​0.04580.25590.13880.2134​0.04660.09880.365840.14264​0.018200.044550.011960.14306​​
则半年以后 $A$ 的市场占有率变为：
v=[25%30%35%10%][0.88940.601750.48340.5009]≈0.624v=\begin{bmatrix}25\% & \,30\% & \,35\% & \,10\%\end{bmatrix}\begin{bmatrix}0.8894 \\ 0.60175 \\ 0.4834 \\ 0.5009\end{bmatrix}\approx 0.624 v=[25%​30%​35%​10%​]​0.88940.601750.48340.5009​​≈0.624

状态的分类及性质

我们首先讨论 Markov 链中各个状态的关系，然后以这些关系将状态分类，最后研究他们的性质。

可达/互通：若存在 $n\ge 0$ 使得 pi,j(n)>0p^{(n)}_{i,j}\gt 0pi,j(n)​>0 ，则称状态 $i$ 可达状态 $j$ ，记为 $i\to j$ ；若 $i\to j$ 且 $j\to i$ ，则称 $i$ 和 $j$ 互通，记为 $i\leftrightarrow j$

Th：互通是一种等价关系，即满足：

• 自反性：$i\leftrightarrow i$ ；
• 对称性：若 $i\leftrightarrow j$ ，则 $j\leftrightarrow i$ ；
• 传递性：若 $i\leftrightarrow j$ 且 $j\leftrightarrow k$ ，则 $i\leftrightarrow k$ ；

自反、对称显然成立，传递性只需要使用 C-K 方程即可得到。

我们按照互通这个等价关系分类，则同一状态不能同时属于两个类，并且同一类中的状态都是互通的。

可约：若 Markov 链只存在一个类，就称它是不可约的；否则称为可约的。

周期：若集合 {n:n≥1,pii(n)>0}\{n:\,n\geq 1,\,p_{ii}^{(n)}\gt0\}{n:n≥1,pii(n)​>0} 非空，则称它的最大公约数 $d$ 为状态 $i$ 的周期。若 $d>1$ ，则称 $i$ 是周期的；若 $d=1$ ，则称 $i$ 是非周期的。若该集合为空集，则称 $i$ 的周期无穷大。

• 注意：即使 $d$ 是有限的，也不代表对任意 m∈N+m\in N^+m∈N+ 都有 pii(md)>0p_{ii}^{(md)}\gt 0pii(md)​>0 ，跟格点分布并不是在所有 $nd$ 上取值都不为 0 一样。

例：以下 Markov 过程，对于状态 $1$ 来说，经过 $4$ ，$6$ ，$8$ ，$10$ ，$\cdots$ 步可以回到状态 $1$ ，周期为 $d=2$ ，虽然经过两步回不来，但是我们仍然说周期为 $2$ ：

Th：若状态 $i$ 和 $j$ 属于同一类，则 $d(i)=d(j)$ ；

证明：由于 $i$ 和 $j$ 互通，则存在 $m$ ，$n$ 使得 pij(m)>0p_{ij}^{(m)}\gt 0pij(m)​>0 和 pji(n)>0p_{ji}^{(n)}\gt 0pji(n)​>0 ；则 pii(m+n)=pij(m)pji(n)>0p_{ii}^{(m+n)}=p_{ij}^{(m)}p_{ji}^{(n)}\gt 0pii(m+n)​=pij(m)​pji(n)​>0 ；又若 $i$ ，$j$ 的周期存在，即 $d(i),d(j)<\infty$ ，则：pii(m+n+d(j))=pij(m)pjj(d(j))pji(n)>0p_{ii}^{(m+n+d(j))}=p_{ij}^{(m)}p_{jj}^{(d(j))}p_{ji}^{(n)}\gt 0pii(m+n+d(j))​=pij(m)​pjj(d(j))​pji(n)​>0 。由此可以得到 $d(i)$ 同时整除 $m+n$ 和 $m+n+d(j)$ ，因此 $d(i)$ 整除 $d(j)$ ；同理可以得到 $d(j)$ 整除 $d(i)$ ，故 $d(i)=d(j)$ 。

Def：对于状态 $i$ 和 $j$ ，以首达概率 fij(n)f_{ij}^{(n)}fij(n)​ 记为从 $i$ 出发经过 $n$ 步正好第一次到达 $j$ 的概率，有：
fij(0)=δijfij(n)=P(Xn=j,Xk≠j,k=1,2,⋯,n−1∣X0=i),n≥1\begin{align} f_{ij}^{(0)}=&\,\delta_{ij} \\ f_{ij}^{(n)}=&\,P(X_n=j,\,X_k\not=j,\,k=1,2,\cdots,n-1\,|\,X_0=i),\,n\geq 1 \end{align} fij(0)​=fij(n)​=​δij​P(Xn​=j,Xk​=j,k=1,2,⋯,n−1∣X0​=i),n≥1​​
令 fij=∑n=1∞fij(n)f_{ij}=\sum\limits_{n=1}^{\infty}f_{ij}^{(n)}fij​=n=1∑∞​fij(n)​ ，若 fjj=1f_{jj}=1fjj​=1 ，则称状态 $j$ 为常返状态；若 fjj<1f_{jj}\lt 1fjj​<1 ，则称 $j$ 为非常返状态或瞬过状态；

容易看出来集合 An={Xn=j,Xk≠j,k=1,2,⋯,n−1∣X0=i}A_n=\{X_n=j,\,X_k\not=j,\,k=1,2,\cdots,n-1\,|\,X_0=i\}An​={Xn​=j,Xk​=j,k=1,2,⋯,n−1∣X0​=i} 在 $n$ 不同时时不相交的，并且 ⋃n=1∞An\bigcup\limits_{n=1}^{\infty}A_nn=1⋃∞​An​ 表示总有一个 $n$ 使得过程从 $i$ 经过 $n$ 步以后可到达 $j$ ，所以：
P(⋃n=1∞An)=∑n=1∞P(An)=∑n=1∞fij(n)=fijP(\bigcup\limits_{n=1}^{\infty}A_n)=\sum\limits_{n=1}^{\infty}P(A_n)=\sum\limits_{n=1}^{\infty}f_{ij}^{(n)}=f_{ij} P(n=1⋃∞​An​)=n=1∑∞​P(An​)=n=1∑∞​fij(n)​=fij​
即==首达概率 fijf_{ij}fij​ 表示从 $i$ 出发，在有限步内可以到达 $j$ 的概率。==所以，当 $i$ 为常返状态时，从 $i$ 出发，在有限步之内，过程将以概率 $1$ 重新返回 $i$ ；而当 $i$ 为非常返状态时，过程以概率 1−fii>01-f_{ii}\gt 01−fii​>0 不再回到 $i$ ，换而言之，从 $i$ 滑过了。

对于常返状态 $i$ ，定义：
μi=∑n=1∞nfii(n)\mu_i=\sum\limits_{n=1}^{\infty}nf_{ii}^{(n)} μi​=n=1∑∞​nfii(n)​
μi\mu_iμi​ 表示从 $i$ 出发再返回 $i$ 所需的平均步数（时间）

Def：对于常返状态 $i$ ，若 μi<∞\mu_i\lt \inftyμi​<∞ ，则称 $i$ 为正常返状态；若 μi=∞\mu_i=\inftyμi​=∞ ，则称 $i$ 为零常返状态。特别地：

• 若 $i$ 为正常返状态，且是非周期的，则称为遍历状态；

• 若 $i$ 为遍历状态，且 fii(1)=1f_{ii}^{(1)}=1fii(1)​=1 ，则称 $i$ 为吸收状态，此时显然 μi=1\mu_i=1μi​=1 。

例：设某 Markov 链的状态空间为 S={1,2,3,4}S=\{1,\,2,\,3,\,4\}S={1,2,3,4} ，其一步转移概率矩阵为：
P=[1212001000013230120120]P=\begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & \frac{1}{3} & \frac{2}{3} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \end{bmatrix} P=​21​1021​​21​031​0​0032​21​​0000​​
试将状态进行分类。

解：没有状态可以转移到状态 4，因此 f44=0f_{44}=0f44​=0 ，4 是非常返状态；状态 3 只会转移到 2 和自己，所以 f33(1)=23f_{33}^{(1)}=\frac{2}{3}f33(1)​=32​ ，而 f33(n)=0f_{33}^{(n)}=0f33(n)​=0 （$n\ge 2$），所以 3 是非常返状态；

1 和 2 都是常返状态，因为：
f11=12+12+0+⋯+0+⋯=1f22=0+12+122+⋯=1\begin{align} f_{11}=&\,\frac{1}{2}+\frac{1}{2}+0+\cdots+0+\cdots=1 \\ f_{22}=&\,0+\frac{1}{2}+\frac{1}{2^2}+\cdots=1 \end{align} f11​=f22​=​21​+21​+0+⋯+0+⋯=10+21​+221​+⋯=1​​
而他们的期望为：
μ1=1×12+2×12+0+⋯+0+⋯=32<∞μ2=1×0+2×12+3×122+⋯=3<∞\begin{align} \mu_{1}=&\,1\times\frac{1}{2}+2\times\frac{1}{2}+0+\cdots+0+\cdots=\frac{3}{2}\lt \infty \\ \mu_{2}=&\,1\times0+2\times\frac{1}{2}+3\times\frac{1}{2^2}+\cdots=3 \lt \infty \end{align} μ1​=μ2​=​1×21​+2×21​+0+⋯+0+⋯=23​<∞1×0+2×21​+3×221​+⋯=3<∞​​
因此他们都是正常返状态，且周期为 1，故都为遍历状态。

Th：同属于一类的状态同为常返状态或者非常返状态；并且当为常返状态时，又同为正常返状态或零常返状态。

Th：转移概率 pij(n)p_{ij}^{(n)}pij(n)​ 和首达概率 fij(n)f_{ij}^{(n)}fij(n)​ 的关系为：（$1\le n<\infty$）
pij(n)=∑l=1nfij(l)pjj(n−l)p_{ij}^{(n)}=\sum\limits_{l=1}^{n}f_{ij}^{(l)}p_{jj}^{(n-l)} pij(n)​=l=1∑n​fij(l)​pjj(n−l)​
证明：使用数学归纳法：

• 当 $n=1$ 时，显然 pij(1)=fij(1)p_{ij}^{(1)}=f_{ij}^{(1)}pij(1)​=fij(1)​ ；
• 假设对 $n-1$ ，pij(n−1)=∑l=1n−1fij(l)pjj(n−1−l)p_{ij}^{(n-1)}=\sum\limits_{l=1}^{n-1}f_{ij}^{(l)}p_{jj}^{(n-1-l)}pij(n−1)​=l=1∑n−1​fij(l)​pjj(n−1−l)​ 成立；那么对于 $n$ ，使用 C-K 方程，有：（中间有一步交换求和次序的比较关键）

pij(n)=∑k∈Spik(1)pkj(n−1)=pij(1)pjj(n−1)+∑k∈S,k≠jpik(1)pkj(n−1)=fij(1)pjj(n−1)+∑k∈S,k≠jfik(1)[∑l=1n−1fkj(l)pjj(n−1−l)]=fij(1)pjj(n−1)+∑l=1n−1[∑k∈S,k≠j(fik(1)fkj(l))pjj(n−1−l)]=fij(1)pjj(n−1)+∑l=1n−1(fij(l+1)pjj(n−1−l))=fij(1)pjj(n−1)+∑l=2n(fij(l)pjj(n−l))=∑l=1n(fij(l)pjj(n−l))\begin{align} p_{ij}^{(n)}=&\,\sum\limits_{k\in S}p_{ik}^{(1)}p_{kj}^{(n-1)}=p_{ij}^{(1)}p_{jj}^{(n-1)}+\sum\limits_{k\in S,\,k\not=j}p_{ik}^{(1)}p_{kj}^{(n-1)} \\ =&\,f_{ij}^{(1)}p_{jj}^{(n-1)}+\sum\limits_{k\in S,\,k\not=j}f_{ik}^{(1)}\left[ \sum\limits_{l=1}^{n-1}f_{kj}^{(l)}p_{jj}^{(n-1-l)} \right] \\ =&\, f_{ij}^{(1)}p_{jj}^{(n-1)}+\sum\limits_{l=1}^{n-1}\left[ \sum\limits_{k\in S,\,k\not=j}\left(f_{ik}^{(1)}f_{kj}^{(l)}\right)p_{jj}^{(n-1-l)} \right] \\ =&\, f_{ij}^{(1)}p_{jj}^{(n-1)}+\sum\limits_{l=1}^{n-1} \left( f_{ij}^{(l+1)}p_{jj}^{(n-1-l)} \right) \\ =&\, f_{ij}^{(1)}p_{jj}^{(n-1)}+\sum\limits_{l=2}^{n} \left( f_{ij}^{(l)}p_{jj}^{(n-l)} \right) \\ =&\,\sum\limits_{l=1}^{n} \left( f_{ij}^{(l)}p_{jj}^{(n-l)} \right) \end{align} pij(n)​======​k∈S∑​pik(1)​pkj(n−1)​=pij(1)​pjj(n−1)​+k∈S,k=j∑​pik(1)​pkj(n−1)​fij(1)​pjj(n−1)​+k∈S,k=j∑​fik(1)​[l=1∑n−1​fkj(l)​pjj(n−1−l)​]fij(1)​pjj(n−1)​+l=1∑n−1​​k∈S,k=j∑​(fik(1)​fkj(l)​)pjj(n−1−l)​​fij(1)​pjj(n−1)​+l=1∑n−1​(fij(l+1)​pjj(n−1−l)​)fij(1)​pjj(n−1)​+l=2∑n​(fij(l)​pjj(n−l)​)l=1∑n​(fij(l)​pjj(n−l)​)​​

pij(n)=∑l=1nfij(l)pjj(n−l)p_{ij}^{(n)}=\sum\limits_{l=1}^{n}f_{ij}^{(l)}p_{jj}^{(n-l)}pij(n)​=l=1∑n​fij(l)​pjj(n−l)​ 可以理解成，将 pij(n)p_{ij}^{(n)}pij(n)​ 的事件按照第一次从 $i$ 到达 $j$ 的步数作为划分依据得到全事件

Th：状态 $i$ 为常返的当且仅当 ∑n=0∞pii(n)=∞\sum\limits_{n=0}^{\infty}p_{ii}^{(n)}=\inftyn=0∑∞​pii(n)​=∞ ；状态 $i$ 为非常返时有 ∑n=0∞pii(n)=11−fii\sum\limits_{n=0}^{\infty}p_{ii}^{(n)}=\frac{1}{1-f_{ii}}n=0∑∞​pii(n)​=1−fii​1​ ；

证明：（中间有一步交换求和次序的比较关键）
∑n=0∞pii(n)=pii(0)+∑n=1∞pii(n)=pii(0)+∑n=1∞[∑l=1nfii(l)pii(n−l)]=1+∑l=1∞∑n=l∞fii(l)pii(n−l)=1+∑l=1∞(fii(l)∑n=l∞pii(n−l))=1+(∑l=1∞fii(l))(∑n=l∞pii(n−l))=1+fii(∑n=0∞pii(n))\begin{align} \sum\limits_{n=0}^{\infty}p_{ii}^{(n)}=&\, p_{ii}^{(0)}+\sum\limits_{n=1}^{\infty}p_{ii}^{(n)} \\ =&\, p_{ii}^{(0)}+\sum\limits_{n=1}^{\infty}\left[ \sum\limits_{l=1}^{n}f_{ii}^{(l)}p_{ii}^{(n-l)} \right] \\ =&\, 1+\sum\limits_{l=1}^{\infty}\sum\limits_{n=l}^{\infty}f_{ii}^{(l)}p_{ii}^{(n-l)} \\ =&\, 1+\sum\limits_{l=1}^{\infty}\left(f_{ii}^{(l)}\sum\limits_{n=l}^{\infty}p_{ii}^{(n-l)}\right) \\ =&\, 1+\left(\sum\limits_{l=1}^{\infty}f_{ii}^{(l)}\right)\left( \sum\limits_{n=l}^{\infty}p_{ii}^{(n-l)} \right) \\ =&\, 1+f_{ii}\left( \sum\limits_{n=0}^{\infty}p_{ii}^{(n)} \right) \\ \end{align} n=0∑∞​pii(n)​======​pii(0)​+n=1∑∞​pii(n)​pii(0)​+n=1∑∞​[l=1∑n​fii(l)​pii(n−l)​]1+l=1∑∞​n=l∑∞​fii(l)​pii(n−l)​1+l=1∑∞​(fii(l)​n=l∑∞​pii(n−l)​)1+(l=1∑∞​fii(l)​)(n=l∑∞​pii(n−l)​)1+fii​(n=0∑∞​pii(n)​)​​
因此：
∑n=0∞pii(n)=11−fii\sum\limits_{n=0}^{\infty}p_{ii}^{(n)}=\frac{1}{1-f_{ii}} n=0∑∞​pii(n)​=1−fii​1​
Th：若 $i\leftrightarrow j$ 且 $i$ 为常返状态，则 fji=1f_{ji}=1fji​=1 ；

证明：由于 $i\leftrightarrow j$ ，因此系统中存在正概率，使得从 $i$ 出发在有限步内可以到达 $j$ ；假设 fji<1f_{ji}\lt 1fji​<1 ，意味着系统中存在正概率从 $j$ 出发在有限步内到达不了 $i$ ；结合上面两点，意味着系统中存在正概率，使得从 $i$ 出发，不能在有限步之内回到 $i$ ，因此 fii<1f_{ii}\lt 1fii​<1 ，与 $i$ 是常返状态矛盾。

Th：常返状态是一个类性质。

证明：即证明若 $i\leftrightarrow j$ ，则 $i$ 、$j$ 同为常返或非常返状态。由 $i\leftrightarrow j$ 可知，存在 $n,m\ge 0$ ，使得 pij(n)>0p_{ij}^{(n)}\gt 0pij(n)​>0 ，pji(m)>0p_{ji}^{(m)}\gt 0pji(m)​>0 。由 C-K 方程得到：（即左边的事件包括了右边的事件，所以概率更大）
pii(m+n+l)≥pij(n)pjj(l)pji(m)pjj(m+n+l)≥pji(m)pii(l)pij(n)\begin{align} p_{ii}^{(m+n+l)}\geq&\, p_{ij}^{(n)}p_{jj}^{(l)}p_{ji}^{(m)} \\ p_{jj}^{(m+n+l)}\geq&\, p_{ji}^{(m)}p_{ii}^{(l)}p_{ij}^{(n)} \\ \end{align} pii(m+n+l)​≥pjj(m+n+l)​≥​pij(n)​pjj(l)​pji(m)​pji(m)​pii(l)​pij(n)​​​
则对 $l$ 求和得到：
∑l=0∞pii(l)≥∑l=0∞pii(m+n+l)≥pij(n)pji(m)∑l=0∞pjj(l)≥∑l=0∞pjj(l)∑l=0∞pjj(l)≥∑l=0∞pjj(m+n+l)≥pji(m)pij(n)∑l=0∞pii(l)≥∑l=0∞pii(l)\begin{align} \sum\limits_{l=0}^{\infty}p_{ii}^{(l)}\geq\sum\limits_{l=0}^{\infty}p_{ii}^{(m+n+l)}\geq&\, p_{ij}^{(n)}p_{ji}^{(m)}\sum\limits_{l=0}^{\infty}p_{jj}^{(l)}\geq\sum\limits_{l=0}^{\infty}p_{jj}^{(l)} \\ \sum\limits_{l=0}^{\infty}p_{jj}^{(l)}\geq\sum\limits_{l=0}^{\infty}p_{jj}^{(m+n+l)}\geq&\, p_{ji}^{(m)}p_{ij}^{(n)}\sum\limits_{l=0}^{\infty}p_{ii}^{(l)}\geq\sum\limits_{l=0}^{\infty}p_{ii}^{(l)} \\ \end{align} l=0∑∞​pii(l)​≥l=0∑∞​pii(m+n+l)​≥l=0∑∞​pjj(l)​≥l=0∑∞​pjj(m+n+l)​≥​pij(n)​pji(m)​l=0∑∞​pjj(l)​≥l=0∑∞​pjj(l)​pji(m)​pij(n)​l=0∑∞​pii(l)​≥l=0∑∞​pii(l)​​​
因此 ∑l=0∞pii(l)\sum\limits_{l=0}^{\infty}p_{ii}^{(l)}l=0∑∞​pii(l)​ 和 ∑l=0∞pjj(l)\sum\limits_{l=0}^{\infty}p_{jj}^{(l)}l=0∑∞​pjj(l)​ 同为有穷或者无限，由上一个定理可以知道，fiif_{ii}fii​ 和 fjjf_{jj}fjj​ 同时等于 1 或者小于 1；因此常返状态是一个类性质。

我们还可以证明，当 $i$ ，$j$ 同为常返状态时，它们同为正常返状态或零常返状态。下一节中将给出证明。

例：设 Markov 链的状态空间 S={0,1,2,⋯}S=\{0,\,1,\,2,\,\cdots\}S={0,1,2,⋯} ，转移概率如图所示。

易知 f00(1)=12f_{00}^{(1)}=\frac{1}{2}f00(1)​=21​ ，f00(2)=12×12f_{00}^{(2)}=\frac{1}{2}\times\frac{1}{2}f00(2)​=21​×21​ ，f00(3)=12×12×12f_{00}^{(3)}=\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}f00(3)​=21​×21​×21​ $\cdots$ ，因此：
f00=∑n=1∞12n=1μ0=∑n=1∞n12n=2<∞\begin{align} f_{00}=&\,\sum\limits_{n=1}^{\infty}\frac{1}{2^n}=1 \\ \mu_0=&\,\sum\limits_{n=1}^{\infty}n\frac{1}{2^n}=2\lt \infty \end{align} f00​=μ0​=​n=1∑∞​2n1​=1n=1∑∞​n2n1​=2<∞​​
可见状态 $0$ 是正常返状态，而且是非周期的，因此也是遍历状态；对于其他状态 $i>0$ ，都有 $i\leftrightarrow 0$ ，因此也都是遍历状态。

查看全文

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.dgrt.cn/a/2211367.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章：

随机过程 Markov 链（上）

文章目录随机过程 Markov 链（上）基本概念n 步转移概率 C-K 方程状态的分类及性质随机过程 Markov 链（上）
基本概念
有一类过程，具备所谓的 ”无后效性“（Markov 性），即要确定过程将……

编程日记2023/4/6 13:46:49

SCons官网，Scons构建工具手册，SCons构建系统

一、SCons官网
SCons: A software construction tool – SCons
二、SCons用户手册
SCons 4.5.2
三、SCons构建工具手册，SCons构建系统
Scons 构建工具手册 – 《RT-Thread工具手册》 – 书栈网 BookStack…

编程日记2023/4/6 13:46:37

更新时无冲突的情况（阁瑞钛伦特软件-九耶实训）

大多数使用“与资源库同步”菜单的目的是想查看本地和远程资源的差异，并不想将本地的内容进行更新。
而“更新”菜单则不然，它的主要作用是将远程仓库中的内容下载到本地，以使本地的版本内容和仓库中的内容一致。
Step01：复用前……

编程日记2023/4/6 13:46:28

华为OD机试-日志限流-2022Q4 A卷-Py/Java/JS

某软件系统会在运行过程中持续产生日志，系统每天运行N单位时间，运行期间每单位时间产生的日志条数保行在数组 records中。records[i]表示第i单位时间内产生日志条数。 由于系统磁盘空间限制，每天可记录保存的日志总数上限为total条。 如果一天……

编程日记2023/4/6 13:46:19

什么是微前端架构？

作为前端开发的新兴架构模式，微前端架构不仅可以提高开发效率、迭代速度和用户体验，还可以提高团队的协作效率和代码复用率，具有很高的业务价值。而与之相比，随着互联网应用的不断发展和迭代，传统的单体应用架构已经逐……

编程日记2023/4/6 13:46:10

【刷题之路】LeetCode 1539. 第 k 个缺失的正整数

【刷题之路】LeetCode 1539. 第 k 个缺失的正整数一、题目描述二、解题1、方法1——暴力法1.1、思路分析1.2、代码实现2、方法2——双指针2.1、思路分析2.2、代码实现3、方法3——二分查找3.1、思路分析3.2、代码实现一、题目描述
原题连接： 1539. 第 k 个缺失的正……

编程日记2023/4/6 13:46:00

【python 定时任务】Python apscheduler 定时调度框架

在开发 Python 应用程序时，我们常常需要编写定时任务。例如，我们可能需要每天自动发送一份报告、每小时清理一次临时文件等。为了实现这些功能，我们可以使用 Python 的 apscheduler 模块。
安装 apscheduler 要使用 apscheduler，你需要先安装它。你可以使用 pip 命令来安装……

编程日记2023/4/6 13:45:40

chatGPT教程

…

编程日记2023/4/6 13:45:31

调用ChatGPT API

安装
pip install openai找到openai.api_key
首先登录到OpenAI API界面(https://platform.openai.com/)，点击右上角的账号弹出的列表中，点击view API keys。跳转到API key界面，点击Create new secret key(如果你已经生成过key并且记录下来就……

编程日记2023/4/6 13:45:21

Word处理控件Aspose.Words功能演示：使用 Aspose.Words for C++ 在 Qt 应用程序中创建 Word 文档

Aspose.Words 是一种高级Word文档处理API，用于执行各种文档管理和操作任务。API支持生成，修改，转换，呈现和打印文档，而无需在跨平台应用程序中直接使用Microsoft Word。此外，
Aspose API支持流行文件格式处……

编程日记2023/4/6 13:45:09

Java 进阶(15)线程安全集合

CopyOnWriteArrayList
线程安全的ArrayList，加强版读写分离。
写有锁，读⽆锁，读写之间不阻塞，优于读写锁。
写⼊时，先copy⼀个容器副本、再添加新元素，最后替换引⽤。
使⽤⽅式与ArrayList⽆异。
示例……

编程日记2023/4/16 14:57:08

HR：面试官最爱问的linux问题，看看你能答对多少

文章目录摘要Linux的文件系统是什么样子的？如何访问和管理文件和目录？如何在Linux中查看和管理进程？如何使用Linux命令行工具来查看系统资源使用情况？如何配置Linux系统的网络设置？如何使用Linux的cron任务调度器来执行……

编程日记2023/4/16 14:56:56

vscode开发常用的工具栏选项,查看源码技巧以及【vscode常用的快捷键】

一、开发常用的工具栏选项
1、当前打开的文件快速在左侧资源树中定位： 其实打开了当前的文件已经有在左侧资源树木定位了，只是颜色比较浅 2、打开太多文件的时候，可以关闭 3、设置查看当前类或文件的结构 OUTLINE
相当于idea 查看当前类或接……

编程日记2023/4/16 14:56:45

数据要素化条件之一：原始性

随着技术的发展，计算机不仅成为人类处理信息的工具，而且逐渐地具有自主处理数据的能力，出现了替代人工的数据智能技术。数据智能的大规模使用需要关于同一分析对象或同一问题的、来源于不同数据源的海量数据。这种数据必须是针对特定对象的记……

编程日记2023/4/16 14:56:36

【面试题 高逼格利用 类实现加法】编写代码, 实现多线程数组求和.

编写代码, 实现多线程数组求和.关键1. 数组的初始化关键2. 奇偶的相加import java.util.Random;public class Thread_2533 {public static void main(String[] args) throws InterruptedException {// 记录开始时间long start System.currentTimeMillis();// 1. 给定一个很长的……

编程日记2023/4/16 14:56:10

一个python训练

美国:28:麻省理工学院,斯坦福大学,哈佛大学,加州理工学院,芝加哥大学,普林斯顿大学,宾夕法尼亚大学,耶鲁大学,康奈尔大学,哥伦比亚大学,密歇根大学安娜堡分校,约翰霍普金斯大学,西北大学,加州大学伯克利分校,纽约大学,加州大学洛杉矶分校,杜克大学,卡内基梅隆大学,加州大学圣地……

编程日记2023/4/16 14:55:59

Mybatis03学习笔记

目录 使用注解开发
设置事务自动提交
mybatis运行原理
注解CRUD
lombok使用（偷懒神器，大神都不建议使用）
复杂查询环境（多对一）
复杂查询环境（一对多）
动态sql环境搭建
动态sql常用标签……

编程日记2023/4/16 14:55:50

设置或取得c# NumericUpDown 编辑框值的方法,(注意：不是Value值)

本人在C#开发中使用到了NumericUpDown控件，但是发现该控件不能直接控制显示值，经研究得到下面的解决办法
NumericUpDown由于是由多个控件组合而来的控件，其中包含一个类似TextBox的控件，若想取得或改变其中的值要使用如下方法
N……

编程日记2023/4/16 14:55:46

使用NPOI 技术 的SetColumnWidth 精确控制列宽不能成功的解决办法（C#）

在使用NPOI技术开发自动操作EXCEL软件时遇到不能精确设置列宽的问题。
如
ISheet sheet1 hssfworkbook.CreateSheet("Sheet1");
sheet1.SetColumnWidth(0, 50 * 256); // 在EXCEL文档中实际列宽为49.29
sheet1.SetColumnWidth(1, 100 * 256); // 在EXCEL文……

编程日记2023/4/16 14:55:46

Mysql 数据库zip版安装时basedir datadir 路径设置问题，避免转义符的影响

本人在开发Mysql数据库自动安装程序时遇到个很奇怪的问题，其中my.ini的basedir 的路径设置是下面这样的：
basedir d:\测试\test\mysql
但是在使用mysqld安装mysql服务时老是启动不了，报1067错误，后来查看window事件发现一个独特……

编程日记2023/4/16 14:55:45