概念

背

• 随机过程: 随机过程是定义在给定概率空间上的一组随机变量 ${X(t), t \in T}$. $T$ 表示参数集, 是实数的一个子集, 当 $t$ 取遍参数集 $T$ 中的每个值时, 均有一个随机变量 $X(t)$ 与之对应.
• 参数值: 随机过程 ${X(t), t \in T}$ $t$ 的取值
• 状态空间: 随机过程 ${X(t), t \in T}$ $t$ 取某个值时, $X(t)$ 对应的是一个随机变量, 这个随机变量的所有可能取值状态的集合就是状态空间
• 样本曲线: $s$ 固定, $X(t, s)$ 是 $t$ 的函数, 称为样本曲线
• 马尔可夫过程: 具有无后效性的随机过程. 随机过程在 $t_{n+1}$ 时刻所处的状态概率特性之于 $t_n$ 时刻所处状态有关, 即 $P{X(t) \le x | X(t_n) \le x_n, X(t_{n-1}) \le x_{n-1}, \dots, X(t_0) \le x_0} = P{X(t) \le x | X(t_n) \le x_n}$
• Jackson 开放排队网络: M 个节点的排队网络, 节点 i 的服务速率与队长相关, 服务时间独立, 服从负指数分布. 一个顾客在上一个节点得到服务后, 做一个概率选择, 要么进入另一个节点, 要么离开网络. 所做的选择与历史无关. 网络是开环的, 至少有一个输入和一个输出.
• 排队论的研究内容: 求出各种排队系统的规律, 使设计人员掌握这种规律, 设计 处最优的排队系统, 使管理人员掌握这种规律, 调整与控制 排队系统使他处于最佳运营状态.
• kendall 符号: A/B/C/D/E/F
  • A: 顾客到达时间分布
  • B: 服务窗服务时间分布
  • C: 服务窗数量
  • D: 系统容量
  • E: 顾客源个数
  • F: 服务策略

马尔可夫链

概率DP, 无后效性.

齐次马尔可夫链: 一步转移与当前时间无关, 任意时间位置都可以当作起始时间. 链: 离散

1. 互通: 两个状态能够相互转移到, 称这两个状态互通, 否则不互通
2. 不可约: 强连通
3. 闭集: 无出度的强连通分量
4. 周期: 从 i 出发走 n 步可以回到 i, 所有这样的 n 的 gcd 称为周期. 若 gcd = 1, 则 i 是非周期状态; 否则是周期状态. 互通的状态有相同的周期
5. 常返:

• 非常返: 不是一定能够走回来
• 正常返: 一定能返回, 并且期望步数不是无穷
• 零常返: 一定能返回, 但是期望步数无穷

6. 遍历: 任何点经过无穷步后, 到 i 点的概率都一样, 则 i 状态具有遍历性. 若所有状态都具有遍历性, 则称整个链具有遍历性
7. 稳定状态分布: 经过若干步 (无穷步?) 后, 在每个状态的概率趋于稳定 (所有点都具有遍历性)

定理/性质:

• 有限齐次马尔可夫链不存在非常返.
• 不可约马尔可夫链状所有状态常返性相同, 若是正常返, 则周期相同
• 有限齐次不可约马尔可夫链均是正常返状态
• 齐次马尔可夫链的一个状态是非周期, 正常返, 则该状态是遍历的
• 不可约有限齐次马尔可夫链存在稳定状态, 且与初始分布无关

马尔可夫链可遍历等价与存在稳定状态, 并且唯一, 与初始分布无关, $\eta_i$ 是其稳定后的概率 (极限分布), 则有方程组:

$$\begin{cases} \eta_j = \sum_{i \in S}\eta_ip_{ij} \newline \sum_{i \in S}\eta = 1 \end{cases}$$

若存在正整数 $m$, 使得转移矩阵 $P$ 的 $m$ 次方 $P^m$ 矩阵中, 没有零元素, 则可遍历, 即存在稳定状态. 并且可以通过解方程组得到极限分布 $\eta_i$

排队论

m/m/1/n

单服务窗口

• 负载水平/强度: $\rho = \frac \lambda \mu$
• 系统在状态 $i$ 的概率 (队长为 $i$ 的概率): $$P_i = \begin{cases} \rho^iP_0, &i>0 \newline \frac{1-\rho}{1-\rho^{n+1}}, &i=0 \end{cases}$$
• 排队中的顾客数量期望: $$L_w = \sum_{k=0}^{n-1}kP_{k+1} = \frac\rho{1-\rho} - \frac{\rho + n\rho^{n+1}}{1-\rho^{n+1}}$$
• 忙服务员数量期望: $L_s = 1 - P_0$
• 系统队长期望: $L = L_w + L_s$
• 损失率 (顾客离开的概率, 即系统满员的概率): $P_{\text{损}} = P_n$
• 单位时间进入系统顾客数量期望: $\lambda_{\text{有效}} = \lambda(1 - P_n)$
• 顾客等待时间期望: $T_w = \frac{L_w}{\lambda_{\text{有效}}}$
• 顾客逗留时间期望: $T_{ws} = \frac L {\lambda_{\text{有效}}}$