离散时间马尔科夫链与转移概率
文章目录
1. 马尔科夫性的引入
随机过程中，最重要的就是研究两个随机变量之间的关系。比如相关，就是研究两个随机变量之间的亲疏远近关系。而相关系数表征了两个随机变量之间的角度。对于高斯过程，我们通过联合高斯分布，把若干个随机变量联系在一起。而泊松过程各个点之间的联系体现在事件发生的间隔是指数分布。
如果我们想描绘n个随机变量之间的联系，最好的方法是使用联合分布。
Joint Distribution P ( Z 1 , . . . , Z n ) \text{Joint Distribution}\\ P(Z_1,...,Z_n) Joint DistributionP(Z1,...,Zn)
但是联合分布求起来非常的麻烦，我们可以尝试使用条件概率的方法来进行计算
P ( Z 1 , . . . , Z n ) = P ( Z n ∣ Z n − 1 , . . . , Z 1 ) P ( Z n − 1 , . . . , Z 1 ) = P ( Z n ∣ Z n − 1 , . . . , Z 1 ) P ( Z n − 1 ∣ Z n − 2 , . . . , Z 1 ) P ( Z n − 2 , . . . , Z 1 ) = ∏ k = 1 n P ( Z k ∣ Z k − 1 , . . . , Z 1 ) P(Z_1,...,Z_n) = P(Z_n|Z_{n-1},...,Z_1) P(Z_{n-1},...,Z_1) \\ = P(Z_n|Z_{n-1},...,Z_1) P(Z_{n-1}|Z_{n-2},...,Z_1)P(Z_{n-2},...,Z_1) \\ = \prod _{k=1}^n P(Z_k|Z_{k-1},...,Z_1) P(Z1,...,Zn)=P(Zn∣Zn−1,...,Z1)P(Zn−1,...,Z1)=P(Zn∣Zn−1,...,Z1)P(Zn−1∣Zn−2,...,Z1)P(Zn−2,...,Z1)=k=1∏nP(Zk∣Zk−1,...,Z1)
事实上，这样做问题并没有得到简化。虽然增加了条件，随机因素减少了，但是约束条件变多了，实际上问题难度并没有得到降低。
比如两点之间直线最短，如果现在增加一个约束，在球面上走，就需要找一个大圆，不能直接穿过去。继续增加约束，在椭球体上找两点间最短距离，用椭圆积分做。如果是随便给一个曲面，就要找测地线了。目前这还是个没有完全解决的问题。因此，一旦约束变强了，一点都没有解决问题
用等号的式子不叫简化，叫化简。如果要做简化，一定要做假设。
Assumption \text{Assumption} Assumption
好的假设需要满足下面三个条件
- 实现起来容易：比如假定某一个方程成立，可能这个方程都没有办法解
- 存在的空间巨大：能满足条件的变量如果没有，变成了空集
- 应用及其广泛：实际环境中，满足这个假设的情况很多
我们在此做一个假设，如果角标是时间的话，表示只有离当前最近的那个随机变量能够产生影响，其他就都可以忽略了。这个假设是马尔科夫做的，因此叫做马尔科夫性
Markov Property P ( Z n ∣ Z n − 1 , . . . , Z 1 ) = P ( Z n ∣ Z n − 1 ) \text{Markov Property}\\ P(Z_n | Z_{n-1},...,Z_1) = P(Z_n | Z_{n-1}) Markov PropertyP(Zn∣Zn−1,...,Z1)=P(Zn∣Zn−1)
马尔科夫的这个假设就满足好的假设的三个条件。马尔科夫性实现起来非常容易，很多随机过程都满足马尔科夫性，应用及其广泛，因此这是个好的假设
随机过程按照时间的连续性和状态的连续性可以分为四种
- 离散时间离散状态的随机过程：离散时间马尔科夫链(DT Markov Chain)
- 离散时间连续状态的随机过程：连续时间马尔科夫链(CT Markov Chain)
- 连续时间离散状态的随机过程：泊松过程(Poisson)
- 连续时间连续状态的随机过程：高斯过程(Gaussian)
2. 马尔科夫性与马尔科夫链
2.1 定义
Markov Chains \text{Markov Chains} Markov Chains
假设我们有一个离散的随机过程
Z
{
n
}
Z
k
∈
{
x
1
,
.
.
,
x
n
,
.
.
.
}
Z\{_n \} \\ Z_k \in \{x_1,..,x_n,... \}
Z{n}Zk∈{x1,..,xn,...}
我们任取n个随机变量，都有如下式子成立，这就是马尔科夫性
P ( Z n ∣ Z n − 1 , . . . , Z 1 ) = P ( Z n ∣ Z n − 1 ) P(Z_n | Z_{n-1},...,Z_1) = P(Z_n|Z_{n-1}) P(Zn∣Zn−1,...,Z1)=P(Zn∣Zn−1)
而叫做链是因为，我们把随机过程的状态表征为一个一个的点，状态随着时间进行变换，对不同时间随机过程的状态进行采样，可以得到一个样本轨道。这种形象的表示就是链
2.2 马尔科夫性的解读
我们假设三个符号，A表示过去，B表示现在，C表示将来
A : P a s t B : N o w C : F u t u r e A: Past \quad B: Now \quad C: Future A:PastB:NowC:Future
- 解读1：假设我们已知当下和过去，如果我们想去预测未来，只有当下对预测未来是有用的，过去可以忘记了
P ( C ∣ B A ) = P ( C ∣ B ) ( 1 ) P(C|BA) = P(C|B) \quad (1) P(C∣BA)=P(C∣B)(1)
- 解读2(等价解读)：如果当下是已知的，过去和未来是独立的，当下是连接过去和将来的纽带
P ( C A ∣ B ) = P ( C ∣ B ) P ( A ∣ B ) ( 2 ) P(CA|B ) = P(C|B)P(A|B) \quad (2) P(CA∣B)=P(C∣B)P(A∣B)(2)
我们验证一下这个式子，首先下面的全概率公式成立
P ( C A ) = P ( C ∣ A ) P ( A ) P(CA) = P(C|A)P(A) P(CA)=P(C∣A)P(A)
加入条件概率之后仍然成立
⇒ P ( C A ∣ B ) = P ( C ∣ B A ) P ( A ∣ B ) = P ( C ∣ B ) P ( A ∣ B ) \Rightarrow P(CA|B) = P(C|BA)P(A|B) = P(C|B)P(A|B) ⇒P(CA∣B)=P(C∣BA)P(A∣B)=P(C∣B)P(A∣B)
证明了(1)->(2)，再证明(2)->(1)
对于条件概率有这样的式子成立
P ( C ∣ A ) = P ( C A ) P ( A ) P(C|A) = \frac{P(CA)}{P(A)} P(C∣A)=P(A)P(CA)
⇒ P ( C ∣ B A ) = P ( C A ∣ B ) P ( A ∣ B ) = P ( C ∣ B ) P ( A ∣ B ) P ( A ∣ B ) = P ( C ∣ B ) \Rightarrow P(C|BA) = \frac{P(CA|B)}{P(A|B)} =\frac{P(C|B)P(A|B)}{P(A|B)} = P(C|B) ⇒P(C∣BA)=P(A∣B)P(CA∣B)=P(A∣B)P(C∣B)P(A∣B)=P(C∣B)
2.3 马尔科夫性的扩展
P ( Z n ∣ Z n − 1 , . . . , Z 1 ) = P ( Z n ∣ Z n − 1 ) ( a ) P(Z_n | Z_{n-1},...,Z_1) = P(Z_n|Z_{n-1}) \quad\quad (a) P(Zn∣Zn−1,...,Z1)=P(Zn∣Zn−1)(a)
2.3.1 模糊未来
如果现在，对未来的条件进行模糊，马尔科夫性是否还是成立的?
P ( Z n ∈ A ∣ Z n − 1 = X n − 1 , . . , Z 1 = X 1 ) = P ( Z n ∈ A ∣ Z n − 1 = X n − 1 ) ( b ) P(Z_n \in A|Z_{n-1} = X_{n-1},..,Z_1 = X_1) = P(Z_n \in A | Z_{n-1} = X_{n-1}) \quad\quad (b) P(Zn∈A∣Zn−1=Xn−1,..,Z1=X1)=P(Zn∈A∣Zn−1=Xn−1)(b)
证明一下
Let a k ∈ A P ( Z n ∈ A ∣ Z n − 1 = X n − 1 , . . , Z 1 = X 1 ) = ∑ k P ( Z n = a k ∣ Z n − 1 = X n − 1 , . . , Z 1 = X 1 ) = ∑ k P ( Z n = a k ∣ Z n − 1 = X n − 1 ) = P ( Z n ∈ A ∣ Z n − 1 = X n − 1 ) \text{Let } a_k \in A \\ P(Z_n \in A|Z_{n-1} = X_{n-1},..,Z_1 = X_1) = \\ \sum_{k} P(Z_n = a_k|Z_{n-1} = X_{n-1},..,Z_1 = X_1) \\ = \sum_{k} P(Z_n = a_k|Z_{n-1} = X_{n-1}) = P(Z_n \in A | Z_{n-1} = X_{n-1}) Let ak∈AP(Zn∈A∣Zn−1=Xn−1,..,Z1=X1)=k∑P(Zn=ak∣Zn−1=Xn−1,..,Z1=X1)=k∑P(Zn=ak∣Zn−1=Xn−1)=P(Zn∈A∣Zn−1=Xn−1)
因为未来本来就是不知道的，多了一些模糊性，不影响马尔科夫性质。
2.3.2 模糊过去
未来是可以模糊的，那么过去是可以模糊的吗?
P ( Z n = X n ∣ Z n − 1 = X n , Z n − 2 ∈ A ) = P ( Z n = X n ∣ Z n − 1 = X n − 1 ) ( c ) P(Z_n = X_n | Z_{n-1}= X_n,Z_{n-2} \in A) = P(Z_n = X_n | Z_{n-1} = X_{n-1}) \quad\quad (c) P(Zn=Xn∣Zn−1=Xn,Zn−2∈A)=P(Zn=Xn∣Zn−1=Xn−1)(c)
从直观上感受是可以的，因为过去本来就是要被丢弃的，模糊一下不应该结果。证明的时候需要注意一下，因为条件号后面的东西是不可以加和的
我们来证明一下，首先根据全概率公式，我们可以做这样的展开
P ( A C ) = P ( A ∣ C ) P ( C ) P ( Z n = X n , ( Z n − 2 , . . . , Z 0 ) ∈ A ∣ Z n − 1 = X n − 1 ) = P ( Z n = X n ∣ Z n − 1 = X n − 1 , ( Z n − 2 , . . . , Z 0 ) ∈ A ) P ( ( Z n − 2 , . . . , Z 0 ) ∈ A ∣ Z n − 1 = X n − 1 ) { 1 } P(AC) = P(A|C)P(C) \\ P(Z_n = X_n,(Z_{n-2},...,Z_0)\in A|Z_{n-1}=X_{n-1}) \\ = P(Z_n = X_n|Z_{n-1}=X_{n-1},(Z_{n-2},...,Z_0)\in A)P((Z_{n-2},...,Z_0)\in A|Z_{n-1}=X_{n-1}) \quad\quad \{1\} P(AC)=P(A∣C)P(C)P(Zn=Xn,(Zn−2,...,Z0)∈A∣Zn−1=Xn−1)=P(Zn=Xn∣Zn−1=Xn−1,(Zn−2,...,Z0)∈A)P((Zn−2,...,Z0)∈A∣Zn−1=Xn−1){1}
这个式子也可以变成累加和的形式
P ( Z n = X n , ( Z n − 2 , . . . , Z 0 ) ∈ A ∣ Z n − 1 = X n ) = ∑ ( Z n − 2 , . . . , Z 0 ) ∈ A P ( Z n = X n , Z n − 2 , . . . , Z 0 ) ∣ Z n − 1 = X n − 1 ) P(Z_n = X_n,(Z_{n-2},...,Z_0)\in A|Z_{n-1}=X_n) \\ = \sum_{(Z_{n-2},...,Z_0)\in A} P(Z_n = X_n,Z_{n-2},...,Z_0)|Z_{n-1}=X_{n-1}) P(Zn=Xn,(Zn−2,...,Z0)∈A∣Zn−1=Xn)=(Zn−2,...,Z0)∈A∑P(Zn=Xn,Zn−2,...,Z0)∣Zn−1=Xn−1)
然后利用马尔科夫性可以做这样的展开
P ( A C ∣ B ) = P ( A ∣ B ) P ( C ∣ B ) P ( Z n = X n , ( Z n − 2 , . . . , Z 0 ) ∈ A ∣ Z n − 1 = X n − 1 ) = ∑ ( Z n − 2 , . . . , Z 0 ) ∈ A P ( Z n = X n ∣ Z n − 1 = X n − 1 ) P ( Z n − 2 , . . . , Z 0 ) ∣ Z n − 1 = X n − 1 ) = P ( Z n = X n ∣ Z n − 1 = X n − 1 ) ∑ ( Z n − 2 , . . . , Z 0 ) ∈ A P ( Z n − 2 , . . . , Z 0 ) ∣ Z n − 1 = X n − 1 ) = P ( Z n = X n ∣ Z n − 1 = X n − 1 ) P ( ( Z n − 2 , . . . , Z 0 ) ∈ A ∣ Z n − 1 = X n − 1 ) { 2 } P(AC|B)=P(A|B)P(C|B) \\ P(Z_n = X_n,(Z_{n-2},...,Z_0)\in A|Z_{n-1}=X_{n-1})\\ =\sum_{(Z_{n-2},...,Z_0)\in A} P(Z_n = X_n|Z_{n-1}=X_{n-1})P(Z_{n-2},...,Z_0)|Z_{n-1}=X_{n-1}) \\ = P(Z_n = X_n|Z_{n-1}=X_{n-1})\sum_{(Z_{n-2},...,Z_0)\in A}P(Z_{n-2},...,Z_0)|Z_{n-1}=X_{n-1}) \\ = P(Z_n = X_n|Z_{n-1}=X_{n-1})P((Z_{n-2},...,Z_0)\in A|Z_{n-1}=X_{n-1}) \quad\quad \{2\} P(AC∣B)=P(A∣B)P(C∣B)P(Zn=Xn,(Zn−2,...,Z0)∈A∣Zn−1=Xn−1)=(Zn−2,...,Z0)∈A∑P(Zn=Xn∣Zn−1=Xn−1)P(Zn−2,...,Z0)∣Zn−1=Xn−1)=P(Zn=Xn∣Zn−1=Xn−1)(Zn−2,...,Z0)∈A∑P(Zn−2,...,Z0)∣Zn−1=Xn−1)=P(Zn=Xn∣Zn−1=Xn−1)P((Zn−2,...,Z0)∈A∣Zn−1=Xn−1){2}
{1}和{2}相等可以得到
P ( Z n = X n ∣ Z n − 1 = X n − 1 , ( Z n − 2 , . . . , Z 0 ) ∈ A ) P ( ( Z n − 2 , . . . , Z 0 ) ∈ A ∣ Z n − 1 = X n − 1 ) = P ( Z n = X n ∣ Z n − 1 = X n − 1 ) P ( ( Z n − 2 , . . . , Z 0 ) ∈ A ∣ Z n − 1 = X n − 1 ) ⇒ P ( Z n = X n ∣ Z n − 1 = X n − 1 , ( Z n − 2 , . . . , Z 0 ) ∈ A ) = P ( Z n = X n ∣ Z n − 1 = X n − 1 ) P(Z_n = X_n|Z_{n-1}=X_{n-1},(Z_{n-2},...,Z_0)\in A)P((Z_{n-2},...,Z_0)\in A|Z_{n-1}=X_{n-1}) \\ = P(Z_n = X_n|Z_{n-1}=X_{n-1})P((Z_{n-2},...,Z_0)\in A|Z_{n-1}=X_{n-1}) \\ \Rightarrow P(Z_n = X_n|Z_{n-1}=X_{n-1},(Z_{n-2},...,Z_0)\in A) = P(Z_n = X_n|Z_{n-1}=X_{n-1}) P(Zn=Xn∣Zn−1=Xn−1,(Zn−2,...,Z0)∈A)P((Zn−2,...,Z0)∈A∣Zn−1=Xn−1)=P(Zn=Xn∣Zn−1=Xn−1)P((Zn−2,...,Z0)∈A∣Zn−1=Xn−1)⇒P(Zn=Xn∣Zn−1=Xn−1,(Zn−2,...,Z0)∈A)=P(Zn=Xn∣Zn−1=Xn−1)
即得到了证明
2.3.3 模糊当前
当前是能够模糊的吗？
P ( Z n = X n ∣ Z n − 1 ∈ A , Z n − 2 = X n − 2 ) = P ( Z n = X n ∣ Z n − 1 ∈ A ) ( d ) P(Z_n = X_n | Z_{n-1}\in A,Z_{n-2} =X_{n-2}) \cancel= P(Z_n = X_n | Z_{n-1} \in A) \quad\quad (d) P(Zn=Xn∣Zn−1∈A,Zn−2=Xn−2)= P(Zn=Xn∣Zn−1∈A)(d)
答案是不能的。这里还是进行直观的描述
如果我们当前状态是确定的，我们就可以不需要记住是怎么来的，之间往下一个状态进行跳转即可
如果我们当前状态是不确定的，我们想往下一个状态进行跳转，我们就得知道我们当前在哪，也就需要知道是怎么来的。因为可能会有很多条路径
因此只有当前是确定的时候，过去才是可以忘记的。
3. 转移概率
3.1 转移概率引入
下面我们引入马尔科夫链中一个非常重要的概念–转移概率,我们想通过转移概率来挖掘马尔科夫链的运行规律
假设有一个离散的随机过程，这个随机过程中的每一个随机变量都属于同一个离散的状态空间
{ Z n } n = 0 ∞ Z k ∈ S = { x 1 , x 2 , . . . , x n , . . . } \{ Z_n \}_{n=0}^{\infty} \quad Z_k \in S = \{x_1,x_2,...,x_n,...\} {Zn}n=0∞Zk∈S={x1,x2,...,xn,...}
我们希望了解这样一个随机过程的联合概率密度。也就是任意n个时刻的联合分布
P ( Z n = x n , . . . , Z 0 = x 0 ) = P ( Z n = x n ∣ Z n − 1 = x n − 1 , . . . , Z 0 = x 0 ) ∗ P ( Z n − 1 = x n − 1 ∣ Z n − 2 = x n − 2 , . . . , Z 0 = x 0 ) ∗ . . . ∗ P ( Z 1 = x 1 ∣ Z 0 = x 0 ) P ( Z 0 = x 0 ) P(Z_n = x_n,...,Z_0 = x_0) \\ = P(Z_n = x_n|Z_{n-1}=x_{n-1},...,Z_0 = x_0)*P(Z_{n-1}=x_{n-1}|Z_{n-2}=x_{n-2},...,Z_0 = x_0)\\ *...*P(Z_1 = x_1|Z_0 = x_0) P(Z_0 = x_0) P(Zn=xn,...,Z0=x0)=P(Zn=xn∣Zn−1=xn−1,...,Z0=x0)∗P(Zn−1=xn−1∣Zn−2=xn−2,...,Z0=x0)∗...∗P(Z1=x1∣Z0=x0)P(Z0=x0)
这个式子可以根据马尔科夫性进行简化
P ( Z n = x n , . . . , Z 0 = x 0 ) = ( ∏ k = 1 n P ( Z k = x k ∣ Z k − 1 = x k − 1 ) ) P ( Z 0 = x 0 ) P(Z_n = x_n,...,Z_0 = x_0) = (\prod_{k=1}^nP(Z_k = x_k|Z_{k-1}=x_{k-1}))P(Z_0 = x_0) P(Zn=xn,...,Z0=x0)=(k=1∏nP(Zk=xk∣Zk−1=xk−1))P(Z0=x0)
这个联乘的概率就是转移概率
Transition Probability P ( Z n = x n ∣ Z n − 1 = x n − 1 ) \text{Transition Probability} \\ P(Z_n = x_n | Z_{n-1} = x_{n-1}) Transition ProbabilityP(Zn=xn∣Zn−1=xn−1)
3.2 转移概率的推广与简化
3.2.1 推广
事实上，转移概率中两个时刻不一定要相邻。也可以使得跳跃之间间隔n-m，就是一个经过了多次跳跃的复杂转移。我们可以用下面的形式来获得转移概率的推广表示
P ( Z n = x n ∣ Z n − 1 = x n − 1 ) ⇒ P ( Z n = x n ∣ Z m = x m ) ⇒ P ( Z n = j ∣ Z m = i ) = P i j ( n , m ) P(Z_n = x_n | Z_{n-1} = x_{n-1}) \Rightarrow P(Z_n = x_n | Z_{m} = x_{m}) \\ \Rightarrow P(Z_n = j| Z_m = i) = P_{ij}(n,m) P(Zn=xn∣Zn−1=xn−1)⇒P(Zn=xn∣Zm=xm)⇒P(Zn=j∣Zm=i)=Pij(n,m)
Pi,j(n,m)是转移概率的标准表达，转移概率有两个要素，一个是空间要素，这里i和j表示从起点i到终点j。令一个要素是时间，在这里表示m时刻位于位置i，n时刻位于位置j。
转移概率是个随机过程，一旦能够把这个转移概率计算清楚，就能够得到清晰的马尔科夫链。
任意一个多元概率分布，都是可以表示转移概率乘积的方式,即使这个多元分布是有跳步的。
P ( Z 5 = k , Z 3 = j , Z 1 = i ) = = P ( Z 5 = k ∣ Z 3 = j , Z 1 = i ) P ( Z 3 = j ∣ Z 1 = i ) P ( Z 1 = i ) = P i j ( 3 , 1 ) P j k ( 5 , 3 ) P ( Z 1 = i ) P(Z_5 = k,Z_3 = j,Z_1 = i) = \\ = P(Z_5 = k|Z_3 = j,Z_1 = i)P(Z_3 = j|Z_1 = i)P(Z_1 = i) \\ =P_{ij}(3,1)P_{jk}(5,3)P(Z_1 = i) P(Z5=k,Z3=j,Z1=i)==P(Z5=k∣Z3=j,Z1=i)P(Z3=j∣Z1=i)P(Z1=i)=Pij(3,1)Pjk(5,3)P(Z1=i)
而用马尔科夫性得到的概率中有一个单项，我们可以用全概率公式展开为初始概率和转移概率乘积的方式。初始概率一定是个已知的。
P ( Z 1 = i ) = ∑ k P ( Z 1 = i ∣ Z 0 = k ) P ( Z 0 = k ) P(Z_1 = i) = \sum_k P(Z_1 = i|Z_0=k)P(Z_0=k) P(Z1=i)=k∑P(Z1=i∣Z0=k)P(Z0=k)
因此，我们知道，只要知道了转移概率和初始概率，我们就可以求得任意一个马尔科夫链
Initial Distribution Transition Probability \text{Initial Distribution} \\ \text{Transition Probability} Initial DistributionTransition Probability
3.2.2 平稳转移概率–四维简化到三维
现在我们想对转移概率进行简化，因为每一个转移概率都有四个参数，如果这样的话要计算很多的转移概率。我们希望通过某些手段，让转移概率依赖的参数尽可能变少
P i j ( n , m ) P_{ij}(n,m) Pij(n,m)
为了简化这个转移概率，我们要继续增加平稳性的假设。这是我们第三个接触的平稳性。我们最早接触了宽平稳，限定的是一阶矩和二阶矩的不变性。然后在泊松过程中，我们接触了平稳增量特性，限定的是强度不变。
我们对马尔科夫链增加一个平稳的条件，就是平稳转移概率。指的是，一个转移行为，仅仅依赖于步长，而与该行为发生的时刻没有关系。
Stationary Transition Probability P i j ( n , m ) = P i j ( n − m ) \text{Stationary Transition Probability} \\ P_{ij}(n,m) = P_{ij}(n-m) Stationary Transition ProbabilityPij(n,m)=Pij(n−m)
增加了平稳转移概率的条件之后，我们的转移概率就从四维量变成了三维量，现在转移行为仅仅依赖于步长(耗时)
3.2.3 Chapman-Kolmogorov方程–三维简化到二维
(1) 概述
即使我们引入了平稳转移概率的定义，这个时候转移概率仍然是个三维量，还是很复杂。
事实上，转移概率是可以继续转化为若干个概率的和的
P i j ( n ) = P ( 1 ) + P ( 2 ) + . . . + P ( n ) + . . . P_{ij}(n) = P^{(1)} + P^{(2)}+...+P^{(n)}+... Pij(n)=P(1)+P(2)+...+P(n)+...
可以直观的来看待这个事情。假设从i经过了5步到了j，那么从i到j必然有很多条路线，每条路径的概率和就是i到j经过5步的转移概率。而每一条路径的概率是若干个一步转移概率的乘积。
P i j ( 5 ) = P i j ( 5 ) p a t h 1 + . . . + P i j ( 5 ) p a t h n P i j ( 5 ) p a t h = P i a ( 1 ) ∗ . . . ∗ P m j ( 1 ) P_{ij}(5) = P_{ij}(5)_{path1}+ ... + P_{ij}(5)_{pathn} \\ P_{ij}(5)_{path} = P_{ia}(1)*...*P_{mj}(1) Pij(5)=Pij(5)path1+...+Pij(5)pathnPij(5)path=Pia(1)∗...∗Pmj(1)
因此，一个多步的转移概率，必定是若干个单步转移概率的加法与乘法的组合。
如果我们能够找到这种组合的方法，转移概率中还剩下的一个时间维度就可以消除了，转移概率就从刚才的三维变成两维了。
(2) CK方程直观表示
而实现多步转移概率拆分为单步转移概率组合的方法吗，就是Chapman-Kolmogorov Equation。而一旦转移概率变成了二维量，就可以用矩阵表示了。
Chapman-Kolmogorov Equation P i j ( n ) = ∑ k P i k ( m ) P k j ( n − m ) ∀ m < n \text{Chapman-Kolmogorov Equation} \\ P_{ij}(n) = \sum_k P_{ik}(m)P_{kj}(n-m) \quad \forall m<n Chapman-Kolmogorov EquationPij(n)=k∑Pik(m)Pkj(n−m)∀m<n
这个方程我们也可以直观表示一下
我们可以以空间为依据进行分治，假设从i到j有很多条路径，我们选择一个时刻，把在这个时刻到达了这个状态的路径归为一类。然后再在这一类中继续拆分，这样就能够让每一个分类中的路径变短，直到最后成了1步转移。
(3) CK方程证明
然后我们来证明一下Chapman-Kolmogorov Equation
Prove
P
i
j
(
n
)
=
∑
k
P
i
k
(
m
)
P
k
j
(
n
−
m
)
∀
m
<
n
\text{Prove } \\ P_{ij}(n) = \sum_k P_{ik}(m)P_{kj}(n-m) \quad \forall m<n
Prove Pij(n)=k∑Pik(m)Pkj(n−m)∀m<n
证明如下
P i j ( n ) = P ( Z n = j ∣ Z 0 = i ) = ∑ k P ( Z n = j , Z m = k ∣ Z 0 = i ) P_{ij}(n) = P(Z_n=j|Z_0 = i) \\ = \sum_k P(Z_n = j,Z_m = k|Z_0 = i) Pij(n)=P(Zn=j∣Z0=i)=k∑P(Zn=j,Zm=k∣Z0=i)
我们可以插入中间点转换概率，然后使用条件概率公式展开
P ( A B ) = P ( A ∣ B ) P ( B ) P(AB) = P(A|B)P(B) P(AB)=P(A∣B)P(B)
P i j ( n ) = ∑ k P ( Z n = j , Z m = k ∣ Z 0 = i ) = ∑ k P ( Z n = j ∣ Z m = k , Z 0 = i ) P ( Z m = k ∣ Z 0 = i ) P_{ij}(n) = \sum_k P(Z_n = j,Z_m = k|Z_0 = i) \\ = \sum_k P(Z_n = j|Z_m = k,Z_0 = i) P(Z_m = k|Z_0 = i) Pij(n)=k∑P(Zn=j,Zm=k∣Z0=i)=k∑P(Zn=j∣Zm=k,Z0=i)P(Zm=k∣Z0=i)
再通过马尔科夫性，即可证明结论
P i j ( n ) = ∑ k P ( Z n = j ∣ Z m = k , Z 0 = i ) P ( Z m = k ∣ Z 0 = i ) = ∑ k P ( Z n = j ∣ Z m = k ) P ( Z m = k ∣ Z 0 = i ) = ∑ k P k j ( n − m ) P i k ( m ) P_{ij}(n)= \sum_k P(Z_n = j|Z_m = k,Z_0 = i) P(Z_m = k|Z_0 = i) \\ = \sum_k P(Z_n = j|Z_m = k) P(Z_m = k|Z_0 = i) \\ = \sum_k P_{kj}(n-m) P_{ik}(m) Pij(n)=k∑P(Zn=j∣Zm=k,Z0=i)P(Zm=k∣Z0=i)=k∑P(Zn=j∣Zm=k)P(Zm=k∣Z0=i)=k∑Pkj(n−m)Pik(m)
CK方程是通过空间维度对转移概率进行简化的
Spatial Simplification \text{Spatial Simplification} Spatial Simplification
(4) CK方程与转移概率的简化
CK方程与矩阵乘法非常相似
C = A B C i j = ∑ k A i k B k j C = AB \\ C_{ij} = \sum_k A_{ik} B_{kj} C=ABCij=k∑AikBkj
我们给一个n步转移概率的定义。其实就是转移概率矩阵。
这个矩阵的第i行第j列就是从i经过n步到达j的概率
P ( n ) = ( P i j ( n ) ) i j P(n) = (P_{ij}(n))_{ij} P(n)=(Pij(n))ij
我们用CK方程表示转移概率矩阵
P ( n ) = P ( m ) P ( n − m ) P(n) = P(m)P(n-m) P(n)=P(m)P(n−m)
基于这个方程，我们可以把n步转移概率矩阵表示为
P ( n ) = P ( 1 ) P ( n − 1 ) = ( P ( 1 ) ) 2 P ( n − 2 ) = . . . = ( P ( 1 ) ) n P(n) = P(1)P(n-1)= (P(1))^2 P(n-2) = ...=(P(1))^n P(n)=P(1)P(n−1)=(P(1))2P(n−2)=...=(P(1))n
因此，我们只需要知道一步转移概率矩阵即可计算出任意一个转移概率矩阵
3.2.4 小结
通过平稳性，我们可以把时间维度从2维变成1维。而通过ck方程，我们可以把时间维度从1维变成0维。因此，我们就不需要记录时间的维度了。多步转移概率矩阵可以通过一步转移概率矩阵变换得到。
因此，我们只要有一个一步转移概率矩阵和一个初始概率向量，我们就可以得到一切n维随机变量的联合分布
P ( Z n = x n , . . . , Z 0 = x 0 ) = ( ∏ k = 1 n P ( Z k = x k ∣ Z k − 1 = x k − 1 ) ) P ( Z 0 = x 0 ) P(Z_n = x_n,...,Z_0 = x_0) = (\prod_{k=1}^nP(Z_k = x_k|Z_{k-1}=x_{k-1}))P(Z_0 = x_0) P(Zn=xn,...,Z0=x0)=(k=1∏nP(Zk=xk∣Zk−1=xk−1))P(Z0=x0)
(
∏
k
=
1
n
P
(
Z
k
=
x
k
∣
Z
k
−
1
=
x
k
−
1
)
)
⇒
Calculate by One-Step Transition Matrix
P
(
Z
0
=
x
0
)
⇒
Initial Probability Vector
(\prod_{k=1}^nP(Z_k = x_k|Z_{k-1}=x_{k-1})) \Rightarrow \text{Calculate by One-Step Transition Matrix} \\ P(Z_0 = x_0) \Rightarrow \text{Initial Probability Vector}
(k=1∏nP(Zk=xk∣Zk−1=xk−1))⇒Calculate by One-Step Transition MatrixP(Z0=x0)⇒Initial Probability Vector
一个矩阵和一个矢量，我们就能够得到马尔科夫链的所有信息
One-Step Transition Matrix
+
Initial Probability Vector
=
Everything
\text{One-Step Transition Matrix} + \text{Initial Probability Vector} = \text{Everything}
One-Step Transition Matrix+Initial Probability Vector=Everything
4. 基于马尔科夫性计算概率的例子
下面我们通过抛硬币的行为，利用马尔科夫性来进行概率计算，从而简单说明一下马尔科夫性的应用
假设抛硬币，正面出现的概率是P，反面出现的概率是1-P，我们想要知道第一次抛出正面的次数的期望。
Coin Tossing ( 1 0 P 1 − P ) \text{Coin Tossing} \quad \begin{pmatrix} 1 & 0 \\ P & 1-P \end{pmatrix} Coin Tossing(1P01−P)
4.1 基本做法
一般的思路是，先计算出k次才抛出正面的分布。这个分布是一个几何分布:如果第k次才是正面，必然说明前k-1次都是反面，然后第k次是正面。
P ( N = k ) = ( 1 − P ) k − 1 P P(N=k) = (1-P)^{k-1}P P(N=k)=(1−P)k−1P
然后使用这个分布求期望，得到的就是第一次抛出正面需要次数的期望
E ( N ) = ∑ k = 1 ∞ k ( 1 − P ) k − 1 P = 1 P E(N) = \sum_{k=1}^{\infty}k(1-P)^{k-1}P = \frac{1}{P} E(N)=k=1∑∞k(1−P)k−1P=P1
这里计算一下这个式子
E ( N ) = ∑ k = 1 ∞ k ( 1 − P ) k − 1 P Let x = 1 − P E ( N ) = ∑ k = 1 ∞ k ( x ) k − 1 P = ∑ k = 1 ∞ d x k d x P = d ∑ k = 1 ∞ ( x k ) d x P = ( 1 ∗ ( 1 − x ) n 1 − x ) ′ P = 1 P 2 ∗ P = 1 P E(N) = \sum_{k=1}^{\infty}k(1-P)^{k-1}P \\ \text{Let } x = 1-P \\ E(N) = \sum_{k=1}^{\infty}k(x)^{k-1}P =\sum_{k=1}^{\infty} \frac{d x^k}{dx} P \\ = \frac{d\sum_{k=1}^{\infty}(x^k)}{dx} P =(1*\frac{(1-x)^n}{1-x})' P = \frac{1}{P^2}*P \\ = \frac{1}{P} E(N)=k=1∑∞k(1−P)k−1PLet x=1−PE(N)=k=1∑∞k(x)k−1P=k=1∑∞dxdxkP=dxd∑k=1∞(xk)P=(1∗1−x(1−x)n)′P=P21∗P=P1
4.2 基于马尔科夫性的解法
其实基于传统的解法不是非常合理，因为期望是对整个系统的一种很粗浅的描述，而概率密度是对整个系统非常精确的一种描述，如果有了概率密度，其实也不是非常需要期望。而马尔科夫的思路，可以让我们不需要使用概率密度就能够求解
我们可以这样思考我们的问题，如果我们抛出了一次硬币，是正面，我们就不用抛了。而如果我们第一次抛出硬币是反面，相当于我们状态又变成了从头开始，这次反面对后面的影响，不过是使得次数多了一次而已
E ( N ) = E ( E ( N ∣ Z 1 ) ) = E ( N ∣ Z 1 = 1 ) P ( Z 1 = 1 ) + E ( N ∣ Z 1 = 0 ) P ( Z 1 = 0 ) = E ( N ∣ Z 1 = 1 ) P ( Z 1 = 1 ) + ( 1 + E ( N ) ) P ( Z 1 = 0 ) = 1 ∗ P + ( 1 + E ( N ) ) ( 1 − P ) E ( N ) = 1 P E(N) = E(E(N|Z_1)) = E(N|Z_1 = 1) P(Z_1 = 1) + E(N|Z_1 = 0)P(Z_1 = 0) \\ = E(N|Z_1 = 1) P(Z_1 = 1) +(1+E(N))P(Z_1 = 0) \\ = 1*P + (1+E(N))(1-P) \\ E(N) = \frac{1}{P} E(N)=E(E(N∣Z1))=E(N∣Z1=1)P(Z1=1)+E(N∣Z1=0)P(Z1=0)=E(N∣Z1=1)P(Z1=1)+(1+E(N))P(Z1=0)=1∗P+(1+E(N))(1−P)E(N)=P1
这个问题还可以再扩展一下，我们希望连续两次投硬币都是正面，第一次出现这种情况的次数的期望是多少?
E ( N ) = E ( E ( N ∣ Z 1 , Z 2 ) ) = E ( N ∣ Z 1 = 0 ) P ( Z 1 = 0 ) + E ( N ∣ Z 1 = 1 , Z 2 = 0 ) P ( Z 1 = 1 ) P ( Z 2 = 0 ) + E ( N ∣ Z 1 = 1 , Z 2 = 1 ) P ( Z 1 = 1 ) P ( Z 2 = 1 ) = ( 1 + E ( N ) ) ( 1 − P ) + ( 2 + E ( N ) ) P ( 1 − P ) + 2 ∗ P ∗ P = ( 1 + E ( N ) ) ( 1 − P ) + ( 2 + E ( N ) ) P ( 1 − P ) + 2 P 2 E ( N ) = 1 + P P 2 E(N) = E(E(N|Z_1,Z_2)) \\ = E(N|Z_1=0)P(Z_1 = 0) + E(N|Z_1=1,Z_2 = 0)P(Z_1 = 1)P(Z_2 = 0) + E(N|Z_1=1,Z_2 = 1)P(Z_1 = 1)P(Z_2 = 1) \\ = (1+E(N)) (1-P) + (2+E(N)) P(1-P) + 2*P*P \\ =(1+E(N)) (1-P) +(2+E(N)) P(1-P) +2P^2 \\ E(N) = \frac{1+P}{P^2} E(N)=E(E(N∣Z1,Z2))=E(N∣Z1=0)P(Z1=0)+E(N∣Z1=1,Z2=0)P(Z1=1)P(Z2=0)+E(N∣Z1=1,Z2=1)P(Z1=1)P(Z2=1)=(1+E(N))(1−P)+(2+E(N))P(1−P)+2∗P∗P=(1+E(N))(1−P)+(2+E(N))P(1−P)+2P2E(N)=P21+P
通过这样的两个例子，我们就了解了马尔科夫性的重要性。
5. 马尔科夫链稳态分析前置知识
5.1 概述
接下来会对马氏链的稳态进行分析，这是一种定性行为。我们假设状态空间只有两种状态的转移
我们描绘一下转移概率矩阵。这是一步状态转移矩阵，然后我们可以通过转移概率矩阵的n次幂判断其稳定性
P
=
(
1
−
P
P
P
1
−
P
)
P = \begin{pmatrix} 1-P & P \\ P & 1-P \end{pmatrix}
P=(1−PPP1−P)
qualitative
Stable Behavior
\text{qualitative} \\ \text{Stable Behavior}
qualitativeStable Behavior
⇒ P n \Rightarrow P^n ⇒Pn
马氏链最终会变换成一个随机变量
P i j ( n ) P_{ij}(n) Pij(n)
5.2 相关概念
5.2.1 可达
Reachable \text{Reachable} Reachable
从i到j可达是指，能够找到一个n，使得从i到j的n步转移概率大于0，也就是从i到j是有路径到达的，这个路径是有向路径
i , j i → j ⇔ ∃ n P i j ( n ) > 0 i,j \quad i\rightarrow j \Leftrightarrow \exists n \quad P_{ij}(n) >0 i,ji→j⇔∃nPij(n)>0
5.2.2 相通
Commutative \text{Commutative} Commutative
两个状态相通是指，从i可达j，并且从j可达i。这二者可以不是同一条路径。相通是指双向可达。
i ↔ j ⇔ i → j j → i i \leftrightarrow j \Leftrightarrow i \rightarrow j \quad j \rightarrow i i↔j⇔i→jj→i
5.2.3 闭集
Closed Set \text{Closed Set} Closed Set
来说明一下闭集的概念。假设所有状态是全集S，S中的一个子集是C，如果C是个闭集，那么，如果i在C中，而j不在C中，i不可达j。闭集是一个只能进不能出的集合。
S C ⊂ S C is Closed ⇔ i ∈ C , j ∈ C ⇒ i → j S \quad C \subset S \quad \text{C is Closed} \\ \Leftrightarrow i \in C, \quad j \cancel \in C \Rightarrow i \cancel \rightarrow j SC⊂SC is Closed⇔i∈C,j∈ C⇒i→ j
5.2.4 约化
Reduction \text{Reduction} Reduction
如果集合C是一个闭集，闭集说明状态的转移只能在自身内部进行。如果我们把闭集C之外的状态全部抹去，剩下的仍然是一个完整的马尔科夫链。从大马尔科夫链简化到小马尔科夫链的过程叫做约化
约化的好处在于，等里面的闭集研究清楚了之后，再研究外面的，只需要了解怎么从外面转移进来的就行了
最后马尔科夫链会变成一种，只有闭集或者只向闭集内转移的状态
通过约化能够减少一步转移矩阵的规模，求幂次就变得简单了。
5.2.5 不可约
Irreducible \text{Irreducible} Irreducible
如果一个链没有闭的真子集，就叫做不可约
No Closed True Subset \text{No Closed True Subset} No Closed True Subset
如果一个马尔科夫链中没有闭集，就约化不动，等效于所有的状态都是相通的。
Irreducible ⇔ ∀ i , j i ↔ j \text{Irreducible} \Leftrightarrow \forall i,j \quad i \leftrightarrow j Irreducible⇔∀i,ji↔j
我们可以证明一下这个事情，如果所有状态都是相通的，证明这个集合是不可约的是平凡情况，不需要证明
Irreducible ⇐ ∀ i , j i ↔ j Trivial \text{Irreducible} \Leftarrow \forall i,j \quad i \leftrightarrow j \text{ Trivial} Irreducible⇐∀i,ji↔j Trivial
我们证明一下不可约能够证明状态是相通的，证明如下
∀ i A i = { j : i → j } ⇒ A i is closed \forall i \quad A_i = \{j: i \rightarrow j \} \Rightarrow A_i \text{ is closed} ∀iAi={j:i→j}⇒Ai is closed
我们可以这样证明，我们假设任意一个状态i，i可以到达的状态是j，由i可以到达的状态j构成的集合为Ai，如果我们能够证明Ai是个闭集，我们就能够证明所有的状态都是相通的。因为我们已知Ai不可约意味着没有闭的真子集，Ai如果是个闭集，必然意味着Ai是全集，i能够到达的状态是全集，而i又是任取的，必然意味着所有状态都是相通的。
现在我们的目标就是，证明i能够到达的状态的集合是个闭集
证明闭集可以这样证明
∀ j ∈ A i k ∈ A i ⇒ j → k \forall j \in A_i \quad k \cancel \in A_i \Rightarrow j \cancel \rightarrow k ∀j∈Aik∈ Ai⇒j→ k
我们假设j在集合Ai中，k不在集合Ai中，j必定到达不了k，如果这个证明了，Ai必定是个闭集。
我们可以使用反证法，我们假设j能够到达k,由于i能够到达j，而j能够达到k，必定i能够到达k，这样的话，k应该在集合Ai内，与已知相矛盾，因此证明Ai必定是个闭集。
Assume j → k Logic i → j ⇒ i → k ⇒ k ∈ A i Prove j → k ⇒ ∃ n P j k ( n ) > 0 i → j ⇒ ∃ m P i j ( m ) > 0 P i k ( m + n ) = ∑ l P i l ( m ) P l k ( n ) ≥ P i j ( m ) P j k ( n ) > 0 ⇒ i → k \text{Assume} \quad j\rightarrow k \\ \text{Logic}\\ i \rightarrow j \Rightarrow i \rightarrow k \Rightarrow k \in A_i \\ \text{Prove}\\ j \rightarrow k \Rightarrow \exists n \quad P_{jk}(n) > 0 \\ i \rightarrow j \Rightarrow \exists m \quad P_{ij}(m) >0 \\ P_{ik}(m+n) = \sum_l P_{il}(m)P_{lk}(n) \geq P_{ij}(m)P_{jk}(n) >0 \\ \Rightarrow i \rightarrow k Assumej→kLogici→j⇒i→k⇒k∈AiProvej→k⇒∃nPjk(n)>0i→j⇒∃mPij(m)>0Pik(m+n)=l∑Pil(m)Plk(n)≥Pij(m)Pjk(n)>0⇒i→k
然后我们就证明了，不可约等价于所有状态都是相通的
5.3 不可约与转移概率矩阵
我们从转移概率矩阵的角度体会一下可约和不可约。
一般来说，如果要对转移概率矩阵做行变换，列也要跟着变，不然会乱。而如果转移概率矩阵是可约的，可以通过初等行变换的方法，得到一个有一部分0的转移概率矩阵
得到的C是个完整的状态转移矩阵，C是个完整的马氏链。做幂次运算的时候，可以简化运算
P = ( A B 0 C ) P n = ( ∗ ∗ 0 C n ) P = \begin{pmatrix} A& B \\ 0 & C \end{pmatrix} \\ P^n = \begin{pmatrix} * & * \\ 0 & C^n \end{pmatrix} P=(A0BC)Pn=(∗0∗Cn)
如果C里面还有闭集，可以继续通过适合的行变换把矩阵变成阶梯状
如果马尔科夫链不可约化，那么所有状态都是相通的，矩阵是不能转化成没有0的部分的。
事实上，不可约矩阵不好证明。因为不可约矩阵没有肯定形式的定义，因此只能通过遍历来证明。
5.4 首达与CK方程
5.4.1 转移概率的时间分解
我们引入下一个概念，叫做首达。
First Passage \text{First Passage} First Passage
首达是指，从i出发经过n步首次到达j的概率，有这样的定义
f i j ( n ) = P ( Z n = j , Z n − 1 = j , . . . , Z 1 = j ∣ Z 0 = i ) f_{ij}(n) = P(Z_n = j,Z_{n-1}\cancel = j,...,Z_1 \cancel = j|Z_0 = i) fij(n)=P(Zn=j,Zn−1= j,...,Z1= j∣Z0=i)
f i j ( n ) ≤ P i j ( n ) f_{ij}(n) \leq P_{ij}(n) fij(n)≤Pij(n)
首达概率一定是小于转移概率的。
转移概率可以通过CK公式，基于空间进行分解。同样，转移概率也可以基于首达概率，基于时间进行分解。
P i j ( n ) = ∑ k = 1 n f i j ( k ) P j j ( n − k ) P_{ij}(n) = \sum_{k=1}^n f_{ij}(k) P_{jj}(n-k) Pij(n)=k=1∑nfij(k)Pjj(n−k)
这个式子的含义意思为，i经过n步到达j的转移概率可以分解为i通过k步首次到达k，然后在j上轮转了n-k步的概率的和。
5.4.2 转移概率的时间分解与空间分解比较
把时间分解和空间分解放到一起比较
P i j ( n ) = ∑ k = 1 n f i j ( k ) P j j ( n − k ) Temporal P i j ( n ) = ∑ k P i k ( m ) P k j ( n − m ) Spatial P_{ij}(n) = \sum_{k=1}^n f_{ij}(k) P_{jj}(n-k) \quad \text{ Temporal}\\ P_{ij}(n) = \sum_k P_{ik}(m)P_{kj}(n-m) \quad \text{ Spatial} Pij(n)=k=1∑nfij(k)Pjj(n−k) TemporalPij(n)=k∑Pik(m)Pkj(n−m) Spatial
5.4.3 转移概率的时间分解证明
我们来证明一下时间分解的公式
我们引入首达时刻的概念
T : First Passage Time T = m i n k { Z k = j ∣ Z 0 = i } T: \text{First Passage Time} \\ T = min_k \{Z_k = j | Z_0 = i\} T:First Passage TimeT=mink{Zk=j∣Z0=i}
P i j ( n ) = P ( Z n = j ∣ Z 0 = i ) = ∑ k = 1 n P ( Z n = j , T = k ∣ Z 0 = i ) P_{ij}(n) = P(Z_n=j|Z_0 = i) = \sum_{k=1}^n P(Z_n = j,T=k|Z_0 = i) Pij(n)=P(Zn=j∣Z0=i)=k=1∑nP(Zn=j,T=k∣Z0=i)
{ T = k } = { Z k = j , Z k − 1 = j , . . . , Z 1 = j } \{ T=k\} = \{ Z_k = j,Z_{k-1} \cancel=j,...,Z_{1} \cancel=j\} {T=k}={Zk=j,Zk−1= j,...,Z1= j}
我们可以在这里用全概率公式展开，这里T=k的意思是，k时刻到达了j，k-1一直到1时刻都从来没有到达过j
P
i
j
(
n
)
=
∑
k
=
1
n
P
(
Z
n
=
j
,
T
=
k
∣
Z
0
=
i
)
=
∑
k
=
1
n
P
(
Z
n
=
j
∣
T
=
k
,
Z
0
=
i
)
P
(
Z
k
=
j
,
Z
k
−
1
=
j
,
.
.
.
,
Z
1
=
j
∣
Z
0
=
i
)
=
∑
k
=
1
n
P
(
Z
n
=
j
∣
Z
k
=
j
,
Z
k
−
1
=
j
,
.
.
.
,
Z
1
=
j
,
Z
0
=
i
)
P
(
Z
k
=
j
,
Z
k
−
1
=
j
,
.
.
.
,
Z
1
=
j
∣
Z
0
=
i
)
P_{ij}(n) = \sum_{k=1}^n P(Z_n = j,T=k|Z_0 = i) \\ = \sum_{k=1}^n P(Z_n = j|T=k,Z_0 = i) P(Z_k = j,Z_{k-1} \cancel=j,...,Z_{1} \cancel=j|Z_0 = i) \\ = \sum_{k=1}^n P(Z_n = j|Z_k = j,Z_{k-1} \cancel=j,...,Z_{1} \cancel=j,Z_0 = i) P(Z_k = j,Z_{k-1} \cancel=j,...,Z_{1} \cancel=j|Z_0 = i)
Pij(n)=k=1∑nP(Zn=j,T=k∣Z0=i)=k=1∑nP(Zn=j∣T=k,Z0=i)P(Zk=j,Zk−1=
j,...,Z1=
j∣Z0=i)=k=1∑nP(Zn=j∣Zk=j,Zk−1=
j,...,Z1=
j,Z0=i)P(Zk=j,Zk−1=
j,...,Z1=
j∣Z0=i)
使用马尔科夫性
P i j ( n ) = ∑ k = 1 n P ( Z n = j ∣ Z k = j , Z k − 1 = j , . . . , Z 1 = j , Z 0 = i ) P ( Z k = j , Z k − 1 = j , . . . , Z 1 = j ∣ Z 0 = i ) = ∑ k = 1 n P ( Z n = j ∣ Z k = j ) P ( Z k = j , Z k − 1 = j , . . . , Z 1 = j ∣ Z 0 = i ) = ∑ k = 1 n P j j ( n − k ) f i j ( k ) P_{ij}(n) = \sum_{k=1}^n P(Z_n = j|Z_k = j,Z_{k-1} \cancel=j,...,Z_{1} \cancel=j,Z_0 = i) P(Z_k = j,Z_{k-1} \cancel=j,...,Z_{1} \cancel=j|Z_0 = i) \\ = \sum_{k=1}^n P(Z_n = j|Z_k = j) P(Z_k = j,Z_{k-1} \cancel=j,...,Z_{1} \cancel=j|Z_0 = i) \\ = \sum_{k=1}^n P_{jj}(n-k)f_{ij}(k) Pij(n)=k=1∑nP(Zn=j∣Zk=j,Zk−1= j,...,Z1= j,Z0=i)P(Zk=j,Zk−1= j,...,Z1= j∣Z0=i)=k=1∑nP(Zn=j∣Zk=j)P(Zk=j,Zk−1= j,...,Z1= j∣Z0=i)=k=1∑nPjj(n−k)fij(k)
就证明了我们的时间分解
P i j ( n ) = ∑ k = 1 n f i j ( k ) P j j ( n − k ) Temporal P_{ij}(n) = \sum_{k=1}^n f_{ij}(k) P_{jj}(n-k) \quad \text{ Temporal}\\ Pij(n)=k=1∑nfij(k)Pjj(n−k) Temporal