markov process是markov chain的泛化版本。它描绘了markov chain中访问的每个state以及interval
介绍
和前面说的一样，markov过程由 $X_0, X_1, .. X_{n-1}$ 和 $U_1, U_2,...U_n$ 组成， $X_n$ 表示访问的state, $U_n$ 表示holding time，即经过 $U_n$ 时间后，系统由state $X_{n-1}$ 进入state $X_n$ 。由于 $X_n$ 就是一个markov chain的sample path，所以也被叫做embedded Markov chain。 $U_n$ 服从参数为 $v_l$的指数分布，即
$Pr\left\{U_n\le u| X_{n-1} = l\right\} = 1-exp(-v_l u)$
若令 $S_n = \sum_{m=1}^n U_m$ ，则markov process 可以表示为：
$X(t) = X_n\text{ for } S_n\le t<S_{n+1}\\$
在这里我们假设 $P_{ii} = 0$ ，即不存在self transition。因为在当前的场景下，self transition难以被检测到
由于指数分布memoryless的特性，会有
$Pr\left\{X(t) = j | X(\tau) = i,\left\{X(s)=x(s);s<\tau \right\}\right\} = Pr\left\{X(t-\tau) = j | X(0)\right\}$
例如一个 M/M/1 queue 可以用下图表示：
$\lambda + \mu$ 可以看做2个poisson过程(arrive and departure)的合并, $\lambda/(\lambda + \mu)$ 可以看做两个过程合并后的分裂。
显而易见这就是一个birth-death chain。所以我们可以直接计算 steady-state 的概率：
$$\pi_0 = \dfrac{1-\rho}{2}\
\pi_n = \dfrac{1-\rho^n}{2}\rho^{n-1}\ \rho = \lambda/\mu$$
所以我们可以从三个角度去看一个markov process：
- 第一个视角也就是我们上面的视角；
- 可以将这个过程看成是poisson process，rate为 $v_i$ ，poisson的arrival就是markov的transition
- 将每个transition视为 $n-1$ 个poisson process的复合， $n$ 为状态数量。在state i到state j的rate为$v_iP_{ij}$ 。这些poisson process中，最先达到的即为下一个transition
sample-time 近似
我们可以将holding time分割成多个时间单元，每个时间单元为 $\delta$ 。如果我们假设每次转移只发生在 $\delta$ 的整数倍时间，那么这个过程就可以被视为markov chain，其中
$P_{ij} = q_{ij}\delta\\ P_{ii} = 1-\sum_{j\neq i} P_{ij} = 1- v_i\delta$
当然，$\delta$ 必须满足 $1- v_i\delta \ge 0$
irreducible Markov processes
我们将embedded Markov chain为irreducible的MP称为 irreducible MP。
下面我们将证明，对于markov process来说，其steady-state概率 $p_j = \dfrac{\pi_j/v_j}{\sum_k\pi_k/v_k}$
首先我们证明一条引理：对于一个开始于state i 的markov process，有 $\lim_{t\to\infty}M_i(t)=\infty$ 。
$$\begin{aligned}
Pr\left\{U_n > u\right\} &= \lim_{k\to\infty} \sum_{j=1}^k P_{ij}^{n-1}\exp(-v_j u)\\
& \le \sum_{j=1}^k P_{ij}^{n-1}\exp(-v_j u) + \sum_{j=k+1}^\infty P_{ij}^{n+1} \quad \text{for every }k
\end{aligned}$$
易知：当 $k$ 增加或 $u\to\infty$ ， $Pr\left\{U_n > u\right\} \to 0$ 。所以 $U_n$ 为rv。故 $S_n$ 必然也是rv。则 $\lim_{t\to\infty} Pr\left\{S_n \le t\right\} = 1$ 。而 $\left\{S_n\le t\right\}=\left\{M_i(t)\ge n\right\}$ 。故 对于任意 $n$ 都有 $\lim_{t\to\infty} Pr\left\{M_i(t)\ge n\right\} = 1$ 。所以 $\lim_{t\to\infty}M_i(t,w) = \infty\ \text{WP1}$
令 $M_{ij}(t)$ 表示 $X_0 = i$ 时，在（0, t]内到达state j的次数。下面证明 $M_{ij}(t)$ 为delay renewal process(i = j时则是renewal process)。
令 $N_{ij}(n)$ 表示对于embedded markov chain来说，从i出发进入state j的次数。 我们在countable-state markov chain 说明了 $N_{ij}(n)$ 为delay renewal process。 易知 $M_{ij}(t) = N_{ij}(M_i(t))$ 故
$\lim_{t\to\infty}M_{ij}(t) = \lim_{t\to\infty} N_{ij}(M_i(t)) = \lim_{n\to\infty} N_{ij}(n) = 0 \quad WP1$
所以从state i 出发，经过一段时间后我们必然可以第一次访问state j；再过一段时间(记为 $W_1$ )，必然可以第二次访问state j。后面访问 state j的interval和 $W_1$ 分布相同。故 $M_{ij}(t)$ 为delay renewal process 。我们将访问state j的interval的期望记为 $\bar{W}(j)$
根据我们前面的假设，$U_n$ 满足指数分布，故 $E[U_n|X_{n-1}=j] = 1/v_j$ 。我们为 $M_ij(t)$ 定义一个reward $R_{ij}(t) = \mathbb{I}_{X(t)=j}$ (如下图所示)
我们令 $p_j$ 表示停留在state j的时间比例。则根据renewal process的性质，可得：
$p_j(i) = \lim_{t\to\infty}\dfrac{\int_0^t R_{ij}(\tau)d\tau}{t} = \dfrac{\bar{U}(j)}{\bar{W}(j)} = \dfrac{1}{v_j\bar{W}(j)}$
现假设embedded chain为positive recurrent， steady-state概率为 $\pi_j$ 且 $X_0 = i$ 。根据renewal process的性质，我们有：
$$\lim_{t\to\infty} \dfrac{M_{ij}(t)}{t} = 1/\bar{W}(j)\quad \text{WP1}\\
\lim_{t\to\infty} \dfrac{M_{ij}(t)}{M_i(t)} = \lim_{t\to\infty} \dfrac{N_{ij}(M_i(t))}{M_i(t)} = \lim_{n\to\infty} \dfrac{N_{ij}(n)}{n} = \pi_j\quad \text{WP1}\\
\Rightarrow \dfrac{1}{\bar{W}(j)} = \lim_{t\to\infty} \dfrac{M_{ij}(t)}{t} = \lim_{t\to\infty} \dfrac{M_{ij}(t)}{M_i(t)}\dfrac{M_i(t)}{t} = \pi_j \lim_{t\to\infty}\dfrac{M_{i}(t)}{t}$$
下面我们证明 $\lim_{l\to\infty}\sum_{k=1}^l p_k(i)=1$
我们令 $R^l_{ij}(t)=\mathbb{I}_{X(t)\le l}$ 。则有：
$\lim_{t\to\infty}\dfrac{\int_0^t R^t_{ij}(\tau)d\tau}{t} = \sum_{k=1}^l p_k(i) = \dfrac{E[R^l_j]}{\bar{U}_j}$
则易知：$\sum_{k=1}^l p_k(i)$ 随 $k$ 的增加而增加且必须小于等于1。故 $\lim_{l\to\infty}\sum_{k=1}^l p_k(i)=1$ 。
结合上面 $p_j(i)$ 的式子，我们可以发现 $p_j(i)$ 和 $\dfrac{\pi_j}{v_j}$ 成正比。故 $p_j(i) = \dfrac{\pi_j/v_j}{\sum_k \pi_k/v_k}$
根据上式以及 $\pi_j = \sum_i \pi_i P_{ij}$ 可得：
$p_jv_j = \sum_i p_i q_{ij}\quad \sum_ip_i = 1$
对于一个 irreducible markov process来说，假设 $p_i$ 为上式的解，如果 $\sum_i p_iv_i < \infty$，则该解唯一、大于0且可得到embedded chain的steady-state 概率 $\pi_j$ ；对于embedded chain来说，若为positive recurrent，则也可以计算出满足上式的 $p_i$ 。
当然了，在embedded chain 为 positive recurrent时，仍然存在markov process没有steady-state的情况(下图即为例子)
对于 $\sum_i p_i = 1$ 来说，也有 $\sum_i p_iv_i = \infty$ 的情况出现这种例子很好构造，就不举例子了。
Kolmogorov differential equations
令 $P_{ij}(t) = P\left\{X_t = j | X_0 = i\right\}$ 的概率，则 $\lim_{t\to\infty} P_{ij}(t)=p_j$ 。我们可以将 $P_{ij}(t)$ 重写为：
$$\begin{aligned}
P_{ij}(t) &= \sum_k Pr\left\{X(t) = j, X(s) = k | X(0) = i\right\}\\
&=\sum_k Pr\left\{X(s) = k | X(0) = i\right\}Pr\left\{X(t) = j | X(s) = k\right\}
&= \sum_k P_{ik}(s)P_{kj}(t-s)
\end{aligned}$$
如果令 $t-s$ 大于0单足够小， $P_{kj}(t-s)$ 可以被表示为 $(t-s)q_{kj}+o(t-s)\ \text{for}k\neq j$ ； $P_{jj}(t-s)$ 可以被表示为 $1-(t-s)v_j + o(s)$ 。因此
$$P_{ij}(t) = \sum_{k\neq j} [P_{ik}(s)(t-s)q_{kj}] + P_{ij}(s)[1-(t-s)v_j] + o(t-s)\\
\Rightarrow \dfrac{P_{ij}(t) - P_{ij}(s)}{t-s} = \sum_{k\neq j}(P_{ik}(s)q_{kj}) - P_{ij}(s)v_j + o(s)/s\\
\Rightarrow \dfrac{dP_{ij}(t)}{dt} = \sum_{k\neq j}(P_{ik}(s)q_{kj}) - P_{ij}(s)v_j$$
最后的式子被称为Kolmogorov forward equations
一个例子
考虑一个最简单的M/M/1 queue。
则有：
$$\dfrac{dP_{01}(t)}{dt} = P_{00}(t)q_{01} - P_{01}(t)v_1 = P_{00}\lambda - P_{01}(t)\mu = \lambda - P_{01}(t)(\mu + \lambda)\\
\Rightarrow P_{01}(t) = \dfrac{\lambda}{\mu + \lambda}[1-e^{-(\mu + \lambda)t}]$$
令 $[P(t)]$ 为MM维的矩阵， 第i行j列元素为$P_{ij}$；$[Q]$ 也为MM维的矩阵， 第i行j列元素为$q_{ij} \text{ if } i \neq j$ 或 $-v_j \text{ if } i = j$ ，则Kolmogorov forward equations可以写成：
$\dfrac{d[P(t)]}{dt} = [P(t)][Q]$
对于Q来说，必然存在唯一一个全部元素均大于0的左特征向量。
$$\begin{aligned} P_{ij}(t) &= \sum_k P_{ik}(s)P_{kj}(t-s)\\ &= \sum_{k\neq i}sq_{ik}P_{kj}(t-s) + (1-sv_i)P_{ij}(t-s) + o(s) \end{aligned}$$ $$\Rightarrow \dfrac{P_{ij}(t) - P_{ij}(t-s)}{s} = \sum_{k\neq i}q_{ik}P_{kj}(t-s) + v_iP_{ij}(t-s) + o(s)/s\\ \Rightarrow \dfrac{dP_{ij}(t)}{dt} = \sum_{k\neq i}q_{ik}P_{kj}(t-s) + v_iP_{ij}(t-s)\\ \Rightarrow \dfrac{d[P(t)]}{dt} = [Q][P(t)]$$这被称为Komogorov backward equation
birth-death process
其实和birth-death chain差不多。
为了保证steady state的存在，有 $p_i \lambda_i=p_{i+1}\mu_{i+1}$ 。令 $\rho_i = \dfrac{\lambda_i}{\mu_{i+1}}$ ， 则
$$p_i = p_0 \prod_{j=0}^{i-1}\rho_j
\Rightarrow p_0 = \dfrac{1}{1+\sum_{i=1}^\infty \prod_{j=0}^{i-1}\rho_j}$$
对于 M/M/1 queue来说，可以简化为 $p_i = (1-\rho)\rho^i$
t时刻队伍中顾客数量的期望 $E[X(t)] = \sum_{i=1}^\infty Pr\left\{X(t)\ge i\right\} = \dfrac{\rho}{1-\rho}$
根据Little’s formula，顾客在队伍中花费的平均时间 $E[system time] = \dfrac{E[X(t)]}{\lambda} = \dfrac{\rho}{\lambda(1-\rho)} = \dfrac{1}{\mu - \lambda}$
顾客在队伍中花费的平均等待时间 $E[Queueing time] = \dfrac{1}{\mu - \lambda} - \dfrac{1}{\mu} = \dfrac{\rho}{\mu - \lambda}$
还可以用Little’s formula计算出队列中顾客数量的期望$E[Number in queue] = \dfrac{\lambda\rho}{\mu - \lambda}$
birth-death process可以建模大多数的queue，不过可能比 M/M/1要复杂很多。
Reversibility
在markov process中，对于backward transition来说，其概率 $P_{ij}^*$ 满足 $\pi_iP_{ij}^* = \pi_jP_{ji}$ 。对于markov process来说，该结论同样成立。而且显而易见backward transition本身也是markov process。我们同样定义 $q_{ij}^*$ ，则 $q_{ij}^* = v_jP_{ij}^* = \dfrac{v_i\pi_jP_{ji}}{\pi_i} = \dfrac{v_i\pi_jq_{ji}}{\pi_iv_j} = p_jq_{ji}/p_i$ 。所以我们可以得到相似的结论：
$p_iq_{ij}^* = p_jq_{ji}$
所以当$q_{ij}^* = q_{ij}$ 时，markov process 就是 reversible。对于markov process与embedded chain在reversibility上的关系如下：
对于 steady state 存在的irreducible markov process，若embedded chain为reversible，则markov process也是reversible
一些性质
对于irreducible markov process，如果 $p_i$ 大于0、和为1、满足 $\sum_ip_iv_i < \infty$ 以及 $p_iq_{ij} = p_jq_{ji} \text{ for all}i, j$ ，则 $p_i$ 是对应的markov process的steady-state 概率(所以肯定大于0喽)，process是reversible，embedded chain是positive recurrent。
证明：对 $p_iq_{ij} = p_jq_{ji}$ 同时取和，得：
$\sum_i p_iq_{ij} = p_jv_j \text{ for all j}$
上面的方程加上 $\sum_i p_i = 1$ 可以解出process的steady-state概率。结合$p_iq_{ij}^* = p_jq_{ji}$ ，就可以证明了。
对于irreducible markov process， 如果有 $p_i$ 满足 $\sum_i p_i = 1, \sum_i p_iv_i < \infty$ ，还有一组 $q_{ij}^*$ 恰好满足
$$\sum_j q_{ij} = \sum_j q_{ij}^* \\
p_iq_{ij} = p_jq_{ji}^*$$
那么 $p_i$ 就是steady-state概率，embedded chain为positive recurrent， $q_{ij}^* {}$ 为backward transition的概率。
证明和上面的思路基本一样，就不证了
对于birth-death process来说，如果 $p_i\lambda_i = p_{i+1}\mu_{i+1}$ 有解且满足 $\sum_i p_i = 1， \sum_i p_iv_i<\infty$ 则process为irreducible且embedded chain为positive recurrent, reversible
对于 M/M/1 queue( $\lambda < \mu$ )来说，有：
- departure process也是poisson，rate为 $\lambda$ (我觉得这是backward)
- state $X(t)$ 和t之前的departure无关
- 对于FCFS来说，假设有顾客在t时间离开，则该顾客的到达时间和t之间的departure没有关系
这是Burke’s theorem的MP版