第十三章 离散时间 Markov 链

常返状态是经过无穷多步后仍要返回的状态，而瞬过状态是经过足够大的步数后，就不会再返回来的状态（也就是有概率再也回不来的）

离散时间 Markov 过程是具有一阶记忆特性的离散时间随机过程，而 离散时间 Markov 链则是状态离散的 Markov 过程。设 $X_n$ 为一个离散时间 Markov 链，则转移概率质量函数满足 $$P\{X_{n+1}=a_{n+1}|X_n=a_n,\cdots ,X_0=a_0\}=P\{X_{n+1}=a_{n+1}|X_n=a_n\}$$ （这是 Markov 链的充要条件）

齐次连续时间 Markov 链的状态停留时间是指数分布的随机变量

嵌入 Markov 链是离散的

13-1-2 状态方程

记 $p_i(n)=P\{X_n=i\}$ 为 Markov 过程 $X_n$ 在时刻 n 出现状态 i 的概率，称为 $X_n$ 的状态概率。 称 $P(n)=(p_1(n),\cdots ,p_N(n))$ 为 Markov 过程 $X_n$ 的状态过程矢量。显然 ${\sum }_{i=1}^N{p}_i(n)=1$。

记 ${\pi }_{ij}(m,n)=P\{X_n=j|X_m=i\}$ 表示在时刻 m 时状态为 i 的条件下，到时刻 n 状态为 j 的条件概率，称为 Markov 链 $X_n$ 的转移概率。称矩阵 $$\begin{array}{rl}\Pi (m,n)& ={\left[{\pi }_{ij}(m,n)\right]}_{N\times N}\\ & =\left[\begin{array}{cccc}{\pi }_{11}(m,n)& {\pi }_{12}(m,n)& \cdots & {\pi }_{1N}(m,n)\\ {\pi }_{21}(m,n)& {\pi }_{22}(m,n)& \cdots & {\pi }_{2N}(m,n)\\ ⋮& ⋮& ⋮& \\ {\pi }_{N1}(m,n)& {\pi }_{N2}(m,n)& \cdots & {\pi }_{NN}(m,n)\end{array}\right]\end{array}$$ 为从时刻 $m$ 到时刻 $n$ 的状态转移矩阵。显然矩阵的每一个元素都非负且每行的和为 1 ，即 $${\pi }_{ij}(m,n)⩾0,\sum _{j=1}^N{\pi }_{ij}(m,n)=1$$ 显然，由全概率公式知 $$\mathbf{P}(n)=\mathbf{P}(m)\mathbf{\Pi }(m,n)$$ 若 $n>r>m$，则由 $\mathbf{P}(n)=\mathbf{P}(r)\mathbf{\Pi }(r,n)$ 和 $\mathbf{P}(r)=\mathbf{P}(m)\mathbf{\Pi }(m,r)$ 知 $$\Pi (m,n)=\Pi (m,r)\Pi (r,n)$$

13-1-3 齐次与平稳 Markov 链

齐次 Markov 链

若有 ${\pi }_{ij}(m,n)={\pi }_{ij}(n-m)$ 对任意 $i,j$ 成立，即转移概率 ${\pi }_{ij}(m,n)$ 只和时间间隔 $n-m$ 有关，与起点时刻 $m$ 无关，则为齐次 Markov 链。

平稳 Markov 链

当齐次 Markov 链的状态概率矢量 $P(n)=P$ 为常矢量时，为严平稳 Markov 链，有 $P=P\Pi$

13-2 平稳 Markov 链的状态分类

若存在 $n\ge 0$，使 ${\pi }_{ij}(n)>0$，则称状态 j 是从状态 i 可达的，记作 $i\to j$， 两个互相可达的状态 i 和 j 称为互达的，记作 $i\leftrightarrow j$。

互达性是一种等价关系，满足自反性，对称性和传递性。

在集合 $S$ 中，所有和 $i$ 等价的元素构成 $S$ 的子集，称为一个等价类 $\bar{i}$。

若 Markov 链 $X_n$ 的所有状态都属于同一个等价类，即所有状态都互达，则称该 Markov 链是不可约的，反之为可约的

