| 第528行： |
第528行： |
| | ==连续时间马尔科夫链== | | ==连续时间马尔科夫链== |
| | | | |
| − | 连续时间马尔科夫链和离散时间马尔科夫链同样具有马尔科夫性质，并且我们后面会看到，连续时间马尔科夫链的很多性质可以完全由一个离散时间马尔科夫链描述。它们之间的区别在于，离散时间马尔科夫链可以用不变的概率转移矩阵<math>P</math>描述，它本质上描述的是经过单位时间后状态的改变。但在连续时间马尔科夫链中，概率转移矩阵<math>P(t)</math>会依赖于状态之间的时间间隔<math>t ,t\in \R</math>。
| + | 连续时间马尔科夫链和离散时间马尔科夫链同样具有马尔科夫性质，并且我们后面会看到，连续时间马尔科夫链的很多性质可以完全由一个离散时间马尔科夫链描述。它们之间的区别在于，离散时间马尔科夫链可以用不变的转移概率矩阵<math>P</math>描述，它本质上描述的是经过单位时间后状态的改变。但在连续时间马尔科夫链中，转移概率矩阵<math>P(t)</math>会依赖于状态之间的时间间隔<math>t ,t\in \R</math>。 |
| | | | |
| − | 我们想与离散时间马尔科夫链中一样，用一个固定的参数描述连续时间马尔科夫链，这个参数也是一个矩阵，它描述了当<math>t</math>变化时，状态转移矩阵<math>P(t)</math>的变化速率。更严格的定义会在后面给出。
| + | 我们想与离散时间马尔科夫链中一样，用一个固定的参数描述连续时间马尔科夫链，这个参数称作矩阵Q，它是概率转移矩阵<math>P(t)</math>在零点的右导数。更严格的定义会在后面给出。 |
| | | | |
| − | ===基本性质=== | + | 回顾一下之前的定义，我们设<math>S</math>是状态空间，<math>\{X(t)\}=\{X(t)|t\geq 0\}</math>是以<math>S</math>为状态空间的连续时间随机过程。如果对于任意正整数<math>n,t_0<t_1<\dots<t_{n+1}</math>和<math>i,j,i_0,i_1,\dots,i_{n-1}\in S</math>，有 |
| − | =====直观模型=====
| |
| | | | |
| − | 我们先用一个直观模型构建连续时间马尔科夫链，让读者能清晰地看到什么参数可以完全确定一个连续时间马尔科夫链。假设有五个房间，编号为<math>1,2,3,4,5</math>。每两个房间由两条通道相连，这两条通道各有一扇单向开放，且方向相反的门（图中箭头代表门，箭头方向代表开放方向）。每扇门会瞬时开放（开放过后立即关闭），并且开放的次数服从速率为<math>Q_{ij}(1\geq i,j\leq 5,i\neq j)</math>的泊松分布，即平均单位时间内开放的次数为<math>Q_{ij}</math>次。一个人从某一个房间出发，只要有方向合适的门瞬时开放，他就会立即进入下一个房间。这个人在某一时刻所处的房间号就是状态空间<math>S=\{1,2,3,4,5\}上的马尔科夫链\{X_t,t\geq 0\}</math>。
| + | <math>\mathbb{P}(X(t_{n+1})=j|X(t_n)=i,X(t_{n-1})=i_{n-1},\dots,X(t_0)=i_0)=\mathbb{P}(X(t_{n+1})=j|X(t_n)=i)</math> |
| | | | |
| − | 我们可将<math>Q_{ij}</math>看做是<math>5\times 5</math>矩阵中第<math>i</math>行，第<math>j</math>的元素，并补充定义对角线元素<math>Q_{ii}=-\sum_{j\neq I}Q_{ij}</math>，它绝对值的大小代表了离开房间<math>i</math>的速率，并把这个矩阵记作<math>Q</math>。很明显，只需要用初始分布<math>\lambda</math>描述从哪一个房间出发，再加上<math>Q</math>，我们就完全确定了上面描述的连续时间马尔科夫链。
| + | 则称<math>\{X(t)\}</math>是连续时间离散状态的马尔科夫链，简称为'''连续时间马尔科夫链'''，后面用英文缩写'''CTMC'''指代。其中的“链”指的就是状态空间<math>S</math>是离散的。 |
| | | | |
| − | =====Q-矩阵=====
| |
| | | | |
| − | 我们称一个矩阵<math>Q=(Q_{ij}:i,j\in S)</math>为'''Q-矩阵'''，当它满足：
| + | ===基本性质=== |
| − | | |
| − | <math>(i)0\leq -Q_{ii}<\infty,\forall i</math>
| |
| − | | |
| − | <math>(ii)Q_{ij}\geq 0,\forall i\neq j</math>
| |
| − | | |
| − | <math>(iii)\sum_{j\in S}Q_{ij}=0,\forall i</math>
| |
| − | | |
| − | 实际上任意一个连续时间马尔科夫链都可以用初始分布<math>\lambda</math>和一个Q-矩阵描述；任意给定一个初始分布<math>\lambda</math>和Q-矩阵，都可以确定一个连续时间马尔科夫链。上面直观模型中的矩阵<math>Q</math>就是一个Q-矩阵
| |
| − | | |
| − | ====从<math>P(t)</math>到Q-矩阵==== | |
| − | 读者应该注意到了，我们在最开始定义连续时间马尔科夫链时，用的是<math>P(t)</math>，而现在建立直观模型的时候，用的是矩阵<math>Q</math>，它们之间有什么样的关系呢？
| |
| − | | |
| − | 我们先回顾一下在第一节中对连续时间马尔科夫链的定义：
| |
| − | 称状态空间<math>S=\{1,2,\ldots,n\}</math>上的随机过程<math>\{X_t,\ t\geq 0\}</math>是'''连续时间马尔科夫链'''<ref name=":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.</ref>(注意此处讨论的是有限状态空间上的马尔科夫链，无限状态空间上的马尔科夫链后面再讨论)，
| |
| − | 若满足<math>\forall n,\ 0=t_0<t_1<\ldots<t_{n-1}<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>P(X(t+s)=j|X(s)=i)</math>与初始时刻<math>s</math>无关，则称该马尔科夫链是'''时齐的'''。简记为<math>P(X(t+s)=j|X(s)=i)=P_{ij}(t)</math>，相应地记转移概率矩阵为<math>P(t)</math>。特别的，<math>P(0)=I</math>。我们所讨论的连续时间马尔科夫链都是时齐的。
| |
| − | | |
| − | =====Chapman-Kolmogorov方程=====
| |
| − | 与离散时间马尔科夫链相同，在连续时间马尔科夫链中也能得到'''C-K方程'''：
| |
| − | | |
| − | <math>P_{ij}(t+s)=\sum_{k\in S}P_{ik}(t)P_{kj}(s),</math>
| |
| − | | |
| − | 对应的矩阵形式为
| |
| − | <math>P(t+s)=P(t)P(s)</math>。
| |
| − | | |
| − | =====转移速率矩阵=====
| |
| − | 我们可以对<math>P(t)</math>求导，并结合C-K方程考察它的变化率：
| |
| − | | |
| − | <math>
| |
| − | \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>\Delta t \to 0</math>时，有<math>P(\Delta t)\to I</math>。假设<math>\lim_{\Delta t\to 0}\frac{P(\Delta t)-I}{\Delta t}</math>存在并记为<math>Q</math>。下面证明矩阵<math>Q</math>就是一个Q-矩阵。
| |
| − | | |
| − | 首先，分析<math>Q</math>的对角线元素
| |
| − | | |
| − | <math>Q_{ii}=\lim_{\Delta t \to 0}\frac{P_{ii}(\Delta t)-1}{\Delta t}\leq 0</math>，
| |
| − | | |
| − | 而非对角线元素
| |
| − | | |
| − | <math>Q_{ij}=\lim_{\Delta t \to 0}\frac{P_{ij}(\Delta t)}{\Delta t}\geq 0\ \ (i\neq j)</math>。
| |
| − | | |
| − | | |
| − | 进一步，考察<math>Q</math>的行和
| |
| − | | |
| − | <math>\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>Q</math>的行和等于0。综合上一小节的Q-矩阵定义，矩阵<math>Q</math>即为Q-矩阵。
| |
| − | | |
| − | 于是我们证明了<math>P(t)</math>在<math>t=0</math>时的变化速率<math>Q</math>就是一个Q-矩阵，也称<math>Q</math>是这个连续时间马尔科夫链的无穷小矩阵或者'''转移速率矩阵'''。
| |
| − | | |
| − | =====向前方程和向后方程=====
| |
| − | 由上面的推导，我们知道<math>\frac{d}{dt}P(t)=P(t)Q</math>成立，我们将它称为'''前向方程'''。
| |
| − | | |
| − | 同理，C-K方程的左式加法的可交换性，可知
| |
| − | <math>
| |
| − | P(t+\Delta t)=P(\Delta t)P(t)
| |
| − | </math>，
| |
| − | 经过同样的推导有
| |
| − | <math>\frac{d}{dt}P(t)=QP(t)</math>成立，
| |
| − | 称它为'''后向方程'''。
| |
| − | | |
| − | ====从Q-矩阵到<math>P(t)</math>====
| |
| − | | |
| − | 另一方面，如果已知上面的向前方程或者向后方程，给定矩阵<math>Q</math>为Q-矩阵，由初值条件<math>P(0)=I</math>，可以证明微分方程存在唯一解<math>P(t)=e^{Qt}</math>。其中<math>e^{Qt}</math>定义为<math>\sum_{k=0}^{\infty}\frac{(tQ)^k}{k!}</math>
| |
| − | | |
| − | ====连续时间马尔科夫链的结构====
| |
| − | | |
| − | 任意一个连续时间马尔科夫链，给定初始状态后，我们如果用一幅图来描述它的状态转移过程，横坐标为时间，纵坐标为所处的状态，得到的函数会是一个右连续的阶梯函数。
| |
| − | | |
| − | 每一个不连续的点称为<math>\{X_t,t\geq 0\}</math>的'''跳跃时间'''，记为<math>J_0,J_1,……</math>。而每两个跳跃时间之间所经历的时间间隔称为<math>\{X_t,t\geq 0\}</math>的'''停留时间'''，记为<math>S_1,S_2,\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}\},\inf\emptyset=\infty，n=0,1,2,\dots</math>
| |
| − | | |
| − | <math>S_n=\begin{cases}
| |
| − | J_n-J_{n-1} &,J_{n}<\infty \\
| |
| − | \infty &,J_n=\infty
| |
| − | \end{cases}</math>
| |
| − | | |
| − | 我们可以通过定义<math>Y_n=X_{J_n}</math>得到一个离散时间马尔科夫链<math>\{Y_n,n=0,1,2,\dots\}</math>，称为<math>\{X_t,t\geq 0\}</math>的跳跃过程或者'''跳跃链'''。若<math>\{X_t,t\geq 0\}</math>的初始分布为<math>\lambda</math>，转移速率矩阵为<math>Q</math>；则它的跳跃链<math>\{Y_n,n=0,1,2,\dots\}</math>的初始分布也为<math>\lambda</math>，概率转移矩阵为<math>\Pi</math>。我们也称<math>\Pi</math>为<math>\{X_t,t\geq 0\}</math>的'''跳跃矩阵'''，它由概率转移矩阵<math>Q</math>完全确定：
| |
| − | | |
| − | <math>\Pi_{ij}=\begin{cases}
| |
| − | -Q_{ij}/Q_{ii} &,j\neq i,Q_{ii}\neq 0\\
| |
| − | 0 &,j\neq i,Q_{ii}=0
| |
| − | \end{cases}</math>
| |
| − | | |
| − | <math>\Pi_{ii}=\begin{cases}
| |
| − | 0 &,Q_{ii}\neq0\\
| |
| − | 1 &,Q_{ii}=0
| |
| − | \end{cases}</math>
| |
| − | | |
| − | ====爆炸====
| |
| − | | |
| − | =====最小的连续时间马尔科夫链=====
| |
| − | 我们前面所讨论的都是有限状态空间中的连续时间马尔科夫链，如果状态空间是无限的，可能会在有限时间内发生无限次状态转移，此时称发生了爆炸。我们定义'''爆炸时间'''<math>\zeta</math>来描述爆炸：
| |
| − | | |
| − | <math>\zeta=\sup_n J_n=\sum_{n=1}^{\infty}S_n</math>
| |
| − | | |
| − | 如果<math>\zeta<\infty</math>，则称发生了爆炸；否则，就没有发生爆炸。当发生爆炸之后，由于时齐性，我们完全可以看做整个随机过程重新开始了，所以可以在状态空间<math>S={1,2,3,\dots}</math>上添加一个特殊的状态<math>\infty</math>来描述爆炸发生后的状态，而不关心具体发生了什么。即当<math>t\geq \zeta</math>时，定义<math>X_t=\infty</math>。我们这样的连续时间马尔科夫链为'''最小的'''，用这种方法描述发生爆炸的连续时间马尔科夫链可以为我们带来很多便利。
| |
| − | | |
| − | =====不发生爆炸的充分条件=====
| |
| − | 大多数情况下，我们关心的都是没有发生爆炸的连续时间马尔科夫链，所以我们给出判断不发生爆炸的三个充分条件，它们非常实用：
| |
| − | | |
| − | <math>(i) |S|<\infty</math>
| |
| − | | |
| − | <math>(ii) \sup_{i\in S}Q_{ii}<\infty</math>
| |
| | | | |
| − | <math>(iii) X_0=i</math>，并且<math>i</math>在跳跃链中是常返的
| + | ====时齐性==== |
| | | | |
| − | 我们称状态<math>i</math>是'''常返的'''，当<math>\mathbb{P}(\sup(\{t\geq 0:X_t=i\})=\infty )=1</math>，直观上来说就是马尔科夫链会无限次返回状态<math>i</math>。
| + | ====转移概率与转移概率矩阵==== |
| | | | |
| − | =====无限状态空间下<math>P(t)</math>与Q-矩阵的关系===== | + | ====历史遗忘性==== |
| − | 在无限状态空间下，给定一个Q-矩阵<math>Q</math>，我们可以像在有限状态空间中一样写出向前方程和向后方程：
| |
| − | <math>\frac{d}{dt}P(t)=P(t)Q</math>
| |
| | | | |
| − | <math>\frac{d}{dt}P(t)=QP(t)</math>
| + | ====Chapman-Kolmogorov方程==== |
| | | | |
| − | 此时虽然两个方程的解并不唯一，但它们仍然有相同的最小非负解<math>P(t),t\geq 0</math>
| + | ====决定CTMC的参数==== |
| | | | |
| − | ===过程描述=== | + | ====转移速率矩阵==== |
| − | ====转移过程====
| |
| − | =====可约性=====
| |
| − | =====周期性=====
| |
| − | ====演化性质====
| |
| − | =====平稳分布=====
| |
| − | =====细致平衡条件=====
| |
| − | =====时间可逆性=====
| |
| | | | |
| | ==参考文献== | | ==参考文献== |
| | | | |
| | <references /> | | <references /> |