“马尔科夫链”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第510行： 第510行：
  
 
==连续时间马尔科夫链==
 
==连续时间马尔科夫链==
−
===<math>Q</math>矩阵及其指数===
 
−
在本节中我们首先引入Q矩阵的定义、说明它在连续时间马尔科夫链中的地位。接着进入纯粹的数学讨论，探讨如何将矩阵幂次连续化。最后我们会利用将矩阵幂次连续化的方法，建立连续时间马尔科夫链中Q矩阵与离散时间马尔科夫链中转移概率矩阵的等价关系。
 
  
−
====<math>Q</math>矩阵====
+
===基本性质===
−
令<math>I</math>为一个可数集，<math>I</math>上的矩阵<math>Q=(q_{ij}:i,j\in I)</math>若满足下面三个条件，则称其为<math>Q</math>矩阵：
+
====有限状态空间====
 +
=====直观模型=====
 +
=====模型参数=====
 +
=====P(t)与Q的关系
 +
====无限状态空间====
 +
=====爆炸=====
 +
=====P(t)与Q的关系
  
−
# <math>0\leq -q_{ii}<\infty ,\forall I</math>
 
−
# <math>q_{ij}\geq 0, \forall i\neq j</math>
 
−
# <math>\sum_{j\in I}q_{i,j}=0, \forall I</math>
 
  
−
有上面三个条件可知<math>Q</math>矩阵的每一行中的非对角线元素可以为任意非负实数，只需要满足每行非对角元素之和有限这一个限制:<math>q_i=\sum_{j\neq i}q_{ij}<\infty</math>。由于条件3使每一行的行和为零，所以对角线元素<math>q_{ii}=-q_{i}</math>
+
===过程描述===
−
 
+
====转移过程====
−
一种可以非常方便地展示Q矩阵的方法是通过转移速率图：
+
=====可约性=====
−
 
+
=====周期性=====
−
[[File:连续马尔科夫链图片示意.png|400px]]
+
====演化性质====
−
 
+
=====平稳分布=====
−
每一张转移速率图都与一个唯一的<math>Q</math>矩阵对应，上面图像对应的<math>Q</math>矩阵为：
+
=====细致平衡条件=====
−
 
+
=====时间可逆性=====
−
<math>Q=\begin{pmatrix}
 
−
-2 & 1 & 1 \\
 
−
1 & -1 & 0 \\
 
−
2 & 1 & -3
 
−
\end{pmatrix}
 
−
</math>
 
−
 
 
−
每一个非对角元素<math>q_{ij}</math>都确定了转移速率图中<math>(i,j)</math>箭头上的值，<math>q_i</math>的值并没有在转移速率图中出现，但你可以很容易地从给出的数值中算出来。<math>q_{ij}</math>是从<math>i</math>状态到<math>j</math>状态转移的速率，<math>q_i</math>的是离开状态<math>i</math>的速率，我们后面会详细解释它们的意义。
 
−
 
 
−
====矩阵幂次的连续化====
 
−
 
 
−
现在我们考虑一个纯粹的数学问题：对于一个有限集合<math>I</math>，以及一个矩阵<math>P= (p_{ij} : i,j\in I)</math>，是否存在一种自然的方式将离散序列<math>P^1,P^2,P^3…</math>中的“空隙”填满？我们利用级数来解决这个问题。
 
−
 
 
−
 
 
−
对于任意一个矩阵<math>Q=(q_{ij} : i,j \in I)</math>（注意本小节的<math>Q</math>指的任意矩阵，而不需要是<math>Q</math>矩阵），级数<math>\sum_{k=0}^\infty \frac{Q^k}{k!}</math>按分量收敛，我们把它的极限值记为<math>e^Q</math>。更进一步，如果两个矩阵<math>Q_1</math>和<math>Q_2</math>可交换，可以证明有<math>e^{Q_1+Q_2}=e^{Q_1}e^{Q_2}</math>（与实数中相应的证明很相似）。
 
−
 
 
−
 
 
−
假设对于矩阵<math>P</math>我们可以找到一个矩阵<math>Q</math>，使得<math>e^Q=P</math>。则有<math>e^{nQ}=(e^Q)^n=P^n</math>，很自然地<math>e^{tQ}（t\geq 0）</math>就填满了离散序列<math>P^1,P^2,P^3…</math>中的“空隙”。在这种连续化操作的基础上，我们能证明下面定理。
 