状态空间分解定理 状态空间 $S$ 必可分解为 $$S=N\cup C_1\cup C_2\cup \cdots \cup C_k\cup \cdots$$ 式中，$N$ 是瞬过状态的集合； $C_1,C_2,\cdots ,C_k,\cdots$ 是两两互不相交的由常返状态组成 集，且满足如下条件:

1. 对每个 $k,C_k$ 内任意两个状态是互达的。
2. 对任意 $k\ne l$，以及任意 $i\in C_k$ 和 $j\in C_l，i$ 和 $j$ 互不可达。

• 零常返：返回自身所需的步数为无穷大（只存在于无限状态的 Markov 链中）
• 正常返：返回自身所需的步数为有限数
• 记 $T_i$ 为首次返回状态 i 需要的步数，$E\{T_i\}={\sum }_{n=1}^{\infty }n{f}_{ii}(n)$
• $E\{T_i\}=\infty$：零常返；$E\{T_i\}<\infty$：正常返

常返状态的周期

对常返状态 i，使 ${\pi }_{ii}(n)>0$ 的所有 n 的最大公约数称作状态 i 的周期，记作 $d(i)$。

• 若对所有 $n\ge 1$，都有 ${\pi }_{ii}(n)=0$，则约定 i 的周期为 $\infty$；
• 若 $d(i)=1$，则称状态 i 为非周期的（即任意步上都能返回）

等价类同周期

遍历：非周期的正常返状态

第十四章 连续时间 Markov 过程

齐次连续时间 Markov 过程在时间段 $h$ 内保持在状态 $i$ 的概率为 $${\pi }_{ii}(h)=P\left\{T_i>h\right\}=e^{-{\nu }_{i}h}=1-{\nu }_{i}h+o(h)$$ 因此在时间段 $h$ 内离开状态 $i$ 的概率为 $$1-{\pi }_{ii}(h)={\nu }_{i}h+o(h)$$ 从式 (14.1.8) 可以看出, Markov 链离开状态 $i$ 的概率和时间近似成正比, 比例系数 ${\nu }_i$ 称 为状态率。 齐次连续时间 Markov 链从状态 $i$ 到状态 $j$ 的状态转移率定义为 $${\mu }_{ij}={\pi }_{ij}^{\prime }(0)=\underset{h\to 0}{\lim }\frac{{\pi }_{ij}(h)-{\pi }_{ij}(0)}{h}=\{\begin{array}{ll}{\lim }_{h\to 0}\frac{{\pi }_{ii}(h)-1}{h},& i=j\\ {\lim }_{h\to 0}\frac{{\pi }_{ij}(h)}{h},& i\ne j\end{array}$$ 上式用到了 $${\pi }_{ij}(0)=\{\begin{array}{ll}1,& i=j\\ 0,& i\ne j\end{array}$$

若连续时间 Markov 链的状态数有限, 设为 $N$, 则此时暂态方程为 $$\frac{\mathrm{d}}{\mathrm{d}t}\mathbf{P}(t)=\mathbf{P}(t)\mathbf{Q}$$ 式中, 矩阵 $\mathbf{Q}$ 具有如下表达 $$\mathbf{Q}={\left({\mu }_{ij}\right)}_{N\times N}$$ 而稳态概率满足下列线性方程组 $$PQ=0$$

第十五章 排队论初步

用 A/B/C/D 描述排队系统，其中 A 代表用户到达时间规律，B 表示用户服务时间规律，C 表示资源窗口数及其结构，D 表示排队规律。

• 到达率（服务率）：$\lambda$（$c\mu$）
• 到达间隔（服务时间）的均值：$1/\lambda$（$1/c\mu$）
• 比例系数：$\rho =\lambda /c\mu$
• $p_0={\left({\sum }_{i=0}^{c-1}\frac{(c\rho {)}^i}{i!}+\frac{(c\rho {)}^c}{c!}\frac{1-{\rho }^{K-c+1}}{1-\rho }\right)}^{-1}$，$p_k=\{\begin{array}{l}\frac{(c\rho {)}^k}{k!}{p}_0,0⩽k⩽c\\ \frac{c^c}{c!}{\rho }^k{p}_0,c⩽k⩽K\end{array}$
• $c=1,K=\infty$ 时 $p_0=1-\rho ,p_k=(1-\rho ){\rho }^k$