5,443
个编辑
更改
→连续时间马尔科夫链
则称<math>\{X(t)\}</math>是连续时间离散状态的马尔科夫链，简称为'''连续时间马尔科夫链'''，后面常用英文缩写'''CTMC'''（Continuous-Time Markov Chain）。其中的“链”指状态空间<math>S</math>是离散的。
则称<math>\{X(t)\}</math>是连续时间离散状态的马尔科夫链，简称为'''连续时间马尔科夫链'''，后面常用英文缩写'''CTMC'''（Continuous-Time Markov Chain）。其中的“链”指状态空间<math>S</math>是离散的。
===基本性质===
===基本概念===
====与离散时间马尔科夫链对应的基本概念====
与离散情形中一样，CTMC对与任意时间间隔都具有'''历史遗忘性'''。即对于<math>t>0</math>，已知<math>X(t)=i</math>的条件下，将来随机过程<math>\{X(u)|u>t\}</math>与过去随机过程<math>\{X(v)|0\leq v<t\}</math>独立。
和离散时间马尔科夫链相同，我们定义满足：
<math>\mathbb{P}(X(t+s)=j|X(s)=i)=\mathbb{P}(X(t)=j|X(0)=i),s,t\geq 0</math>
<math>\mathbb{P}(X(t+s)=j|X(s)=i)=\mathbb{P}(X(t)=j|X(0)=i),s,t\geq 0</math>
的CTMC具有'''时齐性'''。注意，如果没有特别说明，都默认马尔科夫链具有时齐性；只有当马尔科夫链不满足时齐性时，我们才会强调非时齐的。这是因为我们极少会遇到非时齐的马尔科夫链。
由时齐性，可知'''转移概率'''与起始时间<math>s</math>无关：
<math>p_{ij}(t)=\mathbb{P}(X(t+s)=j|X(s)=i)</math>
<math>p_{ij}(t)=\mathbb{P}(X(t+s)=j|X(s)=i)</math>
并且当对于任意一个CTMC<math>t=0</math>时，转移概率<math>p_{ij}(0)</math>是固定的，都是<math>\delta</math>函数：
<math>p_{ij}(0)=\delta_{ij}=\begin{cases}
<math>p_{ij}(0)=\delta_{ij}=\begin{cases}
</math>
</math>
有了任意两个状态间的转移概率，我们就能定义<math>\{X(t)\}</math>的'''转移概率矩阵'''来集中描述CTMC的状态是如何随着时间改变的：<math>P(t)=\left(p_{ij}(t)\right)_{i,j\in I}</math>
<math>P(t)=\left(p_{ij}(t)\right)_{i,j\in I}</math>
我们可以将一个时间间隔比较长的转移概率拆分为两个时间间隔比较短的转移概率，Chapman-Kolmogorov方程给出了两者的关系<math>p_{ij}(t+s)=\sum_{k\in I}p_{ik}(t)p_{kj}(s),\forall t,s\geq 0</math>。或者写成矩阵形式有<math>P(t+s)=P(t)P(s)=P(s)P(t)</math>
只需要给定初始状态和状态改变的规则，唯一决定了一个连续时间马尔可夫链。用更严格的语言来表述，<math>X(t)</math>的概率分布<math>\mathbf{p}(t)</math>由转移概率矩阵<math>P(t)</math>和<math>X(0)</math>的概率分布，即初始分布<math>\mathbf{p}(0)=(p_1(0),p_2(0),\dots)</math>唯一决定：
<math>X(t)</math>的概率分布<math>\mathbf{p}(t)</math>由转移概率矩阵<math>P(t)</math>和<math>X(0)</math>的概率分布<math>\mathbf{p}(0)=(p_1(0),p_2(0),\dots)</math>唯一决定：
<math>\mathbf{p}(t)=\mathbf{p}(0)P(t)</math>，
<math>\mathbf{p}(t)=\mathbf{p}(0)P(t)</math>，
其中<math>\mathbf{p}(t)=(p_1(t),p_2(t),\dots),t\geq 0,p_i(t)=\mathbb{P}(X(t)=i),i\in S </math>。
其中<math>\mathbf{p}(t)=(p_1(t),p_2(t),\dots),t\geq 0,p_i(t)=\mathbb{P}(X(t)=i),i\in S </math>。
====转移速率矩阵====
====连续时间马尔科夫链中独有的概念====
=====转移速率矩阵=====
在CTMC中，我们几乎都是用'''转移速率矩阵'''或者'''转移强度矩阵'''来描述状态转移的规则，记作<math>Q=(q_{ij})_{i,j\in S}</math>，而几乎不用转移概率矩阵。因为CTMC的转移概率矩阵中有一个时间参数t，对于不同的时间参数转移概率矩阵的大小不同，使用起来很麻烦；但在时齐性的前提下，转移速率矩阵是保持不变的，使用起来更加方便。转移速率矩阵具有下面三个重要的性质：
<math>(1)q_{ij}\geq 0,i\neq j</math>
<math>(1)q_{ij}\geq 0,i\neq j</math>
<math>(3)q_{ii}=-\sum_{i\neq j}q_{ij}</math>
<math>(3)q_{ii}=-\sum_{i\neq j}q_{ij}</math>
====Kolmogorov方程====
并且对于有限状态的CTMC，转移概率矩阵<math>P(t)</math>是转移速率矩阵<math>Q</math>的矩阵指数函数：
<math>P(t)=\sum^{\infty}_{k=0}\frac{1}{k!}(Qt)^k=e^{Qt},t\geq 0</math>
=====转移速率矩阵与转移概率矩阵关系=====
在这一节我们给出转移速率矩阵和转移概率矩阵之间关系推导思路，供感兴趣的读者参考，先给定转移概率矩阵<math>P(t)</math>，看看怎么能得到转移速率矩阵<math>Q</math>。对于离散时间马尔科夫链的一步转移概率矩阵<math>P</math>可以唯一决定<math>n</math>步转移概率矩阵：<math>P(n)=P^n</math>。但是对于CTMC，并不存在一个最小的正数<math>\delta</math>，使得对于任意正数<math>t</math>，存在正整数<math>n</math>，有<math>P(t)=P(\delta)^n</math>成立。对于任意<math>\epsilon>0</math>，可以证明<math>\{P(s)|0<s\leq\epsilon\}</math>可以决定所有的<math>P(t)</math>。这就提示我们，<math>P(t)</math>可能被<math>P'(0)=\lim_{s\to 0^+}(P(s)-P(0))/s</math>唯一决定。这个极限是否存在呢？
在任何有限之间内只有有限次转移的CTMC，称作'''规则的CTMC'''。为了简化讨论，以后无特殊声明时，讨论的都是规则的CTMC。CTMC的轨迹是阶梯函数，并且在跳跃点是右连续的，更重要的是，它的概率转移矩阵<math>P(t)</math>在<math>t=0</math>时，存在右导数：
<math>\lim_{t\to 0^+}=\frac{p_{ij}(t)-p_{ij}(0)}{t}=q_{ij}</math>
由于<math>p_{ij}(t)</math>是CTMC从<math>i</math>出发，经过<math>t</math>时间后处于<math>j</math>的概率，所以相应的，我们称<math>q_{ij}</math>是某一时刻从<math>i</math>出发，下一步向<math>j</math>转移的速率或强度，由此我们就得到了转移速率矩阵<math>Q=(q_{ij})_{i,j\in S}</math>。
<math>p'_{ij}(s)=\sum_{k\in S}q_{ik}p{kj}(s)</math>
接着讨论给定转移速率矩阵<math>Q</math>，如何确定转移概率矩阵<math>P(t)</math>？下面就通过Kolmogorov方程回答这个问题。
先回忆Chapman-Kolmogorov方程：
<math>p'_{ij}(t)=\sum_{k\in S}p_{ik}(t)q_{kj}</math>
<math>p_{ij}(t+s)=\sum_{k\in S}p_{ik}(t)p_{kj}(s),i,j\in S</math>
我们将右边称为前，把左边称为后，在上式两边对后面的<math>t=0</math>求导数，形式上得到<math>p'_{ij}(s)=\sum_{k\in S}q_{ik}p{kj}(s)</math>写成矩阵形式得到<math>P'(s)=QP(s)</math>，我们上面这两个式子称作CTMC的'''向后方程'''。
同样可以对Chapman-Kolmogorov方程前面的<math>s=0</math>求导数，形式上得到：<math>p'_{ij}(t)=\sum_{k\in S}p_{ik}(t)q_{kj}</math>写成矩阵形式得到<math>P'(t)=P(t)Q</math>，这两个式子称作CTMC的'''向前方程'''。向前方程和向后方程统称为'''Kolmogorov方程'''。
如果CTMC<math>\{X(t)\}</math>的状态空间<math>S</math>是有限集合，则称<math>\{X(t)\}</math>是'''有限状态CTMC'''。设状态空间<math>S</math>有<math>n</math>个状态，取：<math>q=\max_{i,j\in S}q_{ij}=\max_{i\in S}q_{ii}</math>。则矩阵<math>Qt</math>元素的绝对值都小于<math>qt</math>,<math>(Qt)^2</math>元素的绝对值都小于<math>n(qt)^2</math>，…，<math>(Qt)^k</math>元素的绝对值都小于<math>n^{k-1}(qt)^k</math>，于是下面级数中每个元素都收敛
<math>e^{Qt}\equiv\sum^{\infty}_{k=0}\frac{1}{k!}(Qt)^k</math>
<math>e^{Qt}\equiv\sum^{\infty}_{k=0}\frac{1}{k!}(Qt)^k</math>
<math>(e^{Qt})'=\left(\sum^{\infty}_{k=0}\frac{1}{k!}(Qt)^k\right)'=\sum^{\infty}_{k=1}\frac{1}{(k-1)!}(Qt)^{k-1}Q=e^{Qt}Q</math>
<math>(e^{Qt})'=\left(\sum^{\infty}_{k=0}\frac{1}{k!}(Qt)^k\right)'=\sum^{\infty}_{k=1}\frac{1}{(k-1)!}(Qt)^{k-1}Q=e^{Qt}Q</math>
利用这个等式以及向前方程（也可以用向后方程证明），我们可以证明有限状态CTMC的转移概率矩阵<math>P(t)</math>由转移速率矩阵<math>Q</math>唯一决定，并且有：
利用这个等式以及向前方程（也可以用向后方程证明），我们可以证明有限状态CTMC的转移概率矩阵<math>P(t)</math>由转移速率矩阵<math>Q</math>唯一决定，并且有：
<math>\pmb{P(t)=\sum^{\infty}_{k=0}\frac{1}{k!}(Qt)^k=e^{Qt},t\geq 0}</math>
<math>P(t)=\sum^{\infty}_{k=0}\frac{1}{k!}(Qt)^k=e^{Qt},t\geq 0</math>
====具体例子====
====具体例子====
\end{pmatrix}</math>
\end{pmatrix}</math>
可以看到用<math>Q</math>来描述连续时间马尔科夫链很直接，而试图用<math>P(t)</math>描述连续时间马尔科夫链的话，对每一个t都要计算一次矩阵指数。<math>P(1)</math>第3行<math>[0, 0, 1]</math>，表示一旦进入第三个状态，将永远停留，这也可以直接从<math>Q</math>中直接读出来。<math>Q</math>还可以很方便地描述<math>P(t)</math>中无法直接描述的比例成块性，详见[[马尔科夫链的成块性]]。
可以看到用<math>Q</math>来描述连续时间马尔科夫链很直接，而试图用<math>P(t)</math>描述连续时间马尔科夫链的话，对每一个t都要计算一次矩阵指数。<math>P(1)</math>第3行<math>[0, 0, 1]</math>，表示一旦进入第三个状态，将永远停留，这也可以直接从<math>Q</math>中直接读出来。<math>Q</math>还能很方便地描述<math>P(t)</math>中无法直接描述的比例成块性，详见[[马尔科夫链的成块性]]。
===转移过程和演化性质===
===转移过程和演化性质===
====可达、互通和可约性====
====状态的划分——可达、互通和可约性====
和离散时间马尔科夫链的一样，为了研究CTMC的极限分布以及平稳分布存在的条件，需要引入可达概念。设<math>S</math>是<math>\{X(t)\}</math>的状态空间，如果存在<math>t>0</math>使得<math>p_{ij}(t)>0</math>，则称<math>i</math>'''可达'''<math>j</math>，记作<math>i\to j</math>。如果<math>i\to j</math>且<math>j\to i</math>，则称<math>i,j</math>'''互通'''，记作<math>i\leftrightarrow j</math>。如果<math>S</math>的所有状态互通，则称<math>\{X(t)\}</math>互通。上面这个例子中，所有状态之间均存在转移路径，因此所有状态互通，该CTMC是不可约的。
和离散时间马尔科夫链的一样，为了研究CTMC的极限分布以及平稳分布存在的条件，需要引入可达概念。设<math>S</math>是<math>\{X(t)\}</math>的状态空间，如果存在<math>t>0</math>使得<math>p_{ij}(t)>0</math>，则称<math>i</math>'''可达'''<math>j</math>，记作<math>i\to j</math>。如果<math>i\to j</math>且<math>j\to i</math>，则称<math>i,j</math>'''互通'''，记作<math>i\leftrightarrow j</math>。如果<math>S</math>的所有状态不互通，则称<math>\{X(t)\}</math>'''可约'''。上面这个例子中，所有状态之间均存在转移路径，因此所有状态互通，该CTMC是不可约的。
实际上CTMC的状态划分问题与DTMC的状态划分问题完全等价。对于任何<math>h>0</math>，称<math>\{X(nh)\}=\{X(nh)|n=0,1,2,\dots\}</math>为<math>\{X(t)\}</math>的一个'''离散骨架'''或'''h骨架'''。容易看出，<math>\{X(t)\}</math>的h骨架是有1步转移概率<math>p_{ij}(h)=\mathbb{P}(X(h)=j|X(0)=i)</math>的离散时间马尔科夫链，其状态空间和<math>\{X(t)\}</math>的状态空间相同。并且CTMC的状态划分完全由h骨架的状态划分决定：<math>i\to j</math>的充分必要条件是对存在一个h骨架<math>i \to j</math>。
因为总有<math>p_{ii}(nh)>0</math>，所以对于h骨架来讲，从<math>i</math>出发可以在任意时刻回到<math>i</math>，说明它的所有状态都是'''非周期的'''，该性质为以后的讨论带来许多方便。<math>i\to j</math>的充分必要条件是对存在一个h骨架<math>i \to j</math>。
====状态分布随着时间变化稳定——平稳分布====
类似离散时间马尔科夫链，可以引入CTMC的平稳分布的定义。设<math>P(t)</math>是<math>\{X(t)\}</math>的转移概率矩阵，如果概率分布列<math>\mathbf{p}=(p_0,p_1,\dots)</math>满足<math>\mathbf{p}=\mathbf{p}P(t)</math>，则称<math>\mathbf(p)</math>是<math>\{X(t)\}</math>的'''平稳分布'''，或平稳不变分布。
类似离散时间马尔科夫链，可以引入CTMC的平稳分布的定义。设<math>P(t)</math>是<math>\{X(t)\}</math>的转移概率矩阵，如果概率分布列<math>\mathbf{p}=(p_0,p_1,\dots)</math>满足<math>\mathbf{p}=\mathbf{p}P(t)</math>，则称<math>\mathbf(p)</math>是<math>\{X(t)\}</math>的'''平稳分布'''，或平稳不变分布。
更进一步，我们可以定义平稳过程。如果对于任何<math>n\geq1,s>0,0\leq t_0<t_1<\dots<t_n</math>随机向量<math>(X(t_0+s),X(t_1+s),\dots,X(t_n+s))</math>和<math>(X(t_0),X(t_1),\dots,X(t_n))</math>同分布，则称<math>\{X(t)\}</math>是'''平稳过程'''。显然，当初始分布为平稳分布<math>\mathbf{p}</math>时，<math>\{X(t)\}</math>为平稳过程。
更进一步，我们可以定义平稳过程。如果对于任何<math>n\geq1,s>0,0\leq t_0<t_1<\dots<t_n</math>随机向量<math>(X(t_0+s),X(t_1+s),\dots,X(t_n+s))</math>和<math>(X(t_0),X(t_1),\dots,X(t_n))</math>同分布，则称<math>\{X(t)\}</math>是'''平稳过程'''。显然，当初始分布为平稳分布<math>\mathbf{p}</math>时，<math>\{X(t)\}</math>为平稳过程。
前面我们提到了，在实际问题中我们常用转移速率矩阵<math>Q</math>描述CTMC，而不会用转移概率矩阵<math>P(t)</math>。所以最好能从转移速率矩阵<math>Q</math>入手的到平稳分布。平稳分布的定义<math>\mathbf{p}P(t)=\mathbf{p}</math>提示我们，形式上关于t求导应当有<math>\mathbf{p}Q=\mathbf{p}P'(t)|_{t=0}=\mathbf{p}'=0</math>。事实上，如果互通的CTMC<math>\{X(t)\}</math>有转移速率矩阵<math>Q</math>，则<math>\{X(t)\}</math>有唯一的平稳分布的充分必要条件是下面方程组有唯一非负解，这时<math>\mathbf{p}</math>是<math>\{X(t)\}</math>的唯一平稳分布。：
<math>\begin{cases}
<math>\begin{cases}
====平稳可逆过程====
====平稳可逆过程====
在离散时间马尔科夫链<math>\{X_n\}</math>中，如果概率分布<math>\mathbf{\pi}=(\pi_0,\pi_1,\dots)</math>满足细致平衡条件<math>\pi_ip_{ij}=\pi_jp_{ji}</math>，则称<math>\mathbf{\pi}</math>是<math>\{X_n\}</math>的平稳可逆分布，以平稳可逆分布<math>\mathbf{\pi}</math>为初始分布的<math>\{X_(n)\}</math>称为平稳可逆的过程。CTCM中也有类似结论。
设<math>\{X(t)\}</math>的转移概率矩阵是<math>P(t)</math>，<math>\mathbf{p}=(p_0,p_1,\dots)</math>是概率分布，称
设<math>\{X(t)\}</math>的转移概率矩阵是<math>P(t)</math>，<math>\mathbf{p}=(p_0,p_1,\dots)</math>是概率分布，称
<math>p_ip_{ij}(t)=p_jp_{ji}(t)\ i,j\in S,t\geq 0</math>
<math>p_ip_{ij}(t)=p_jp_{ji}(t)\ i,j\in S,t\geq 0</math>
为'''细致平衡条件'''，若<math>\mathbf{p}</math>满足细致平衡条件，则称<math>\mathbf{p}</math>为<math>\{X(t)\}</math>的'''平稳可逆分布'''或可逆分布。当<math>\mathbf{p}</math>为<math>\{X(t)\}</math>的平稳可逆分布时，<math>\mathbf{p}</math>也是<math>\{X(t)\}</math>的平稳分布，并且<math>\{X(t)\}</math>以<math>\mathbf{p}</math>为初始分布时，<math>\{X(t)\}</math>是平稳可逆过程。
为'''细致平衡条件'''，若<math>\mathbf{p}</math>满足细致平衡条件，则称<math>\mathbf{p}</math>为<math>\{X(t)\}</math>的'''平稳可逆分布'''或'''可逆分布'''。当<math>\mathbf{p}</math>为<math>\{X(t)\}</math>的平稳可逆分布时，<math>\mathbf{p}</math>也是<math>\{X(t)\}</math>的平稳分布。
<math>\{X(t)\}</math>以<math>\mathbf{p}</math>为初始分布时，<math>\{X(t)\}</math>是'''平稳可逆过程'''。此时对于任何<math>0\leq t_1<t_2<\dots<t_n<T</math>，随机向量<math>(X(T-t_1),X(T-t_2),\dots,X(T-t_n))</math>和<math>(X(t_1),X(t_2),\dots,X(t_n))</math>同分布。如果<math>\{X(t)\}</math>是平稳可逆过程，则可以把时间方向倒过来观测这个过程，并且倒过来观测到的这个过程也是CTMC，转移概率和原来的过程一样。
同样的，由于实际问题中常用转移速率矩阵<math>Q</math>描述CTMC，而不是<math>P(t)</math>，所以我们也想从转移速率矩阵<math>Q</math>入手得到平稳可逆分布。对上面给出的细致平衡条件的<math>t</math>求导数，并利用<math>q_{ij}=p'_{ij}(0)</math>得到
<math>p_iq_{ij}=p_jq_{ji},\ i,j\in S</math>
<math>p_iq_{ij}=p_jq_{ji},\ i,j\in S</math>
事实上，若<math>\{X(t)\}</math>互通，有并且存在平稳分布，则细致平衡条件和这个方程有相同的非负解，满足这个方程的概率分布<math>\mathbf{p}</math>也是<math>\{X(t)\}</math>的平稳可逆分布，所以我们也常常称<math>p_iq_{ij}=p_jq_{ji}</math>为CTMC的细致平衡条件。
====具体例子====
====具体例子====
</math>
</math>
通过解平稳分布一节中给出的线性方程组，可以得到CTMC的唯一平稳分布<math>\mathbf{p}=(\frac{5}{18},\frac{4}{18},\frac{1}{2})</math>。平稳分布是不是可逆的呢？以状态0和1为例，有<math>\mathbf{p}_0q_{01}=\frac{5}{9}\neq\frac{2}{9}=\mathbf{p}_1q_{10}</math>，不满足细致平衡条件，所以这个CTMC是不可逆的。