−
 
 
−
 
 
−
<math>Q</math>是一个有限集合<math>I</math>上的矩阵，令<math>P(t)=e^{tQ}</math>，则<math>P(t)(t\geq 0）</math>具有下面的性质：
 
−
# <math>P(s+t)=P(s)P(t),\forall s,t</math>（半群性质）
 
−
# <math>P(t)</math>是向前方程<math>\frac{d}{dt}P(t)=P(t)Q,P(0)=I</math>的唯一解
 
−
# <math>P(t)</math>是向后方程<math>\frac{d}{dt}P(t)=QP(t),P(0)=I</math>的唯一解
 
−
# <math>\left.\left(\frac{d}{dt}\right)^k\right|_{t=0}P(t)=Q^k,k=0,1,2,…</math>
 
−
 
 
−
====随机矩阵与Q矩阵的等价关系====
 
−
上一小节我们讨论的是矩阵指数的普遍性质，这一小节我们来看看<math>Q</math>的行为。先回忆一下，一个矩阵<math>P=(p_{ij}:i,j\in I)</math>是随机矩阵，当它满足：
 
−
# <math>0\leq p_{ij}<\infty ,\forall i,j</math>
 
−
# <math>\sum_{j\in I}p_{ij}=1 ,\forall i</math>
 
−
我们可以证明定理：一个定义在有限集合<math>I</math>上的矩阵<math>Q</math>是一个<math>Q</math>矩阵，当且仅当<math>P=e^{tQ}</math>对任意<math>t\geq 0</math>都是一个随机矩阵。
 
−
 
 
−
 
 
−
如果随机矩阵<math>P</math>可以用一个<math>Q</math>矩阵的矩阵指数表示成<math>P=e^Q</math>，我们可就以填补<math>P</math>所决定的随机过程的“空隙”。我们固定一个非零整数<math>m</math>,并令<math>(X^m_n)_{n\geq 0}</math>为离散时间马尔科夫链Markov(<math>\lambda,e^{Q/m}</math>)，再令<math>X_{n/m}=X^m_n</math>，就得到了一个具有时间参数为<math>\{n/m:n=0,1,2,…\}</math>的马尔科夫链。按我们的标记，当<math>m=1</math>，得到的<math>X_n</math>就是原来的离散时间马尔可夫链Markov（<math>\lambda,P</math>）。由<math>(e^{Q/m})^m=e^Q=P</math>，当我们在<math>X_{n/m}</math>中对时间参数取样为整数时，就得到了Markov（<math>\lambda,P</math>）。当m取得足够大的时候，时间参数就会被细分得足够地小，最终我们可以得到一个连续时间马尔科夫链<math>(X_t)_{t\geq 0}</math>，当对<math>t</math>取样为整数时，就回到了离散时间马尔科夫链Markov（<math>\lambda,P</math>）。
 
−
 
 
−
 
 
−
因此我们可以将离散时间马尔科夫链看做是连续时间马尔科夫链在时间参数整数点取样得到的特殊情况。稍微提前说明一下，一个具有<math>Q</math>矩阵<math>Q</math>的连续时间马尔科夫链<math>(X_t)_{t\geq 0}</math>满足：
 
−
 
 
−
<math>\mathbb{P}(X_{t_{n+1}}=|X_{t_0}=i_0,…,X_{t_n}=i_n)=p_{i_ni_{n+1}}(t_{n+1}-t_n)</math>
 
−
 
 
−
上式对所有<math>n=0,1,2,…</math>，所有时间<math>0\leq t_0\leq … \leq t_{n+1}</math>，以及所有状态<math>i_0,…,i_{n+1}</math>成立，其中<math>p_{ij}(t)</math>是<math>e^{tQ}</math>中位置为<math>(i,j)</math>的元素。特别的，在<math>t</math>时刻从状态<math>i</math>到状态<math>j</math>的转移概率由下式给出：
 
−
 
 
−
<math>\mathbb{P}(X_t=j):=\mathbb{P}(X_t=j|X_0=i)=p_{ij}(t)</math>
 
−
 
 
−
读者可以与离散时间马尔科夫链自行比较一下。
 
−
 
 
−
=== 连续时间随机过程 ===
 
−
 
 
−
==== 简单定义 ====
 
−
令<math>I</math>是一个可数集，则一个在[math]I[/math]中取值的连续时间随机过程<math>(X_t)_{t\geq 0}=(X_t:0\leq t<\infty)</math>，就是一系列随机变量<math>X_t:\Omega\to I</math>。我们接下来会讨论如何确定<math>(X_t)_{t\geq 0}</math>的概率行为，这一系列讨论让我们至少在理论上可以计算和这个过程相关的任何概率，比如<math>\mathbb{P}(X_t=i)</math>、<math>\mathbb{P}(X_{t_0}=i_0,\dots,X_{t_n}=i_n)</math>、<math>\mathbb{P}(X_t=i,t\in B\subseteq (0,\infty])</math>。与离散时间的情况相比，这些问题会更加复杂和微妙，这是因为对于一个可数不交并集，有
 
−
 
 
−
<math>\mathbb{P}\left(\cup_nA_n\right)=\sum_n\mathbb{P}(A_n)</math>
 
−
 
 
−
成立，但对于一个不可数并集<math>\cup_{t\geq 0}A_t</math>，上述结果并不成立。为了避免尽可能地避免那些复杂的情况，我们将会把后续讨论的内容限制在具有右连续性的随机过程<math>(X_t)_{t\geq 0}</math>上。在这里右连续定义为，对于任意<math>\omega \in \Omega</math>以及<math>t\geq 0</math>，存在<math>\epsilon</math>，使得当<math>t\leq s\leq t+\epsilon</math>时，总有<math>X_s(\omega)=X_t(\omega)</math>成立。由测度论中的标准结果可知，具有右连续性的随机过程中的任意一个事件的概率，可以由它的有限维分布确定，也就是可以由概率<math>\mathbb{P}(X_{t_0}=i_0,X_{t_1}=i_1,\dots,X_{t_n}=i_n),n\geq 0,0\leq t_0\leq t_1\leq\dots\leq t_n、i_0,\dots,i_n\in I</math>。例如：
 
−
 
 
−
<math>\mathbb{P}(X_t=i,t\in B\subseteq [0,\infty))=1-\lim_{n\to \infty}\sum_{j_1,\dots,j_n\neq i}\mathbb{P}(X_{q_1}=j_i,\dots,X_{q_n}=j_n)</math>
 
−
 
 
−
其中<math>q_1,q_2,\dots</math>是有理数的枚举。
 
−
 
 
−
具有右连续性的随机过程中的每一条路径<math>t\mapsto X_t(\omega)</math>在每个新状态中必须保持一段时间不变，因此一共有三种可能的路径类型。第一种类型中有无限次跳跃，但是在任意一个给定的区间<math>[0,t]</math>中只有有限次。第二种类型中只有有限次跳跃，最终会永远“卡”在某一个状态中。第三种类型在一个有限的区间中发生无限次跳跃。第三种类型中，经过爆炸时间<math>\zeta</math>,整个随机过程会重新从头开始，之后可能会再次爆炸（即在有限的区间中发生无限次跳跃），可能会可能会有无限次跳跃，也可能只有有限次跳跃。
 
−
 
 
−
我们称<math>0=J_0,J_1,\dots</math>为<math>（X_t）_{t\geq 0}</math>的跳跃时间，其中<math>J_0=0,J_{n+1}=\inf\{t\geq J_n:X_t\neq X_{J_n}\}</math>，指状态发生改变的时间点。每<math>S_1,S_2,\dots</math>称为<math>（X_t）_{t\geq 0}</math>的停留时间，其中
 
−
 
 
−
<math>S_n=\begin{cases}
 
−
J_n-J_{n-1} & ,J_n<\infty \\
 
−
\infty & ,J_n=\infty
 
−
\end{cases}
 
−
</math>
 
−
 
 
−
指每两个跳跃时间之间的状态持续时间。
 
−
 
 
−
注意，右连续性保证了<math>S_n>0</math>。当<math>J_{n+1}=\infty</math>时，则我们定义<math>X_{\infty}=X_{J_n}</math>，否则最终状态<math>X_{\infty}</math>没有定义。（第一个）爆炸时间<math>\zeta</math>由下式定义：
 
−
 
 
−
<math>\zeta=\sup_nJ_n=\sum_{n=1}^{\infty}S_n</math>
 
−
 
 
−
从一个连续时间随机过程中，我们可以取一系列离散时间点得到一个离散时间随机过程，我们称由<math>Y_n=X_{J_n}</math>决定的离散时间随机过程<math>(Y_n)_{n\geq 0}</math>为<math>（X_t）_{t\geq 0}</math>的跳跃过程，特别地，当<math>(Y_n)_{n\geq 0}</math>为离散马尔科夫链时，也称它为跳跃链。这仅仅是在<math>（X_t）_{t\geq 0}</math>爆炸之前的取值序列，并没有给出爆炸发生之后的信息。
 
−
 
 
−
由于我们不需要考虑在一个随机过程发生爆炸之后的行为，所以可以在<math>I</math>中添加一个新状态<math>\infty</math>来统一描述它。我们规定，<math>X_t=\infty</math>当<math>t\geq\zeta</math>时。我们称满足这种规定的随机过程为极小过程，极小过程指的并不是状态取值极小，而是当过程活跃的时间区间。注意一个极小过程可以由停留时间和跳跃过程中所蕴含的信息重建，因此通过指定<math>S_1,S_2,\dots</math>和<math>(Y_n)_{n\geq 0}</math>的联合分布，我们可以对<math>（X_t）_{t\geq 0}</math>的概率行为进行另一种“可数的”描述。例如，<math>X_t=i</math>的概率可以由下面的式子描述：
 
−
 
 
−
<math>\mathbb{P}(X_t=i)=\sum^{\infty}_{n=0}\mathbb{P}(Y_n=i,J_n\leq t<J_{n+1})</math>
 
−
 
 
−
<math>\mathbb{P}(X_t=i,t\in B\subseteq[0,\infty))=\mathbb{P}(Y_n=i,n\in B\subseteq\mathbb{N})</math>
 
−
 
 
−
==== 指数分布的性质 ====
 
−
 
 
−
==== 泊松过程 ====
 
−
 
 
−
==== 生灭过程 ====
 
−
 
 
−
==== 向前方程与向后方程 ====
 
  
 
==参考文献==
 
==参考文献==
  
 
<references />
 
<references />

2025年3月27日 (四) 22:47的版本

首先，介绍一个经典的骰子游戏——Yahtzee。在游戏中共有5个六面均匀的骰子，游戏参与者至多有三次投掷机会。为了简化，此处假设目标是使得所有骰子的结果相同（称为获得Yahtzee）。具体规则是在第一次和第二次投掷后，可以仅重新投掷部分数量骰子，而保持其他骰子不动。例如，第一次投掷结果为11234，由于有两个1，可以保持对应的两个骰子不动，重新投掷234对应的三个骰子。[1]


实际上，是否获得Yahtzee是看投掷结果中相同的骰子个数是否等于5。每次投掷中结果相同的骰子个数都是一个随机变量，其可能的取值均为0，1，2，3，4，5。只不过，后面一次投掷结果相同的骰子个数小于前面投掷结果相同的骰子个数发生的概率为0。在整个过程中，投掷结果相同的骰子个数在0-5六个数字间进行转移，所以称集合[math]\displaystyle{ \{0,1,2,3,4,5\} }[/math]为状态空间。此外，当投掷两次骰子后，分析第三次投掷结果中相同的骰子个数的发生概率，可以发现这个概率与第一次投掷结果中相同的骰子个数的发生概率无关。即在给定当前状态下，对于未来状态的预测不再依赖于过去状态。这个特性被称为马尔科夫特性，这一类特殊的随机过程被称为马尔科夫过程。


马尔科夫链是一种应用十分广泛的马尔科夫过程，能够用于描述天气变化和基因调控等现象。本词条主要参考北京大学李东风老师的应用随机过程讲义[2]对相关基础概念进行梳理，为后续相关应用做铺垫。


离散（或连续）时间马尔科夫链的定义

上述Yahtzee例子中，时间和状态空间均是离散的且满足马尔科夫性质，称这类随机过程为离散时间马尔科夫链（简称马尔科夫链，Markov chain），严格的数学定义如下：

称状态空间[math]\displaystyle{ S=\{1,2,\ldots\} }[/math]上的随机过程[math]\displaystyle{ \{X_n,\ n=0,1,2,\ldots\} }[/math]是马尔科夫链[3]或具有马尔科夫性质，若满足

[math]\displaystyle{ \forall n,\ \ P(X_n=j|X_{n-1}=i,X_{n-2}=x_{n-2},\ldots,X_0=x_0)=P(X_n=j|X_{n-1}=i), }[/math]

其中，[math]\displaystyle{ X_n=j\in S }[/math]表示过程在时刻[math]\displaystyle{ n }[/math]处于状态[math]\displaystyle{ j }[/math]，称[math]\displaystyle{ P(X_n=j|X_{n-1}=i) }[/math]为马尔科夫链的一步转移概率，并引入记号[math]\displaystyle{ P_{ij}(m,n)=P(X_n=j|X_m=i) }[/math]。


此外，当时间是连续的但状态空间仍是离散的且满足马尔科夫性质，称这类随机过程为连续时间马尔科夫链，具体定义为

称状态空间[math]\displaystyle{ S=\{1,2,\ldots\} }[/math]上的随机过程[math]\displaystyle{ \{X_t,\ t\geq 0\} }[/math]是连续时间马尔科夫链[4] ，若满足 [math]\displaystyle{ \forall n,\ 0=t_0\lt t_1\lt \ldots\lt t_{n-1}\lt t_{n},\ \ P(X_{t_n}=j|X_{t_{n-1}}=i,X_{t_{n-2}}=x_{t_{n-2}},\ldots,X_{t_{0}}=x_{t_{0}})=P(X_{t_n}=j|X_{t_{n-1}}=i) }[/math]。


日常生活中的许多现象都可以利用马尔科夫链来描述，例如天气的变化。简单考虑两种天气状态，下雨和不下雨。那么，对应的马尔科夫假设就是明天是否下雨只取决于今天的天气，而与之前的天气无关。

离散时间马尔科夫链

基本性质

多步转移概率

上述定义中强调了一步转移概率对于历史的遗忘性，那么对于多步转移概率是否也满足？答案是肯定的。


考虑离散时间马尔科夫链，对任意的[math]\displaystyle{ n\geq0 }[/math]和[math]\displaystyle{ m\geq1 }[/math]，有

[math]\displaystyle{ \begin{aligned} P(X_{n+m}=j|X_n=i,X_{n-1}=x_{n-1},\ldots,X_0=x_0)=P(X_{n+m}=j|X_n=i), \end{aligned} }[/math]

即当[math]\displaystyle{ X_n }[/math]给定后，[math]\displaystyle{ X_{n+m} }[/math]和[math]\displaystyle{ X_{n-1},\ldots,X_0 }[/math]条件独立。

注：可以对[math]\displaystyle{ m }[/math]进行数学归纳得证上述性质。


Chapman-Kolmogorov方程

由于上述性质，即给定现在，过去与未来独立，对于多步转移概率也是成立的。那么，任意步转移概率的计算就可以根据这个性质进行分解计算。


具体来说，对于[math]\displaystyle{ n\geq2 }[/math]步转移概率[math]\displaystyle{ P(X_n=j|X_0=i) }[/math]，可以先给定某一中间时刻[math]\displaystyle{ 0\lt m\lt n }[/math]的状态[math]\displaystyle{ k }[/math]，此时由条件独立性，从[math]\displaystyle{ i }[/math]先经[math]\displaystyle{ m }[/math]步至[math]\displaystyle{ k }[/math]，再经[math]\displaystyle{ n-m }[/math]步至[math]\displaystyle{ j }[/math]的概率就可以被分解为两个转移概率的乘积。接下来，只需要遍历状态[math]\displaystyle{ k }[/math]的所有可能，即

[math]\displaystyle{ \begin{aligned} P(X_n=j|X_0=i)&=\sum_{k\in S}P(X_n=j,X_m=k|X_0=i)\\ &=\sum_{k\in S}P(X_n=j|X_m=k,X_0=i)P(X_m=k|X_0=i)\\ &=\sum_{k\in S}P(X_n=j|X_m=k)P(X_m=k|X_0=i),\\ \end{aligned} }[/math]

其中，[math]\displaystyle{ P(X_n=j|X_0=i)=\sum_{k\in S}P(X_n=j|X_m=k)P(X_m=k|X_0=i) }[/math]称为Chapman-Kolmogorov方程。


时齐性与非时齐性

由上述Chapman-Kolmogorov方程可知，多步转移概率其实是一步转移概率的乘积（和）。那么，自然地会想到，在计算乘积的过程中，一步转移概率是否会随时间变化？


回顾天气变化的例子，记下雨和不下雨分别为状态2和状态1，即样本空间为[math]\displaystyle{ S=\{1,2\} }[/math]。令今天为时刻[math]\displaystyle{ n=0 }[/math]，为了方面描述，记[math]\displaystyle{ X_n }[/math]为时刻[math]\displaystyle{ n }[/math]的天气状态，今天不下雨的条件下明天不下雨的概率为[math]\displaystyle{ P(X_1=1|X_0=1)=p }[/math]，今天下雨的条件下明天下雨的概率为[math]\displaystyle{ P(X_1=2|X_0=2)=q }[/math]。随着时间的推移，明天不下雨的条件下后天不下雨的概率[math]\displaystyle{ P(X_2=1|X_1=1) }[/math]可能不一定等于[math]\displaystyle{ p }[/math]，即一步转移概率可能不仅与状态有关，可能还与时间有关。


在一个经典概率模型——波利亚坛子模型（Polya's urn scheme)中，一步转移概率就与时间有关。模型假设坛子中装有[math]\displaystyle{ b\gt 0 }[/math]个黑球和[math]\displaystyle{ w\gt 0 }[/math]个白球。每次随机地从坛子中有放回地抽出一个球，并且再放入一个同颜色的球。记[math]\displaystyle{ X_n }[/math]为第[math]\displaystyle{ n }[/math]次抽取后坛子中黑球的个数，则一步转移概率

[math]\displaystyle{ P(X_n=m+1|X_{n-1}=m)=\frac{m}{b+w+n-1},\ \ P(X_n=m|X_{n-1}=m)=\frac{b+w+n-1-m}{b+w+n-1}. }[/math]

显然，上述概率是随着[math]\displaystyle{ n }[/math]的变化而变化的。


一般的，当一步转移概率[math]\displaystyle{ P(X_n=j|X_{n-1}=i) }[/math]只与状态[math]\displaystyle{ i,j }[/math]有关，而与时刻[math]\displaystyle{ n }[/math]无关（平稳性假设），称此马尔科夫链为时齐马尔科夫链（homogeneous）；若[math]\displaystyle{ P(X_n=j|X_{n-1}=i) }[/math]与状态[math]\displaystyle{ i,j }[/math]和时刻[math]\displaystyle{ n }[/math]均有关，则称此马尔科夫链为非时齐的。


下面主要讨论离散时间时齐马尔科夫链。

转移过程

时齐性与平稳性

由时齐性假设，记一步转移概率 [math]\displaystyle{ P(X_n=j|X_{n-1}=i)=p_{ij} }[/math]。


此时，对应的Chapman-kolmogorov方程为

[math]\displaystyle{ \begin{aligned} P_{ij}(0,n)&=\sum_{k_1\in S}P(X_n=j|X_1=k_1)P(X_1=k_1|X_0=i)\\ &=\sum_{k_1\in S}P(X_n=j|X_1=k_1)p_{ik_1}\\ &=\ldots\\ &=\sum_{k_1\in S}\ldots\sum_{k_{n-1}\in S}p_{ik_1}p_{k_1k_2}\ldots p_{k_{n-1}j}. \end{aligned} }[/math]


不难看出，上述方程与起始时刻无关，仅与时间间隔有关，即如果将时间窗任意平移[math]\displaystyle{ l }[/math]个时刻，有

[math]\displaystyle{ P_{ij}(l,n+l)=\sum_{k_1\in S}\ldots\sum_{k_{n-1}\in S}p_{ik_1}p_{k_1k_2}\ldots p_{k_{n-1}j}=P_{ij}(0,n) }[/math]。

所以，一般的，记[math]\displaystyle{ n-m }[/math]步转移概率 [math]\displaystyle{ P_{ij}(m,n)=P_{ij}(n-m) }[/math]。


注：此处的“平稳性”指的并不是一般的随机过程中的平稳性。这里的“平稳性”与宽平稳中的二阶条件（即协方差函数仅与时间差有关）类似，但一阶条件无法保证（即均值函数不依赖于时间）。


转移概率矩阵

观察上述方程容易发现，求和项是对处在中间的下角标进行遍历，这恰恰对应着矩阵乘法。 将上述例子中一步转移概率[math]\displaystyle{ p_{ij}(i,j\in S) }[/math]排列为一个矩阵

[math]\displaystyle{ P=(p_{ij})_{i,j\in S}=\begin{bmatrix} p_{11}& p_{12}&\ldots\\ p_{21}& p_{22}&\ldots\\ \vdots&\vdots&\ddots \end{bmatrix}, }[/math]

那么，Chapman-Kolmogorov方程变形为，

[math]\displaystyle{ P(n)=P\times P(n-1)=\ldots=P^n, }[/math]

其中，[math]\displaystyle{ P(n) }[/math]称为[math]\displaystyle{ n }[/math]步转移概率矩阵，[math]\displaystyle{ P }[/math]称为一步转移概率矩阵（transition probability matrix, TPM），下面简称为转移概率矩阵。


通过观察可知，矩阵[math]\displaystyle{ P }[/math]满足如下性质

[math]\displaystyle{ \begin{aligned} p_{ij}&\geq0,\ \forall\ i,j\in S,\\ \sum_{j\in S}p_{ij}&=1,\ \forall\ i\in S。 \end{aligned} }[/math]

一般的，称满足上述性质的矩阵为随机矩阵（stochastic matrix）。


可达、互通与可约性

下面举一个简单的例子具体观察状态间的转移行为，下图中(a)和(b)分别为马尔科夫链的转移概率矩阵和图表示。

可约.png

由Chapman-Kolmogorov方程，可得100步转移概率矩阵和200步转移概率矩阵为

[math]\displaystyle{ \begin{aligned} P(100)=\left(\begin{matrix}0&0.9&0.1\\0.8&0.2&0\\ 0&0&1 \end{matrix}\right)^n=\left(\begin{matrix}0.0041&0.0050&0.9909\\0.0044&0.0052&0.9904\\ 0&0&1 \end{matrix}\right),\ \ \ \ P(200)=\left(\begin{matrix}0&0.9&0.1\\0.8&0.2&0\\ 0&0&1 \end{matrix}\right)^n=\left(\begin{matrix}0&0&1\\0&0&1\\ 0&0&1 \end{matrix}\right)。\\ \end{aligned} }[/math]

通过观察马尔科夫链的图表示可以发现，状态1和状态2之间存在互相到达的路径，但状态3与状态1和状态2之间均不能互相到达。此外，容易看出，随着转移步数的增加，对应的转移概率矩阵的第一列和第二列均趋近0，即状态1和状态2的转移行为逐渐一致，但与状态3的转移行为存在明显差异。那么，可以利用这种互相可达的特性来将相同转移行为的状态划分为一类，状态1和状态2是互通的，可被归为一类，而状态3只可达自身，所以状态3为另一个类，即此马尔科夫链是可约的。下面给出可达和互通的严格定义。


首先，需要明确可达的定义。图中的路径的权重是大于0的概率值，所以定义如下：

[math]\displaystyle{ \exists n\geq 0,\ \ P_{ij}(n)\gt 0 }[/math]，则称状态[math]\displaystyle{ i }[/math]可达状态[math]\displaystyle{ j }[/math]，记为[math]\displaystyle{ i\to j }[/math]。易知，可达是传递关系，即 [math]\displaystyle{ i\to j,\ j\to k\Longrightarrow i\to k }[/math]。


进一步，若[math]\displaystyle{ i\to j }[/math]且[math]\displaystyle{ j\to i }[/math]，则称状态[math]\displaystyle{ i }[/math]和[math]\displaystyle{ j }[/math]互通，记为[math]\displaystyle{ i\leftrightarrow j }[/math]。易知，互通是一种等价关系。那么，可以将互通的状态归为一类，且任一状态仅属于一个类。特别的，若马尔科夫链中只存在一个类，则称它是不可约的（irreducible）；否则，称为是可约的（reducible）。


周期性

不禁会提出一个疑问，是否所有的转移矩阵都具有极限？下面考察一个简单的两状态马尔科夫链， [math]\displaystyle{ P=\begin{bmatrix}0&1\\1&0\end{bmatrix} }[/math]。

计算[math]\displaystyle{ n }[/math]步转移概率矩阵，得

[math]\displaystyle{ P(n)=\begin{cases} \begin{bmatrix}0&1\\1&0\end{bmatrix},&n=2k,\ k\in\mathcal{Z},\\ \begin{bmatrix}1&0\\0&1\end{bmatrix},& n=2k+1,\ k\in\mathcal{Z}。 \end{cases} }[/math]

根据[math]\displaystyle{ n }[/math]步转移概率矩阵可知，[math]\displaystyle{ P_{ii}(n) }[/math]序列为[math]\displaystyle{ 0,1,0,1,\ldots }[/math]，[math]\displaystyle{ P_{ij}(n) }[/math]序列为[math]\displaystyle{ 1,0,1,0\ldots }[/math]，四个转移概率均不存在极限，即转移矩阵没有极限。


不难发现这个马尔科夫链的状态转移存在着周期性——初始状态不论是状态1还是状态2，每转移2步，都能够以正概率返回自身状态，即周期为2。进一步，如果有任一状态能够以一定周期、正概率返回自身，转移矩阵则不存在极限，即状态的周期性成为了一个转移矩阵收敛的判断条件。下面介绍状态的周期性的严格定义：

记使得转移概率[math]\displaystyle{ P_{ii}(n)\gt 0 }[/math]的转移步数[math]\displaystyle{ n }[/math]所组成的集合为[math]\displaystyle{ A_i=\{n:n\geq1,P_{ii}(n)\gt 0\} }[/math]。若[math]\displaystyle{ A_i }[/math]非空，则称其最大公约数为状态[math]\displaystyle{ i }[/math]的周期，记为[math]\displaystyle{ d_i }[/math]。若[math]\displaystyle{ d_i\gt 1 }[/math]，称[math]\displaystyle{ i }[/math]是周期的；若[math]\displaystyle{ d_i=1 }[/math]，称[math]\displaystyle{ i }[/math]是非周期的。


回顾上节中三状态马尔科夫链，由于[math]\displaystyle{ P_{33}=1\gt P_{22}=0.2\gt 0 }[/math]，那么[math]\displaystyle{ A_{2}=A_{3}=\{1,2,\ldots\} }[/math]，所以它们都是非周期的。对于状态1，其与状态2互通且状态2一步可达自身，那么[math]\displaystyle{ A_{1}=\{2,3,\ldots\} }[/math]，所以状态1也是非周期的。可以看出，互通的状态1和状态2的周期性是相同的。实际上，可以通过严格证明得出，互通状态的周期是相同的，即周期性也是一个类性质。那么，互通的状态只需要判断其中任一状态的周期性即可，这大大减少了判断的次数。


上述分类方法是基于局部性质进行两两判断分类。此外，还可以从整体转移机制的角度对状态进行划分，详细介绍参见成块性（Lumpability）。

演化性质

演化过程

上节中关于转移过程的内容，实际上是固定了初始时刻的状态。一般的，初始时刻的状态也存在着一定的随机性，即可以使用一个分布列来刻画。


记[math]\displaystyle{ X_n(n\geq0) }[/math]的分布列 [math]\displaystyle{ \pi_n=(\pi_n(1),\pi_n(2),\ldots) }[/math]， 其中，[math]\displaystyle{ \pi_n(i)=P(X_n=i),\ i\in S }[/math]。


根据全概率公式，[math]\displaystyle{ X_{n+1} }[/math]的分布列

[math]\displaystyle{ \pi_{n+1}=\pi_{n}P }[/math]。

进一步，递推可得，

[math]\displaystyle{ \forall\ n\geq0,\ \ \pi_n=\pi_0P^n }[/math]。

注：[math]\displaystyle{ \pi }[/math]是一个行向量，上述方程为左手方程（left hand equation）。


上节中的马尔科夫链如果在0时刻三个状态等概率地出现，那么在1时刻和2时刻的状态分布分别为

[math]\displaystyle{ \pi_1=(1/3,1/3,1/3)\left(\begin{matrix}0&0.9&0.1\\0.8&0.2&0\\ 0&0&1 \end{matrix}\right)=(0.2667,0.3667,0.3667),\ \ \ \ \ }[/math] [math]\displaystyle{ \pi_2=(1/3,1/3,1/3)\left(\begin{matrix}0&0.9&0.1\\0.8&0.2&0\\ 0&0&1 \end{matrix}\right)^2=(0.2933,0.3133,0.3933) }[/math]。


若将左手方程的左右两边同时进行转置，得

[math]\displaystyle{ \pi_{n}^{\rm T}=(P^{\rm T})^n\pi_{0}^{\rm T} }[/math]。


这是一个一阶线性齐次常微分方程。由递推关系，自然地会联想到，马尔科夫链的长期行为本质上是一个特征值问题。


转移概率矩阵的特征值

下面考察[math]\displaystyle{ P }[/math]的特征值，由于[math]\displaystyle{ P }[/math]的行和为[math]\displaystyle{ 1 }[/math]，那么

[math]\displaystyle{ P\mathbf{1}=\begin{bmatrix} p_{11}& p_{12}&\ldots\\ p_{21}& p_{22}&\ldots\\ \vdots& \vdots&\ddots\\ \end{bmatrix}\begin{bmatrix} 1 \\ 1\\ \vdots\\ \end{bmatrix}=\begin{bmatrix} \sum_{j\in S}{p_{1j}}\\ \sum_{j\in S}{p_{2j}}\\ \vdots\\ \end{bmatrix}=\begin{bmatrix} 1 \\ 1\\ \vdots\\ \end{bmatrix}=\mathbf{1}. }[/math]

即[math]\displaystyle{ 1 }[/math]是[math]\displaystyle{ P }[/math]的特征值，且对应的特征向量为[math]\displaystyle{ \mathbf{1} }[/math]。 另一方面，

[math]\displaystyle{ det(P-\lambda I)=det((P-\lambda I)^{\rm T})=det(P^{\rm T}-\lambda I) }[/math]。

所以，[math]\displaystyle{ 1 }[/math]也是[math]\displaystyle{ P^{\rm T} }[/math]的特征值。

注：即方程[math]\displaystyle{ \pi=\pi P }[/math]总有非零解，这与马尔科夫链是否有极限没有关系。


若[math]\displaystyle{ \pi_0 }[/math]是方程[math]\displaystyle{ \pi=\pi P }[/math]的解，那么由递推关系得

[math]\displaystyle{ \pi_n=\pi_0P^n=\pi_0 }[/math]。

即若[math]\displaystyle{ P(X_0=i)=\pi_0(i) }[/math]，有

[math]\displaystyle{ \forall\ n,\ P(X_n=i)=\pi_0(i) }[/math]，

称[math]\displaystyle{ \pi_0 }[/math]为平稳分布。


进一步，设[math]\displaystyle{ \lambda }[/math]为[math]\displaystyle{ P }[/math]的任一特征值，对应的特征向量为[math]\displaystyle{ x=(x_1,x_2,\ldots)^{\rm T} }[/math]。那么，[math]\displaystyle{ \lambda }[/math]也是[math]\displaystyle{ P^{\rm T} }[/math]的特征值，且[math]\displaystyle{ \lambda x^{\rm T}=x^{\rm T}P^{\rm T} }[/math]，展开得

[math]\displaystyle{ \lambda x_j=\sum_{i}p_{ji}x_i }[/math]。

不失一般性，假设[math]\displaystyle{ |x_j|=\max_{k}|x_i| }[/math]，有

[math]\displaystyle{ |\lambda|\cdot|x_j|=\Big|\sum_i p_{ji}x_i\Big|\leq\sum_{i}p_{ji}|x_i|\leq\sum_{i}p_{ji}|x_j|=|x_j| }[/math]。

那么，[math]\displaystyle{ |\lambda|\leq 1 }[/math]。

注：上述两条性质对于一般的随机矩阵均成立。


细致平衡条件

前面的讨论都沿着时间正向在讨论，下面考虑时间反向的过程。

[math]\displaystyle{ P(X_n=j|X_{n+1}=i,X_{n+2},\ldots)= \frac{P(X_n=j|X_{n+1}=i)P(X_{n+2},\ldots|X_{n+1}=i,X_n=j)}{P(X_{n+2},\ldots|X_{n+1}=i)} =P(X_n=j|X_{n+1}=i) =\frac{P(X_n=j)P(X_{n+1}=i|X_n=j)}{P(X_{n+1}=i)} }[/math]，

即反向过程仍满足马尔科夫性质。这其实是马尔科夫性质的等价定义——给定现在的条件下，过去与未来条件独立。并且，一般来讲，上述一步转移概率是与时间[math]\displaystyle{ n }[/math]有关的，即反向过程是非齐次的。


下面考察有限状态空间上不可约、非周期的马尔科夫链，其唯一的平稳分布为[math]\displaystyle{ \pi }[/math]。从平稳分布出发，有

[math]\displaystyle{ P(X_n=j|X_{n+1}=i,X_{n+2},\ldots) =\frac{P(X_n=j)P(X_{n+1}=i|X_n=j)}{P(X_{n+1}=i)}=\frac{\pi_jp_{ji}}{\pi_i}\triangleq q_{ij} }[/math]。

此时，反向过程是齐次的。


进一步，考虑一种特殊情形，若[math]\displaystyle{ q_{ij}=p_{ij} }[/math]，即对于任意的状态[math]\displaystyle{ i,j }[/math]，满足[math]\displaystyle{ \pi_i p_{ij}=\pi_jp_{ji} }[/math]。此时，称马尔科夫链满足细致平衡条件，也称该马尔科夫链是时间可逆的'。

注：[math]\displaystyle{ \pi_i p_{ij} }[/math]可以理解为状态[math]\displaystyle{ i }[/math]向状态[math]\displaystyle{ j }[/math]的输送，同理，[math]\displaystyle{ \pi_jp_{ji} }[/math]可以理解为状态[math]\displaystyle{ j }[/math]向状态[math]\displaystyle{ i }[/math]的输送。细致平衡条件可以理解为任意的状态[math]\displaystyle{ i }[/math]与状态[math]\displaystyle{ j }[/math]之间的相互输送是相同的。


进一步，若满足细致平衡条件，则

[math]\displaystyle{ \pi_i=\sum_k\pi_kP_{ki}\iff \pi=\pi P }[/math]。

证：[math]\displaystyle{ \pi_i=\pi_i\sum_kP_{ik}=\sum_k\pi_iP_{ik}=\sum_k\pi_kP_{ki} }[/math]。


时间可逆性与动力学可逆性

时间可逆性描述的是在达到平稳后，时间反转前后的转移机制的一致性，即当前状态给定后，不论时间方向是朝向未来还是过去，它以同一个转移分布进行转移。与时间可逆性不同，动力学可逆性是指转移概率矩阵可逆且其逆矩阵仍是一个转移概率矩阵，它描述的则是转移机制的一一对应性。进一步，近似动力学可逆性可以作为一种因果度量，详细内容参见词条基于可逆性的因果涌现理论。

离散时间马尔科夫链的粗粒化和度量

离散时间马尔科夫链的粗粒化

一般的，在状态分类的基础上，对分类后状态空间（宏观尺度上）重新定义马尔可夫转移矩阵的过程被称为马尔科夫概率转移矩阵的粗粒化（coarse-graining），详细介绍参见词条马尔科夫链的粗粒化。下面，简要介绍两种粗粒化方法——成块性和基于SVD分解的粗粒化方法。

马尔科夫链的成块性

可约是基于局部连通性进行两两判断从而对状态空间进行分类，但有时这个划分粒度仍很粗糙，即连通的状态间存在其他性质或结构可以继续划分。


例如，考虑如下马尔科夫链，

[math]\displaystyle{ P=\begin{bmatrix} 0.3&0.3&0.3&0.1\\ 0.2&0.4&0.2&0.2\\ 0&0.2&0.3&0.5\\ 0.2&0&0.2&0.6 \end{bmatrix}, }[/math]

易知，这个马尔科夫链是不可约的。此外，无论从状态1还是2出发，下一时刻转移至状态1或状态2的概率均为0.6，转移至其他两个状态3和4的概率均为0.4。另一方面，状态3和状态4也是如此。那么，基于这样的转移机制，可以将状态1和2划分为1组，状态3和状态4划分为一组，形成两个宏观状态，得到一个新的两状态的马尔科夫转移矩阵

[math]\displaystyle{ P=\begin{bmatrix} 0.6&0.4\\ 0.2&0.8\\ \end{bmatrix}, }[/math]

即同属于一个宏观状态的原始微观状态转移至宏观状态的机制是相同的，这种性质被称为成块性（Lumpability）。定义[math]\displaystyle{ A = \{A_i \} }[/math]为宏观态，成块性的数学表达式为：

[math]\displaystyle{ \forall A_i, A_j, \forall m, n \in A_i, \sum_{k \in A_j} p_{mk} = \sum_{k \in A_j} p_{nk} }[/math]

详细介绍参见词条马尔科夫链的成块性。


马尔科夫链的SVD粗粒化

从转移矩阵谱的角度出发，张江团队提出了基于奇异值分解（SVD）的粗粒化方法[5]。


第一步，对状态空间进行划分。首先，考虑[math]\displaystyle{ N }[/math]阶转移矩阵[math]\displaystyle{ P }[/math]的截断奇异值分解 [math]\displaystyle{ U\Sigma_{r\times r} V^{\rm T} }[/math]， 其中，[math]\displaystyle{ r }[/math]为粗粒化后的状态个数。之后，利用矩阵[math]\displaystyle{ V }[/math]对转移矩阵[math]\displaystyle{ P }[/math]做投影操作，得 [math]\displaystyle{ \tilde{P}=PV }[/math]。接下来，利用Kmeans等聚类算法将[math]\displaystyle{ \tilde{P} }[/math]的行向量聚为[math]\displaystyle{ r }[/math]类，得到指示矩阵[math]\displaystyle{ \Phi }[/math]，其元素表示如下

[math]\displaystyle{ \Phi_{ij}=\begin{cases} 1,&j=a(i),\\ 0,&j\neq a(i), \end{cases} }[/math]

其中，[math]\displaystyle{ a(i)\in\{1,2,\ldots,r\} }[/math]为[math]\displaystyle{ \tilde{P} }[/math]的第[math]\displaystyle{ i }[/math]行行向量所属类别。


第二步，定义新的转移概率矩阵。假设有限维转移矩阵[math]\displaystyle{ P }[/math]对应的马尔科夫链是不可约且非周期的，则存在唯一平稳分布[math]\displaystyle{ \pi }[/math]。考虑达到平稳后的两步联合概率

[math]\displaystyle{ P(X_n=j,X_{n-1}=i)=P(X_{n-1}=i)P(X_n=j|X_{n-1}=i)=\mu_ip_{ij},\ \ i,j=1,2,\ldots,N }[/math]，

称其组成的矩阵[math]\displaystyle{ F }[/math]为平稳流矩阵。接下来，基于平稳流矩阵和指示矩阵，定义简化平稳流矩阵

[math]\displaystyle{ F'=\Phi^{\rm T}F\Phi }[/math]。

为了满足行和为1的约束，对矩阵[math]\displaystyle{ F' }[/math]进行行归一化，得到粗粒化后转移矩阵[math]\displaystyle{ P' }[/math]，其元素为

[math]\displaystyle{ P'_{ij}=\frac{F'_{ij}}{\sum_kF'_{ik}} }[/math]。

详细介绍参见词条基于可逆性的因果涌现理论。


离散时间马尔科夫链的度量

转移概率矩阵的有效性息

马尔科夫链可以视为是通信领域中一种特殊的信道——离散无记忆信道。信道的输入和输出分别记为[math]\displaystyle{ X }[/math]和[math]\displaystyle{ Y }[/math]，当前输入[math]\displaystyle{ X }[/math]给定的条件下，对应的输出[math]\displaystyle{ Y }[/math]与之前的输入和输出独立。


为了描述信道能够传输的最大信息量，信息论领域提出了信道容量的概念，具体定义为

[math]\displaystyle{ C=\max_{\pi_X}I(X;Y)=\max_{\pi_X} H(Y)-H(Y|X) }[/math]。


基于上述信道容量的概念，Erik Hoel[6]提出了离散马尔科夫动力学的有效信息度量

[math]\displaystyle{ C=\max_{U_X}I(X;Y)=\max_{U_X} H(Y)-H(Y|X), }[/math]

其中，[math]\displaystyle{ U_X }[/math]为均匀分布。


通过粗粒化操作，可以得到宏观尺度下的转移矩阵[math]\displaystyle{ P_M }[/math]，并计算有效信息[math]\displaystyle{ {\rm EI}(P_M) }[/math]。进一步，可以通过宏观与微观尺度下的动力学有效信息差值来度量马尔科夫动力学的因果效应，并称这个差值

[math]\displaystyle{ {\rm CE}={\rm EI}(P_M)−{\rm EI}(P_m), }[/math]

为有效信息增益。如果存在某个宏观尺度，使得有效信息增益大于0，则认为该系统发生了因果涌现。详细内容参见词条有效信息。


转移概率矩阵的动力学可逆性

易知，当且仅当[math]\displaystyle{ P }[/math]为置换矩阵，有效信息的值最大。并且，置换矩阵的逆矩阵也是一个置换矩阵，同时也是一个转移概率矩阵，即[math]\displaystyle{ P }[/math]是可逆矩阵且[math]\displaystyle{ P^{−1} }[/math]也是一个转移概率矩阵，则称这类转移概率矩阵是严格动力学可逆的。但是，只有置换矩阵满足严格动力学可逆。所以，需要定义一个可以度量接近动力学可逆程度的指标。


通过观察可以发现置换矩阵具有两方面特性：一方面，它是满秩矩阵；另一方面，它每行或列均为独热向量，具有稀疏性。这两方面都可以通过转移概率矩阵[math]\displaystyle{ P }[/math]的奇异值进行度量。考虑一个[math]\displaystyle{ N }[/math]阶转移概率矩阵[math]\displaystyle{ P }[/math]，设其奇异值为[math]\displaystyle{ \sigma_1\geq\sigma_2\geq\ldots\ge\sigma_N\geq0 }[/math]，则[math]\displaystyle{ P }[/math]的秩有如下表示

[math]\displaystyle{ r=\sum_{i=1}^N\sigma_i^0, }[/math]

并且[math]\displaystyle{ P }[/math]的稀疏性可以通过矩阵的Frobenius范数度量，

[math]\displaystyle{ \|P\|_F^2=\sum_{i=1}^N\sigma_i^2 }[/math]。


基于上述特性，张江团队定义转移概率矩阵[math]\displaystyle{ P }[/math]的[math]\displaystyle{ \alpha\in(0,2) }[/math]阶

[math]\displaystyle{ \Gamma_\alpha=\sum_{i=1}^N\sigma_i^\alpha }[/math]

作为动力学可逆性的近似[5]。在应用中，常采用[math]\displaystyle{ \Gamma_{\alpha=1} }[/math]即转移概率矩阵的核范数来度量接近动力学可逆的程度。


基于[math]\displaystyle{ \Gamma_{\alpha} }[/math]，给出了清晰因果涌现和模糊因果涌现程度的计算方法。值得注意的是，它们均与粗粒化方法无关。详细内容参见词条基于可逆性的因果涌现理论。


连续时间马尔科夫链的基础

时齐性

与离散时间马尔科夫链相同，若连续马尔科夫链的转移概率[math]\displaystyle{ P(X(t+s)=j|X(s)=i) }[/math]与初始时刻[math]\displaystyle{ s }[/math]无关，那么称该马尔科夫链是时齐的。简记[math]\displaystyle{ P(X(t+s)=j|X(s)=i)=P_{ij}(t) }[/math]，相应地记转移概率矩阵为[math]\displaystyle{ P(t) }[/math]。特别的，[math]\displaystyle{ P(0)=I }[/math]。


C-K方程

与离散时间马尔科夫链相同，连续马尔科夫链也能得到C-K方程：

[math]\displaystyle{ P_{ij}(t+s)=\sum_{k\in S}P_{ik}(t)P_{kj}(s), }[/math]

对应的矩阵形式为

[math]\displaystyle{ P(t+s)=P(t)P(s) }[/math]。


Q矩阵

上式中乘积转化为求和，这会自然地联想到指数函数。由于指数函数具有特殊的求导性质，所以考察转移概率矩阵的变化率

[math]\displaystyle{ \begin{aligned} &\frac{1}{\Delta t}\left(P(t+\Delta t)-P(t)\right)\\ &=\frac{1}{\Delta t}\left(P(t)P(\Delta t)-P(t)\right)\\ &=P(t)\left(\frac{P(\Delta t)-I}{\Delta t}\right)。 \end{aligned} }[/math]

易知，当[math]\displaystyle{ \Delta t \to 0 }[/math]，有[math]\displaystyle{ P(\Delta t)\to I }[/math]。那么，假设 [math]\displaystyle{ \lim_{\Delta t\to 0}\frac{P(\Delta t)-I}{\Delta t} }[/math]存在并记为[math]\displaystyle{ Q }[/math]，则

[math]\displaystyle{ \frac{d}{dt}P(t)=P(t)Q }[/math]， 称为前向方程。

同理，由于

[math]\displaystyle{ P(t+\Delta t)=P(\Delta t)P(t), }[/math]

可得

[math]\displaystyle{ \frac{d}{dt}P(t)=QP(t) }[/math]， 称为后向方程。

进一步，由初值条件[math]\displaystyle{ P(0)=I }[/math]， 可得

[math]\displaystyle{ P(t)=\exp(Qt) }[/math]。


Q矩阵的基本性质

首先，分析[math]\displaystyle{ Q }[/math]矩阵的对角线元素

[math]\displaystyle{ Q_{ii}=\lim_{\Delta t \to 0}\frac{P_{ii}(\Delta t)-1}{\Delta t}\leq 0 }[/math]，

而非对角线元素

[math]\displaystyle{ Q_{ij}=\lim_{\Delta t \to 0}\frac{P_{ij}(\Delta t)}{\Delta t}\geq 0\ \ (i\neq j) }[/math]。


进一步，考察有限空间对应的[math]\displaystyle{ Q }[/math]矩阵的行和

[math]\displaystyle{ \sum_{j}Q_{ij}=\sum_{j}\lim_{\Delta t \to 0}\frac{P_{ij}(\Delta t)-\delta_{ij}}{\Delta t}= \lim_{\Delta t \to 0}\frac{1}{\Delta t}\sum_{j}\left(P_{ij}(\Delta t)-\delta_{ij}\right)=0 }[/math]，

即[math]\displaystyle{ Q }[/math]矩阵的行和等于0。

连续时间马尔科夫链

基本性质

有限状态空间

直观模型
模型参数

=====P(t)与Q的关系

无限状态空间

爆炸

=====P(t)与Q的关系


过程描述

转移过程

可约性
周期性

演化性质

平稳分布
细致平衡条件
时间可逆性

参考文献

  1. ↑ http://www.stat.yale.edu/~pollard/Courses/251.spring2013/Handouts/Chang-MarkovChains.pdf
  2. ↑ 李东风. 应用随机过程, 2024, 163-215. https://www.math.pku.edu.cn/teachers/lidf/course/stochproc/stochprocnotes/html/_book/StocProc.pdf
  3. ↑ Brémaud P．Markov chains: Gibbs fields, Monte Carlo simulation, and queues．Springer Science & Business Media, 1999, 53-156.
  4. ↑ Kendall D G, Batchelor G K, Bingham N H, Hayman W K, Hyland J M E, Lorentz G G, Moffatt H K, Parry W, Razborov A A, Robinson C A and Whittle P. Andrei Nikolaevich Kolmogorov (1903–1987). Bulletin of the London Mathematical Society, 1990, 22(1): 31-100.
  5. ↑ 5.0 5.1 Zhang J, Tao R Y, Leong H K, Yang M Z, Yuan B. Dynamical reversibility and a new theory of causal emergence based on SVD. npj Complexity, 2025, 2(3): 1-11.
  6. ↑ Hoel E P, Albantakis L, Tononi G. Quantifying causal emergence shows that macro can beat micro. Proceedings of the National Academy of Sciences, 2013, 110(49): 19790-19795.
取自“https://wiki.swarma.org/index.php?title=马尔科夫链&oldid=43037”