04-2Markov链-连续时间

Lingfeng 2024-11-04

04-2Markov链-连续时间

1. 定义与基本性质

Definition (连续时间Markov链)

随机过程 $\{ X(t),t>0 \}$ ， $S$ 为离散状态空间，若 $\forall s,t\geq 0$ ， $i$ ， $j\in S$ ，有 $P(X(t+s)=j\mid X(s)=i,X(u)=x(u),0\leq u<s)=P(X(t+s)=j\mid X(s)=i)$ 则称 $\{ X(t),t\geq 0 \}$ 为连续时间Markov链。若 $p_{ij}(s,t)$ 与 $s$ 无关，此时称是时齐的。

Definition (正则性)

若以概率1在任意有限长的时间内的次数是有限的，此时有连续性条件 $\lim_{ t \to 0 } p_{ij}(t)=\left\{\begin{align*} 1, & \quad i=j \\ 0, & \quad i\neq j \end{align*}\right.$

Theorem (等待时间分布)

若 $\{ X(t),t\geq 0 \}$ 为连续时间Markov链，假定0时刻刚到达状态 $i$ ，记 $\tau_{i}$ 是在 $i$ 停留的时间，则 $\tau_{i}$ 满足指数分布。

证明
$\begin{align*} & P\{ \tau_{i}>t+s\mid \tau_{i}>s \} \\ & = P\{ X(u)=i,0\leq u<s,X(v)=i,s\leq v<s+t\mid X(u)=i,0\leq u\leq s \} \\ & = P\{ X(v)=i,s\leq v<s+t\mid X(s)=i \} \\ & =P\{ X(u)=i,0\leq u<t\mid X(0)=i \} \\ & =P(\tau_{i}>t) \end{align*}$ 故 $\tau_{i}$ 无记忆性，故服从指数分布。

Theorem (连续时间MC性质)

在转移到另一状态之前处于状态 $i$ 的时间服从参数为 $\mu_{i}$ 的指数分布。
当过程离开状态 $i$ 时，以概率 $p_{ij}$ 进入状态 $j$ ，则 $\sum_{j \neq i}p_{ij}=1$

2. Kolmogorov微分方程

Definition (Q矩阵)

$Q=\left(\begin{matrix} -q_{11} & q_{12} & \dots & q_{1n} \\ q_{21} & -q_{22} & \dots & q_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ q_{n1} & q_{n2} & \dots & -q_{nn} \end{matrix}\right)$ 其中 $q_{ij}=\lim_{ t \to 0 } \frac{p_{ij}(t)-p_{ij}(0)}{t}$

Theorem (性质)

对有限时齐连续时间Markov链，有 $q_{ii}=\sum_{j \neq i}q_{ij}<\infty$

证明
注意到 $1-p_{ii}(t)=\sum_{j \neq i}p_{ij}(t)$ 因此 $\lim_{ t \to 0 } \frac{1-p_{ii}(t)}{t}=\lim_{ t \to 0 } \sum_{j \neq i} \frac{p_{ij}(t)}{t}=\sum_{j \neq i}q_{ij}<\infty$

Theorem (Kolmoforov方程)

向后方程 $p_{ij}'(t)=\sum_{j \neq i}q_{ik}p_{kj}(t)-q_{ii}p_{ij}(t)$ 向前方程 $p'_{ij}(t)=\sum_{j \neq i}q_{kj}p_{ik}(t)-q_{jj}p_{ij}(t)$

证明
注意到 $p_{ij}(t+h)=\sum_{k \in S}p_{ik}(h)p_{kj}(t)$ 因此 $p_{ij}(t+h)-p_{ij}(t)=\sum_{k \neq i}p_{ik}(h)p_{kj}(t)-(1-p_{ii}(h))p_{ij}(t)$ 故证毕。

3. 生灭过程 (Birth-and-Death Process)

Definition (生灭过程定义)

生灭过程是一种特殊的连续时间Markov链，其状态空间为非负整数集合 $S=\{0,1,2,...\}$ ，且只允许在相邻状态间转移。

状态i表示系统中某一物种的数目
生：状态从i增加到i+1
灭：状态从i减少到i-1

Theorem (生灭过程的基本性质)

当系统处于状态i时：

下一个个体到达（生）的时间间隔 $\sim \exp(\lambda_i)$
现有个体离开（灭）的时间间隔 $\sim \exp(\mu_i)$
停留时间 $T_i \sim \begin{cases} \exp(\lambda_0), & i=0 \\ \exp(\lambda_i + \mu_i), & i \neq 0 \end{cases}$
转移概率：

当i = 0时： $P_{01} = 1$
当i ≥ 1时： $P_{i,i-1} = \frac{\mu_i}{\lambda_i + \mu_i}$ ， $P_{i,i+1} = \frac{\lambda_i}{\lambda_i + \mu_i}$

证明

停留时间分布：
- 由于生和灭是独立的指数分布事件
- 当i ≠ 0时，下一次转移时间是两个独立指数分布的最小值
- 根据之前的定理， $\min(X,Y) \sim \exp(\lambda + \mu)$ ，故 $T_i \sim \exp(\lambda_i + \mu_i)$
- 当i = 0时，只可能发生生的事件，故 $T_0 \sim \exp(\lambda_0)$
转移概率：
- 当i = 0时，只能转移到状态1，故 $P_{01} = 1$
- 当i ≥ 1时，应用之前的定理：
- $P(X \leq Y) = \frac{\lambda}{\lambda + \mu}$ ，其中X,Y独立
- 因此 $P_{i,i+1} = \frac{\lambda_i}{\lambda_i + \mu_i}$
- $P_{i,i-1} = \frac{\mu_i}{\lambda_i + \mu_i}$

Example (传染病扩散模型)

一个人群中共有 $N$ 个个体，考虑以下两种传染病扩散模型：
模型条件：

群体中任意两成员之间按速率为 $\lambda$ 的泊松过程接触
每次接触等可能地涉及总体中的 $\binom{N}{2}$ 对成员中的任意一对
如果接触涉及一个感染者和一个未感染者，则未感染者将变成感染者
一旦感染，该成员始终保持感染状态
记 $X(t)$ 表示群体在时刻 $t$ 受感染成员的个数。
问题：
写出Markov链 $\{X(t),t \geq 0\}$ 的转移速率矩阵 $Q$
若假设感染者在感染后立即服药，每个成员的治愈时间相互独立且服从参数为 $\mu$ 的指数分布，治愈时间与感染相互独立，求新的转移速率矩阵 $Q$

解答：

第一问：
- 状态空间： $S = \{0,1,2,...,N\}$
- 当系统处于状态 $i$ 时：
- 感染者人数： $i$
- 未感染者人数： $N-i$
- 可能的感染对数： $i(N-i)$
- 转移速率： $\begin{align*} q_{i,i+1} & = \frac{\lambda}{\binom{N}{2}} \cdot i(N-i)，i = 0,1,...,N-1 \\ q_{i,i} & = -q_{i,i+1}，i = 0,1,...,N-1 \\ q_{N,N} & = 0 \\ \end{align*}$
  其他所有 $q_{ij} = 0$ 。
第二问：
- 此时系统既有感染过程，也有治愈过程
- 感染速率不变： $q_{i,i+1} = \frac{\lambda}{\binom{N}{2}} \cdot i(N-i)$
- 治愈速率： $q_{i,i-1} = i\mu$ （因为有 $i$ 个感染者可能被治愈）
- 转移速率： $\begin{align*} q_{i,i+1} & = \frac{\lambda}{\binom{N}{2}} \cdot i(N-i)，i = 0,1,...,N-1 \\ q_{i,i-1} & = i\mu，i = 1,2,...,N \\ q_{i,i} & = -(q_{i,i+1} + q_{i,i-1}) \end{align*}$
  其他所有 $q_{ij} = 0$ 。

Definition (局部平衡)

对于生灭过程，当系统达到平稳状态时，任意两个相邻状态i和i+1之间的流量相等，即：
$\lambda_i\pi_i = \mu_{i+1}\pi_{i+1}$
其中：

$\lambda_i$ 是从状态i到i+1的转移率（生率）
$\mu_{i+1}$ 是从状态i+1到i的转移率（灭率）
$\pi_i$ 是状态i的平稳概率

Theorem (局部平衡方程的必要性)

对于生灭过程，平稳分布必须满足局部平衡方程。

证明：

考虑平稳分布的定义：πQ = 0
对于生灭过程，Q矩阵是三对角矩阵：
$\begin{align*} q_{i,i+1} & = \lambda_{i} \\ q_{i,i-1} & = \mu_{i} \\ q_{i,i} & = -(q_{i,i+1} + q_{i,i-1}) \end{align*}$
写出第i个平衡方程：
$\pi_{i-1}\lambda_{i-1} - \pi_i(\lambda_i + \mu_i) + \pi_{i+1}\mu_{i+1} = 0$
这个方程说明：
- 进入状态i的总流量 = 离开状态i的总流量
- 对生灭过程，这等价于相邻状态间流量相等

Example (应用)

在排队系统中：

设λ是到达率，μ是服务率
则平稳分布满足：
$\lambda\pi_i = \mu\pi_{i+1}$
可以递推得到：
$\pi_{i+1} = \frac{\lambda}{\mu}\pi_i = \rho\pi_i$
其中ρ = λ/μ称为业务强度