Simulation Theory

CS专业课学习笔记

確率分布

(0-1)分布

定义：若X的概率分布律为

$X$	$0$	$1$
$P$	$1-p$	$p$

其中$0 < p < 1$，就称X服从参数为p的0-1分布（或两点分布），记为$\color{blue}{X \sim 0-1(p)}$ 或 $\color{blue}{X \sim B(1, p)}$

其分布律还可以写成：$P(X = k) = p^k(1 - p)^{1-k}, \quad k = 0,1$

伯努利试验，二项分布

设试验E只有两个可能的结果：$A$或$\overline{A}$，且$P(A) = p, \quad 0 < p < 1$。将E独立地重复进行n次，则称这一串重复地独立试验为n重伯努利试验

二项分布定义：若$X$地的概率分布律为：

$$\begin{aligned} \color{blue}{P(X = k) = C_n^k p^k (1 - p)^{n-k}, \quad k = 0, 1, \cdots, n} \end{aligned}$$

其中$n \geq 1,\quad 0 < p < 1$，就称$X$服从参数为$n,p$的二项分布(Binomial)，记为$\color{blue}{X \sim B(n, p)}$

• $E(X) = np$
• $V(X) = np(1 - p)$

例題

〇×で解答する試験において、気まぐれに解答する。10問ある時、正答の個数を $X$ として、$X$ の平均と分散を求めよ。また、$X \geq 8$ となる確率を求めよ

• $E(X) = np = 10 * 0.5 = 5$
• $V(X) = np(1 - p) = 10 * 0.5 * 0.5 = 2.5$
• $P(X \geq 8) = P(X = 8) + P(X = 9) + P(X = 10) = C_{10}^8 (\frac{1}{2})^8 (\frac{1}{2})^2 + C_{10}^9 (\frac{1}{2})^9 (\frac{1}{2}) + C_{10}^{10} (\frac{1}{2})^{10} (\frac{1}{2})^0 \simeq 0.0547$

泊松分布

定义：若$X$的概率分布律为

$$\begin{aligned} \color{blue}{P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}, \quad k = 0, 1, 2, \cdots} \end{aligned}$$

• $E(X) = \lambda$
• $V(X) = \lambda$

其中$\lambda > 0$，就称 $X$ 服从参数为 $\lambda$ 的泊松分布(Poisson)，记为$\color{blue}{X \sim \pi(\lambda)}$或$\color{blue}{X \sim P(\lambda)}$

泊松分布的用途：

• 某人一天内收到的微信的数量
• 来到某公交汽车站的乘客
• 某放射性物质发射出的粒子
• 显微镜下某区域中的白血球

如果某事件以固定强度 $\lambda$，随机且独立地出现，该事件在单位时间内出现地次数（个数）可以看成是服从泊松分布

二项分布与泊松分布有以下近似关系：

$$\begin{aligned} C_n^k p^k (1 - p)^{n - k} \simeq \frac{e^{-\lambda}\lambda^k}{k!}, \quad \lambda = np, n > 10, p < 0.1 \end{aligned}$$

例題

ある製品の製造工程では、微小領域に1万個の点にレーザーを当てていく。位置をずれるのは2万個に一つであるという。この工程ではずれが一つもないという確率を求めよ

• $\lambda = np = 10000 * \frac{1}{20000} = 0.5$
• $E(X) = \lambda = 0.5$
• $V(X) = \lambda = 0.5$
• $P(X = 0) = P(0, \lambda) = e^{-0.5} \cdot \frac{0.5^0}{0!} \simeq 0.606531$
• $B(n, p) = C_{10000}^0 (\frac{1}{20000})^0 (\frac{19999}{20000})^{10000} \simeq 0.606523$

几何分布

定义：若 $X$ 的概率分布律为

$$\begin{aligned} \color{blue}{P(X = k) = p(1 - p)^{k - 1}, \quad k = 1, 2, 3, \cdots} \end{aligned}$$

其中 $0 < p < 1$，称 $X$ 服从参数为 $p$ 的几何分布(Geometric)，记为 $\color{blue}{X \sim Geom(p)}$

几何分布的用途：在重复多次的伯努利实验中，实验进行到某种结果出现第一次为止，此时的试验总次数服从几何分布。如：射击，首次击中目标时射击的次数

• $E(X) = \frac{1}{p}$
• $V(X) = \frac{1 - p}{p^2}$

例題

合格率10%の試験を挑み、$X$ 回目で初めて合格する。$X$ の平均と分散を求めよ。また、$X = 3$ となる確率を求めよ

• $E(X) = \frac{1}{p} = \frac{1}{0.1} = 10$
• $V(X) = \frac{1 - p}{p^2} = \frac{1 - 0.1}{0.1^2} = 90$
• $P(X = 3) = 0.9^2 * 0.1 = 0.081$

均匀分布

若 $X$ 的概率密度函数为

$$\begin{aligned} \color{blue}{f(x) = \begin{cases} \frac{1}{b-a}, \quad &x \in (a, b) \\ 0, \quad &\text{其他} \end{cases}} \end{aligned}$$

其中 $a < b$，就称 $X$ 服从 $(a, b)$ 上的均匀分布(Uniform)，记为 $\color{blue}{X \sim U(a, b)}$ 或 $\color{blue}{X \sim \text{Unif}(a, b)}$

均匀分布的性质：均匀分布具有等可能性，即，服从 $U(a, b)$ 上的均匀分布的随机变量 $X$ 落入 $(a, b)$ 中的任意子区间上的概率只与其区间长度有关与区间所处的位置无关。即 $X$ 落入 $(a, b)$ 中的等长度的任意子区间上是等可能的。

• $E(X) = \frac{b + a}{2}$
• $V(X) = \frac{(b - a)^2}{12}$

例題

ある自動車のブレーキテストで時速50kmでブレーキをかけた時、止まるまでに要する距離 $X$ は区間 $(a, b)$ 上の一様分布に従うという。$b$ よりも $a$ に近いところで止まる確率を求めよ

$$P(a < X < \frac{a+b}{2}) = \int_a^{\frac{a+b}{2}} \frac{1}{b - a} dx = \frac{1}{2}$$

指数分布

若 $X$ 的概率密度函数为

$$\begin{aligned} \color{blue}{f(x) = \begin{cases} \lambda e^{-\lambda x}, \quad &x > 0 \\ 0, \quad &x \leq 0 \end{cases}} \end{aligned}$$

其中 $\lambda > 0$，就称 $X$ 服从参数为 $\lambda$ 的指数分布(Exponential)，记为 $\color{blue}{X \sim E(\lambda)}$ 或 $\color{blue}{X \sim \text{Exp}(\lambda)}$

• $E(X) = \frac{1}{\lambda}$
• $V(X) = \frac{1}{\lambda^2}$

随机变量 $X$ 的分布函数为：

$$\begin{aligned} \color{blue}{F(x) = \begin{cases} 1 - e^{-\lambda x}, \quad &x > 0 \\ 0, \quad &x \leq 0 \end{cases}} \end{aligned}$$

指数分布的性质：指数分布具有无记忆性

指数分布的用途：

• 指数分布可以用来表示独立随机事件发生的时间间隔，比如旅客进机场的时间间隔，中文维基百科新条目出现的时间间隔等等
• 在排队论中，一个旅客接受服务的时间长短也可以用指数分布来近似
• 无记忆性的现象（连续时）

正态分布

若 $X$ 的概率密度函数为

$$\begin{aligned} \color{blue}{f(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x - \mu)^2}{2\sigma^2}}, \quad -\infty < x < +\infty} \end{aligned}$$

其中 $-\infty < \mu < +\infty, \sigma > 0$ ，就称 $X$ 服从参数为 $\mu, \sigma$ 的正态分布（或高斯分布），记为 $\color{blue}{X \sim N(\mu, \sigma^2)}$

• $E(X) = \mu$
• $V(X) = \sigma^2$

正态分布的特征：

• $f(x)$ 关于 $x = \mu$ 对称
• 当 $x \leq \mu$ 时，$f(x)$ 是严格单调递增函数
• $f_{max} = f(\mu) = \frac{1}{\sqrt{2\pi}\sigma}$
• $\lim_{|x - \mu| \rightarrow \infty} f(x) = 0$

正态分布的参数：

• $\mu$ 为位置参数，决定对称轴位置
• $\sigma$ 为尺度参数，决定曲线分散程度

正态分布的用途：

• 自然界和人类社会中很多现象可以看做正态分布
  • 例如：人的生理尺寸（身高，体重），医学检验指标（红细胞数，血小板），测量误差等等
• 多个随机变量的和可以用正态分布来近似
  • 例如：注册MOOC的某位同学完成所有作业的时间，二项分布等等

标准正态分布

若 $Z \sim N(0, 1)$，称 $Z$ 服从标准正态分布

• $Z$ 的概率密度函数：$\phi(z) = \frac{1}{\sqrt{2\pi}}e^{-\frac{z^2}{2}}$
• $Z$ 的分布函数：$\Phi(z) = \int_{-\infty}^Z \frac{1}{\sqrt{2\pi}} e^{-\frac{t^2}{2}} \, dt$

标准正态分布的分布函数有一个重要的性质：

$$\Phi(-z_0) = 1 - \Phi(z_0)$$

对于任意的实数 $z_0$ 都成立

此外，当 $X \sim N(\mu, \sigma^2)$ 时，$\frac{X - \mu}{\sigma} \sim N(0, 1)$，由此可知，当 $X \sim N(\mu, \sigma^2)$ 时，对于任意实数 $a$，有

$$\color{blue}{F_X(a) = P(X \leq a) = P(\frac{X - \mu}{\sigma} \leq \frac{a - \mu}{\sigma}) = \Phi(\frac{a - \mu}{\sigma})}$$

マルコフ連鎖(Markov chain)

马尔可夫过程是研究信号多级传输，分子的布朗运动，顾客服务，计算机网络流量等诸多问题时使用的经典模型

確率過程

時間 $t$ に応じて偶然に変化する結果を $X(t)$ とする

• $X(t)$：確率変数
• $\lbrace X(t); t \geq 0 \rbrace$：確率過程

例：

• $t$ 時に届くemailの数
• $t$ 日の株価の終値
• コイン投げ $t$ 回における表の出現回数

マルコフ過程：ある時点における現象の確率が直前の結果だけで決まる確率過程

• マルコフ連鎖：離散時間 $\lbrace t = 0, 1, 2, \cdots \rbrace$、離散値 $\lbrace i;i = 0, 1, 2, \cdots \rbrace$ をとるマルコフ過程
• ポアソン過程：連続時間 $t \geq 0$、離散値をとるマルコフ過程

マルコフ連鎖の例

0, 1のラベルがついた球が入っている箱A, 箱Bを考える

初めにどちらかの箱から球を取り出し、玉のラベルを書き出す。次にラベルに応じて次に取り出す箱を決める。球はその都度元の箱へ戻す

• ラベルが0なら箱A
• ラベルが1なら箱B

マルコフ連鎖の定義

$X_n;n = 0, 1, 2, \cdots$ が任意の $n \geq 0$ と、任意の $S$ の要素 $x_0, x_1, \cdots, i, j$ について次のような性質を持つとき、マルコフ連鎖という

$$P(X_{n+1} = j \ |\ X_0 = x_0, X_1 = x_1, \cdots, X_n = i) = P(X_{n+1} = j \ |\ X_n = i)$$

2状態マルコフ連鎖

ある学習モデルを考える。一連の実験において正答した次は確率 $a$ で誤答し、誤答した次は確率 $b$ で正答する。このマルコフ連鎖の推移図と推移行列を求めよ。（ただし、正答の状態を0、誤答の状態を1とおく）

マルコフ連鎖の時間ダイナミクス

• $p_{ij}$ は状態 $i$ から状態 $j$ へ一段階で推移する確率
• 状態 $i$ から状態 $j$ へちょうど $n$ 段かかって推移する確率を $p^{(n)}_{ij}$ とおく ($n$ 段階の推移確率)
• 時間に一様な場合なので $m$ に無関係

$$p_{ij}^{(n)} = P(X_{m+n} = j \ |\ X_m = i)$$

查普曼-柯尔莫格洛夫方程(Chapman-Kolmogorov equation,C-K equation)

チャップマン・コルモゴロフの等式(Chapman–Kolmogorov equation)：一般に $(n + m)$ 段階では

$$p_{ij}^{(n + m)} = p_{i0}^{(n)} p_{0j}^{(m)} + p_{i1}^{(n)} p_{1j}^{(m)} + \cdots + p_{ik}^{(n)} p_{kj}^{(m)} + \cdots = \sum_k p_{ik}^{(n)} p_{kj}^{(m)}$$

$n$ 段階の推移確率 $p_{ij}^{(n)}$ を $(i, j)$ 成分とする行列を $P^{(n)}$ ($n$ 段階の推移行列)と書く

$$P^{(n+m)} = P^{(n)} P^{(m)}$$

• $P^{(1)} = P$
• $P^{(2)} = P^{(1+1)} = PP = P^2$
• $P^{(3)} = P^{(2+1)} = P^2P = P^3$
• $P^{(n)} = P^n$

初期確率 $\alpha_i$ (状態 $i$ から始まる確率)が次のように与えられているとする

$$\alpha_i = P(X_0 = i), \quad i = 0, 1, 2, \cdots \quad (\sum_i \alpha_i = 1)$$

マルコフ連鎖が $n$ 段階後に状態 $j$ にある確率 $P(X_n = j)$ は、

$$P(X_n = j) = \sum_i \alpha_i p_{ij}^{(n)}$$

したがって、初期確率ベクトル $\mathbf{\alpha} = (\alpha_0, \cdots, \alpha_i, \cdots)$ とおくと $P(X_n = j)$ は $\mathbf{\alpha}P^n$ の $(i, j)$ 成分である

例題2.1

$$\alpha = (0, 0, 1)$$

と置く

$$\begin{aligned} \mathbf{\alpha}P^2 = \begin{pmatrix} 0.5 & 0.4 & 0.4 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.3 & 0.5 \end{pmatrix} \begin{pmatrix} 0.5 & 0.4 & 0.4 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.3 & 0.5 \end{pmatrix} = (0.29, 0.35, 0.36) \end{aligned}$$

状態の分類

ある整数 $n \geq 0$ に対し、$p_{i,j}^{(n)} > 0$ の時、状態 $j$ は状態 $i$ から到達可能であるといい、$i \rightarrow j$ と表す。$i, j$ が互いに到達可能であるとき、$i \leftrightarrow j$ と表す

関係 $\leftrightarrow$ は次の同値関係を満たす

• $i \leftrightarrow j$：反射法則
• $i \leftrightarrow j$ ならば $j \leftrightarrow i$：対称法則
• $i \leftrightarrow j$ および $j \leftrightarrow k$ ならば、$i \leftrightarrow k$：推移法則

状態の全体は、同値な組に分割することができる（同値な組に含まれる状態は互いに到達可能）

同値な組がただ一つなとき、そのマルコフ連鎖は既約であるという

• 少なくとも１個のループができている = 既約

例題2.2

$p_{ii} = 1$ の時、状態 $i$ は吸収的である

第一个状态转移图有错（$\frac{1}{4}, \frac{3}{4}$ 颠倒），图片待修改！！！
第二个状态转移图也有错，$p_{00} = 1$ ，图片待修改！！！

状態 $i$ から出発するマルコフ連鎖が状態 $i$ へ初めて戻るまでに要する時間（段階数）を $\tau_i$ とする。すなわち

$$\tau_i = \min \lbrace n \geq 1;X_n = i \rbrace$$

この時、$\tau_i$ が有限となる確率が1の時、状態 $i$ は再帰的であるという。一方、1よりも小さい時、状態 $i$ は一時的であるという

• 状態 $i$ が再帰的、状態 $i$ と状態 $j$ は互いに到達可能 $\rightarrow$ 状態 $j$ も再帰的
• 状態 $i$ が一時的、状態 $i$ と状態 $j$ は互いに到達可能 $\rightarrow$ 状態 $j$ も一時的

再帰的、一時的の性質：

• 規約なマルコフ連鎖においては全ての状態は再帰的か一時的かのどちらか
  • どれか一つの状態をチェックすればよい
• 有限マルコフ連鎖（有限個の状態からなる連鎖）においては、状態 $i$ が一時的であるための必要十分条件は、$i \rightarrow j$ であるが $i \nLeftarrow j$ となる $j$ があることである
  • 有限マルコフ連鎖の一時的な組は"閉じてない"
  • 少なくとも一つの再帰的な状態が存在する（規約なら再帰的）
• 状態 $i$ が再帰的であれば、$i$ から出発すると何回も $i$ に戻ってくる。したがって、状態 $i$ が再帰的であるための必要十分条件は、$i$ から出発して $i$ へ戻る回数の平均が無限大になることである

式で書くと

$$\begin{aligned} ln = \begin{cases} 1, \quad X_n = 1 \\ 0, \quad X_n \neq 1 \end{cases} \qquad T = \sum_{n=1}^{\infty} l_n \end{aligned}$$

とおき、マルコフ連鎖が状態 $i$ から出発するときの条件的確率で測った $T$ の期待値を求めると、

$$E_i[T] = \sum_{n=1}^{\infty} E_i[l_n] = \sum_{n=1}^{\infty} 1 \times P(X_n = i \ |\ X_0 = i) = \sum_{n=1}^{\infty}p_{ii}^{(n)}$$

となる。したがって、状態 $i$ は

• $\sum_{n=1}^{\infty}p_{ii}^{(n)} = \infty$ ならば再帰的
• $\sum_{n=1}^{\infty}p_{ii}^{(n)} < \infty$ ならば一時的

別の表現として

状態 $i$ から出発して、$n$ 段階目ではじめて $j$ に到達する確率を $f^{(n)}_{ij}$（初到達確率）とおく

$$f_{ij}^{(1)} = p_{ij}$$

$$f_{ij} = \sum_{n=1}^{\infty}f_{ij}^{(n)}: \text{最終到達確率}$$

• $\sum_{n=1}^{\infty}f_{ii}^{(n)} = \infty$ ならば再帰的
• $\sum_{n=1}^{\infty}f_{ii}^{(n)} < \infty$ ならば一時的

例題2.3

マルコフ連鎖の再帰性と一時性

思路：求解 $\sum_{n=1}^{\infty}p_{ii}^{(n)}$ 即可

• $p_{00}^{(n)} = 1 \rightarrow \sum_{n=1}^{\infty} p_{00}^{(n)} = \infty$：状態 0 は再帰的
• $\sum_{n=1}^{\infty} p_{11}^{(n)} = \sum_{n=1}^{\infty} (\frac{1}{2})^n = \frac{\frac{1}{2}}{1 - 1 - 2} = 1$：状態 1 は一時的

进入0的话一直循环，如果是1的话，只会进入1次0，一旦进入0的话就出不来了

状態 $i$ が再帰的なとき、$\tau_i$ の平均値

$$\mu_i = \sum_{n=1}^{\infty} nf_{ii}^{(n)}$$

を平均再帰時間といい、$\mu_i < \infty, \mu_i = \infty$ に応じて $i$ をそれぞれ正状態、零状態という

状態 $i$ に対して、$p_{ii}^{(n)} > 0$ を満たす整数 $n \geq 1$ の全体の最大公約数を状態 $i$ の周期といい、$d_i$ で表す。$d_i = 1$ の時、$i$ は非周期的であるという。また、全ての $n$ に対して $p_{ii}^{(n)} = 0$ の時は $d_i = 1$ とする。非周期的、再帰的、正状態をエルゴード状態という

例題2.4

マルコフ連鎖の周期

对于状态 $i$，满足 $p_{ii}^{(n)} > 0$ 的整数 $n \geq 1$ 的所有最大公约数为状态 $i$ 的周期，$d_i = 1$ 的时候，$i$ 是非周期。

第二个周期为2的例子，是以01循环，故周期为2

例題2.5

今日の天気が晴れなので

$$\alpha = (1, 0, 0)$$

• $\alpha \mathbf{P} = (0.4, 0.6, 0)$
• $\alpha \mathbf{P}^2 = (0.28, 0.54, 0.18)$

マルコフ連鎖の定常分布

マルコフ連鎖が既約でエルゴード状態である場合，推移行列の極限値が存在する

$$\pi_j = \lim_{n \rightarrow \infty}p_{ij}^{(n)}$$

これは状態 $i$ に無関係であり、

$$\pi_j = \frac{1}{\mu_j}, \quad j = 0, 1, 2, \cdots$$

$\mu_j$ は状態 $j$ の平均再帰時間、この $\pi_j$ は次の方程式を解いて得られ，解は正の値としてただ一通りに決まる

$$\color{blue}{\mathbf{\pi} P = \mathbf{\pi}, \qquad \mathbf{\pi} = (\pi_0, \pi_1, \cdots), \qquad \sum_{j=0}^{\infty} \pi_j = 1}$$

時間が経過しても確率分布が変化しない場合，その分布を定常分布という

$$\mathbf{\pi} P = \mathbf{\pi} \quad \leftrightarrow \quad \sum_{i=0}^{\infty} \pi_i p_{ij} = \pi_j, \quad j = 0, 1, 2, \cdots$$

この方程式の解 $\pi$ をマルコフ連鎖の定常分布という

確率分布 $\pi$ が存在するための必要十分条件はマルコフ連鎖が再帰的で正状態であること

既約なマルコフ連鎖のすべての状態は再帰的な正状態、再帰的な零状態、一時的のいずれかである

既約な有限マルコフ連鎖は再帰的な正状態

例題2.6

$$\pi \mathbf{P} = \pi$$

を解くと

$$\pi = (\frac{19}{85}, \frac{48}{85}, \frac{18}{85})$$

设 $\pi = (a, b, c)$ 计算即可，注意 $a + b + c = 1$

吸収マルコフ連鎖

吸収マルコフ連鎖：状態空間が一時的もしくは吸収的な状態からなるマルコフ連鎖

$k$ 個の吸収状態，$n - k$ 個の一時状態がある吸収マルコフ連鎖

$$\begin{aligned} \color{blue}{\mathbf{P} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{R} & \mathbf{Q} \end{pmatrix}} \end{aligned}$$

• $\mathbf{I}$：$k \times k$ の単位行列
• $\mathbf{R}$：一時状態から吸収状態への推移に関する $(n - k) \times k$ 行列
• $\mathbf{Q}$：一時状態から一時状態への推移に関する $(n - k) \times (n - k)$ 行列
• $\mathbf{0}$：ゼロ行列

$$\begin{aligned} \mathbf{P}^n = \begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{R}_n & \mathbf{Q}^n \end{pmatrix} \end{aligned}$$

ただし、

$$\begin{aligned} \mathbf{R}_n &= (\mathbf{I} + \mathbf{Q} + \cdots + \mathbf{Q}^{n-1}) \mathbf{R} \\ &= (\mathbf{I} - \mathbf{Q}^n) (\mathbf{I} - \mathbf{Q})^{-1} \mathbf{R} \end{aligned}$$

$\mathbf{Q}$ は非負行列で，行の和は1以下であるため、$\lim_{n \rightarrow \infty} \mathbf{Q}^n = 0$ より

$$\lim_{n \rightarrow \infty} \mathbf{R}_n = (\mathbf{I} - \mathbf{Q})^{-1} \mathbf{R} = \mathbf{MR}$$

$$\begin{aligned} \color{blue}{\mathbf{P}^{\infty} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{MR} & \mathbf{0} \end{pmatrix}} \end{aligned}$$

• $\mathbf{M}$：基本行列
• $\mathbf{MR}$：吸収確率

状態 $i, j$ が一時状態の時、$i$ から出発して吸収状態に達するまでの間に $j$ を訪問する平均回数を $m_{ij}$ とする

$m_{ij}$ は，一時状態 $i$ から出発して吸収状態に達するまでに平均何時間（何段階）を一時状態 $j$ で過ごすかを表している

$$m_{ij} = \delta_{ij} + \sum_t p_{it} m_{tj}$$

状態 $i$ から一段階で吸収状態に達するか、途中の一時状態 $t$ を経て最終的に吸収状態に達するかのどちらか

$\mathbf{M} = (m_{ij})$ と置いて上式を行列で表せば、平均滞在時間(平均訪問回数)の行列 $\mathbf{M}$ は次式で表される

$$\mathbf{M} = \mathbf{I} + \mathbf{QM} \quad \leftrightarrow \quad \color{blue}{\mathbf{M} = (\mathbf{I} - \mathbf{Q})^{-1}}$$

例題2.7

吸収マルコフ連鎖

先按照吸収マルコフ連鎖定义将推移矩阵分为4部分，并通过 $\mathbf{M} = (\mathbf{I} - \mathbf{Q})^{-1}$ 求解 $\mathbf{M}$ 和 $\mathbf{MR}$

与单位矩阵同一列的矩阵是表示从一时状态到吸收状态

从一时状态到吸收状态所需平均时间看矩阵 $\mathbf{M}$。例如状态2到吸收状态的平均时间记为矩阵 $\mathbf{M}$ 中表示状态2的那一行加起来即可

到吸收状态的概率看吸收概率矩阵 $\mathbf{MR}$

1次元ランダム・ウォーク

数直線上を確率 $p$ で右へ1だけ移動するか，確率 $q = 1 - p$ で左へ1だけ移動する粒子の運動

状態 $i$ から状態 $i$ に戻る推移確率を考える

• 奇数ステップ $(2n - 1)$ で戻る確率：$p_{ii}^{(2n - 1)} = 0, \quad n = 1, 2, \cdots$
• 偶数ステップ $(2n)$ で戻る確率：$p_{ii}^{(2n)} = \frac{(2n)!}{n!n!} (p(1 - p))^n$

スターリングの公式

$$n! \simeq \sqrt{2\pi n}(\frac{n}{e})^n$$

より、$p = \frac{1}{2}$ の時

$$\sum_{n=1}^{\infty}p_{ii}^{(2n)} = \sum_{n=1}^{\infty} \frac{(4p (1 - p))^n}{\sqrt{\pi n}} = \sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} > \frac{1}{\sqrt{\pi}} \sum_{n=1}^{\infty}\frac{1}{n} = \infty$$

よって，再帰的

$p \neq \frac{1}{2}$ の時、$r = 4p(-1p), (|r| < 1)$ と置くと

$$\sum_{n=1}^{\infty}p_{ii}^{(2n)} = \sum_{n=1}^{\infty} \frac{r^n}{\sqrt{\pi n}} < \frac{1}{\sqrt{\pi}} \sum_{n=1}^{\infty} r^n = \frac{1}{\sqrt{\pi}} \frac{r}{1 - r} < \infty$$

よって，一時的

左右等確率で移動する場合を、1次元の対称なランダム・ウォークという

1次元と2次元の対称な $(p = 1/2)$ ランダム・ウォークは再帰的、3次元以上の対称なランダム・ウォークは一時的である

• 原点回りをうろつくよりも、一方の側に偏っていることが多い。原因：原点右側にいる割合を $x$，左側にいる割合を $1 - x$ とすると、その確率密度関数 $f(x)$ は $f(x) = \frac{1}{\pi \sqrt{x(1 - x)}}$ となることが知られている(逆正弦法則)

例題2.8

$$\begin{aligned} \mathbf{P} = \begin{pmatrix} \frac{3}{10} & \frac{7}{10} \\\\ \frac{2}{3} & \frac{1}{3} \end{pmatrix} \end{aligned}$$

定常分布：$\pi \mathbf{P} = \pi$

例題2.9

ポアソン過程

泊松过程是一种典型的独立增量过程，它具有连续参数 $t$ 与分离散状态取值，因而也是连续参数马尔科夫链。在通信，交通，日常零售业务等各个领域的研究中，泊松过程是各类问题建模时最常用的一种输入模型

e-mailの着信数，交通事故の発生数，新築の住宅数，外国人の流入数，機械の修理数，サービス窓口の行列人数などの事象を考える

$t = 0$ で観測を始め，時間 $t$ までに起こる発生数を $N(t)$ とすると、$N(t)$ はどのような性質を持つ？

時間10までに起こる交通事故の発生数 $N(10)$ は、時間10と15の間に起こる交通事故の発生数 $N(15) - N(10)$ とは無関係

独立増分：互いに排反な時間区分に起こる事象の発生数が独立

$N(15) - N(10)$ は時間の幅 $15 - 10 = 5$ のみにより定まる確率変数

定常増分：時間 $s$ と $t(s < t)$ の間に起こる事象の発生数の分布が時間の幅 $(t - s)$ のみに依存して決まる

ポアソン過程の定義

連続時間 $t \geq 0$ で離散値 $\lbrace i; i = 0, 1, 2, \cdots \rbrace$ を取るマルコフ過程のうち、次のような性質を持つものをポアソン過程という

1. $N(0) = 0$
2. $N(t)$ は定常独立増分を持つ
3. 十分小さい時間の幅 $h$ に対して，$P(N(h) = 1) = \lambda h + o(h)$．ただし $\lambda > 0$
4. 十分小さい時間の幅 $h$ に対して，$P(N(h) \geq 2) = o(h)$

ここで，$\lim_{h \rightarrow 0} = \frac{f(h)}{h} = 0$ が成り立つとき，$f(h) = o(h)$ と表す $h$ が十分小さいとき，$o(h)$ は無視できる

$$\begin{aligned} &P(N(h) = 1) \simeq \lambda h \\ &P(N(h) \geq 2) \simeq 0 \end{aligned}$$

ポアソン過程の性質

1. 観測開始時点 $t = 0$ では事象の発生はない
2. $t_0 < t_1 < \cdots < t_n$ の時，確率変数 $N(t_i) - N(t_{i - 1})$ と $N(t_j) - N(t_{j - 1})$ は独立 $(i \neq j)$ (独立増分)
3. 確率変数 $N(t_2 + h) - N(t_1 + h)$ と $N(t_2) - N(t_1)$ は，任意の $h > 0$ に対し同じ分布を持つ(定常増分)
4. 十分小さい時間幅 $h$ の間に発生する事象の数が1回である確率は $h$ に比例
5. $h$ の間に発生する事象の数が2回以上発生する確率は0
6. $h$ の間に事象が発生しない確率は $1 - \lambda h$

$y = N(t)$ は，高さ1で飛躍する階段状の関数となる．$\tau_i$ は確率変数である

ポアソン分布

時間 $t$ 内に事象が $k$ 個発生する確率 $P_k(t)$

$N(t)$ は平均 $\lambda t$ のポアソン分布をしている

$$\color{blue}{P_k(t) = e^{-\lambda t} \frac{(\lambda t)^k}{k!}, k = 0, 1, 2, \cdots}$$

• $E[N(t)] = V[N(t)] = \lambda t$

例題3.1

事象の発生確率–ポアソン分布

アクセス数は $\lambda = 0.5$ のポアソン過程をなすと考える

$$\color{blue}{P_k(t) = e^{-\lambda t} \frac{(\lambda t)^k}{k!}, k = 0, 1, 2, \cdots}$$

(1) 丁度3

$$P_3(2) = e^{-1} \frac{1}{3!} = 0.0613$$

(2) 3以下

$$P_0(2) + P_1(2) + P_2(2) + P_3(2) = e^{-1} (1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!}) = 0.981$$

(3) 3以上

$$1 - (P_0(2) + P_1(2) + P_2(2)) = 1 - 0.9197 = 0.0803$$

事象の発生時間間隔の分布

発生時間間隔 $T_i$ は独立，かつ，パラメータ $\lambda$ の指数分布に従う

$$E[T_i] = \frac{1}{\lambda}, \quad V[T_i] = \frac{1}{\lambda^2}$$

$$P(T_i > t) = e^{-\lambda t}$$

指数分布の無記憶性

$$P(X > t + s \ |\ X > s) = P(X > t)$$

を満たす確率分布は指数分布のみ

事象の発生確率がポアソン分布、事象の発生時間間隔は指数分布

例題3.2

事象の発生時間間隔–指数分布

$$\color{blue}{P(T_i > t) = e^{-\lambda t}}$$

(1) 2分以上

$$P(T \geq 2) = 1 - P(T < 2) = 1 - (1 - e^{-1}) = 0.3679$$

(2) 4分以内

$$P(T \leq 4) = 1 - P(T > 4) = 1 - e^{-2} = 0.8647$$

n番目の事象が起こるまで時間 $S_n$ が従う分布

$S_n$ はパラメータ $n, \lambda$ のガンマ分布 $g_{n, \lambda}$ に従う

$$g_{n, \lambda}(t) = \lambda e^{-\lambda t} \frac{(\lambda t)^{n-1}}{(n - 1)!}, \quad t \geq 0$$

$$E[S_n] = \frac{n}{\lambda}, \quad V[S_n] = \frac{n}{\lambda^2}$$

例題3.3

(1) $E[S_n] = \frac{n}{\lambda}$ より

$$E[S_{100}] = \frac{100}{1} = 100$$

(2) $P(T_i > t) = e^{-\lambda t}$ より

$$P(T_{101} > 2) = e^{-\lambda t} = e^{-2} = 0.1353$$

(3) $P_k(t) = e^{-\lambda t} \frac{(\lambda t)^k}{k!}, k = 0, 1, 2, \cdots$ より

$$P(N(6) = 0) = P_0(6) = e^{-6} = 0.0025$$

例題3.4

[1] ポアソン分布

(1)

$$P_n(t) = e^{-\lambda t} \cdot \frac{(\lambda t)^n}{n!}$$

(2)

$$P_0(T) = e^{-\lambda t}$$

[2] 一時間あたり受け取るメール数は $\lambda = \frac{48}{24} = 2$

(1) 事象の発生確率がポアソン分布に従う。

$$P_3(6) = e^{-2 * 6} \cdot \frac{(2 * 6)^3}{3!} = 0.00177$$

(2) 事象の発生時間間隔は指数分布に従う。$P(T_i > t) = e^{-\lambda t}$ より

$$P(T \geq 2) = e^{-2 * 2} = 0.01832$$

(3) 事象の発生確率がポアソン分布に従う。$E[N(t)] = V[N(t)] = \lambda t$ より

$$E[N(t)] = \lambda t = E[N(3)] = 2 * 3 = 6$$

純出生過程

ポアソン過程の最も簡単な拡張を考える

• 独立性の仮定の除外
• 時間 $t$ 内に起こる事象の発生数が $j$ (状態 $j$ )のとき、引き続く微小区間で新た1つ発生する確率が $j$ に依存する場合を考える

状態遷移が隣り合う状態だけで起きる

• 純出生過程
• 純死滅過程

に分けて考える

純出生過程

時刻 $t$ で状態 $j$ の時

1. 十分小さい時間幅 $h$ で $j \rightarrow j + 1$ に変わる確率 $\lambda_j h + o(h)$
2. 十分小さい時間幅 $h$ で $j \rightarrow j + 1$ 以外に変わる確率 $o(h)$
3. 変化しない確率 $1 - \lambda_j h + o(h)$

ただし，各 $\lambda_j$ は正数(出生率に相当)

$$\begin{aligned} &P'_j(t) = -\lambda_j P_j(t) + \lambda_{\lambda_{j-1}}P_{j-1}(t), \quad j = 1, 2, \cdots \\ &P'_0(t) = -\lambda_0 P_0(t) \end{aligned}$$

初期条件 $P_0(0) = 1, P_j(0) = 0, j = 1, 2, \cdots$ を用いて，

$$P_0(t) = e^{-\lambda_0 t}$$

となり，$P_1(t), P_2(t)$ を順に求めることができる

ユール・ファーリ過程

$\lambda_j = j \lambda, (\lambda > 0)$ とすると，初期条件

$$\begin{aligned} &P_j(0) = 1, \quad j = 1 \\ &P_j(0) = 0, \quad j \neq 1 \end{aligned}$$

のもとで，$P_j(t)$ は次式で表される．

$$P_j(t) = e^{-\lambda t}(1 - e^{\lambda t})^{j - 1}, \quad j \geq 1$$

$P_0(t) = 0$. 線形出生過程ともいわれる

$$\sum_{j=1}^{\infty} P_j(t) = \sum_{j=1}^{\infty} e^{-\lambda t}(1 - e^{\lambda t})^{j-1} = e^{-\lambda t} \lbrace \frac{1}{1 - (1 - e^{-\lambda t})} \rbrace = 1$$

純死滅過程

時刻 $t$ で状態 $j$ の時

1. 十分小さい時間幅 $h$ で $j \rightarrow j - 1$ に変わる確率 $\mu_j h + o(h)$
2. 十分小さい時間幅 $h$ で $j \rightarrow j - 1$ 以外に変わる確率 $o(h)$
3. 変化しない確率 $1 - \mu_j h + o(h)$

ただし，各 $\mu_j$ は正数(死亡率に相当)

$$\begin{aligned} &P'_j(t) = -\mu_j P_j(t) + \mu_{\mu_{j+1}}P_{j+1}(t), \quad j = 1, 2, \cdots \\ &P'_n(t) = -\mu_n P_n(t) \\ &P'_0(t) = \mu_1 P_1(t) \end{aligned}$$

初期条件 $P_n(0) = 1, P_j(0) = 0, j = 1, 2, \cdots$ を用いて，

$$P_n(t) = e^{-\mu_n t}$$

となり，$P_{n-1}(t), P_{n-2}(t), \cdots, P_0(t)$ を順に求めることができる

例題3.5

1. 時刻0は $P_n(0)$ 以外は全部0
2. 通式：$P_j(t) = e^{-\mu t} \cdot \frac{(\mu t)^{n-j}}{(n - j)!}, \quad j = 1, 2, \cdots, n$

出生死滅過程

• 純出生過程では状態数の増加のみが発生
• 純死滅過程では状態数の減少のみが発生

実際のシステムでは，出生と死滅がランダムに発生する場合が多い

時刻 $t$ で状態 $j$ の時

1. 十分小さい時間幅 $h$ で $j \rightarrow j + 1$ に変わる確率 $\lambda_j h + o(h)$
2. 十分小さい時間幅 $h$ で $j \rightarrow j - 1$ に変わる確率 $\mu_j h + o(h)$
3. 隣以外に変わる確率 $o(h)$
4. 変化しない確率 $1 - (\lambda_j + \mu_j) h + o(h)$

時間 $t$ で状態 $j$ にある確率を $P_j(t)$ とおくと，次式を得る

$$\frac{d}{dt}P_j(t) = -(\lambda_j + \mu_j)P_j(t) + \lambda_{j-1}P_{j-1}(t) + \mu_{j+1} P_{j+1}(t)$$

$t = 0$ で状態 $i$ にあるとする．この時，初期条件は

$$\begin{aligned} P_j(0) = \delta_{ij}, \quad \delta_{ij} = \begin{cases} 1, \quad j = i \\ 0, \quad j \neq i \end{cases} \end{aligned}$$

に従う $P_j(t)$ を $P_{i, j}(t)$ とする

$$\begin{aligned} &\frac{d}{dt}P_{i, 0}(t) = -\lambda_0 P_{i, 0}(t) + \mu_1 P_{i, 1}(t) \\\\ &\frac{d}{dt}P_{i, j}(t) = -(\lambda_i + \mu_j)P_{i, j}(t) + \lambda_{j - 1} P_{i, j-1}(t) + \mu_{j+1}P_{i, j+1}(t) \\\\ &P_{i, j}(0) = 1, \quad j = i \\\\ &P_{i, j}(0) = 0, \quad j \neq i \end{aligned}$$

パラメータ $\lbrace \lambda_j > 0, \mu_{j+1} > 0. j = 0, 1, 2, \cdots \rbrace$ の出生死滅過程において，極限の推移確率

$$p_j = \lim_{t \rightarrow \infty} P_{i, j}(t), \quad i, j = 0, 1, 2, \cdots$$

が初期状態 $i$ と独立に存在するための必要十分条件は

$$\sum_{j=0}^{\infty} a_j < \infty, a_j = \frac{\lambda_{j-1} \lambda_{j=2} \cdots \lambda_0}{\mu_j \mu_{j-1} \cdots \mu_1}, \quad a_0 = 1$$

この時，極限の推移確率は次式となる

$$\color{blue}{p_0 = (\sum_{j=0}^{\infty})^{-1}, p_j = a_j p_0}$$

例題3.6

(1) $n$ 番目の事象が起こるまで時間 $S_n$ が従う分布はガンマ分布なので

$$E[S_n] = \frac{n}{\lambda} = E[S_{180}] = \frac{180}{3} = 60[min]$$

(2) $\color{blue}{P(S_n \leq t) = P(N(t) \geq n) = \sum_{j=1}^{\infty} e^{-\lambda t} \frac{(\lambda t)^j}{j!}}$

$$P(S_5 > 2) = 1 - P(S_5 \leq 2) = e^{-6}(1 + 6 + \frac{6^2}{2!} + \frac{6^3}{3!} + \frac{6^4}{4!}) = 0.2851$$

(3) 事象の発生時間間隔–指数分布

$$P(T_4 \leq 0.5) = 1 - P(T_4 \geq 0.5) = 1 - e^{-3 * 0.5} = 0.7769$$

例題3.7

待ち行列

待ち行列理論の発展

• 1838: ポアソン分布 ランダムに発生するイベントの統計分布
• 1900前半: アーランの計算 ポアソン分布を電話の呼び出しが発生する確率に応用し，電話がつながらない確率などを計算（待ち行列理論の始まり）
• 1953: ケンドールの記号 ケンドールの記号を導入し，待ち行列理論を分類・整理
• 1957: ジャクソンによるネットワーク問題の解析 待ち行列理論を組み合わせたネットワークの問題を解析（空港の手続きのようにチェックインで並び，セキュリティ検査で並び，というような引き続き起こる待ち行列モデルの解析）
• 1961: リトルの公式 リトルが待ち行列，待ち時間に関する一般的な公式を導出

待ち行列モデル

待ち行列理論(Queueing Theory)：不確定な需要と供給という両面から待ちができる行列モデルを数学モデルとして扱う

• スーパーのレジ台
  • 到着する客が支払いサービスを受ける
  • サービスが終わると出ていく
  • 順番を待っている次の客がサービスを受ける
• 情報処理センターのスパコン
  • 到着するジョブが処理のサービスを受ける
  • 終わって空きができると次のジョブが処理を受ける

客、ジョブの到着、支払い／処理のサービス時間は偶然に変化する．どのようにシステムを設計する？

• 客：サービスを受けようとする個々の要求
• 窓口：サービスを提供するもの
• 待ち行列：サービス中の客を除いた実際の待ち行列
• システム：サービス中の人も含めた全体の待ち行列

行列が一つでサービス窓口が一つの場合を単一待ち行列という（行列が一つで窓口が複数の場合は複数待ち行列）

ケンドールの記号

• $A$：客はどれくらいの間隔で到着する？
• $B$：サービスの時間はどれくらいばらつく？
• $C$：窓口の数？
• $K$：行列の上限は？

ケンドールの記号: $A/B/C/K$ もしくは $A/B/C(K)$

この表記の場合，

• 母集団（システムに来る客の数）は $\infty (= m)$
• 待ち行列のルールは先着順(First Come, First Served) $(= Z)$

全て書き出す場合は，

$$A/B/C/K/m/Z$$

と表される

客の到着(A)/サービス時間(B)

ポアソン到着（記号：$M$）

• 到着がパラメータ $\lambda$ のポアソン過程に従う
• 到着時間間隔は指数分布に従う

$$F(t) = 1 - e^{-\lambda t}, \quad t > 0$$

一定分布（記号：$D$）

• 到着間隔が $t = \lambda$ で一定

$$\begin{aligned} F(t) = \begin{cases} 0, \quad t \leq \frac{1}{\lambda} \\ 1, \quad t \geq \frac{1}{\lambda} \end{cases} \end{aligned}$$

一般分布(記号：$G$)

• 到着間隔は独立で同一の分布 $F(t)$ に従う

単一待ち行列モデル

M/M/1(INF)

• 客の到着：パラメータ $\lambda$ のポアソン分布
• サービス時間：パラメータ $\mu$ の指数分布
• 窓口の数：1つ
• 行列の上限：制限なし

客の到着を個体の出生，サービスを受けて退出することを死亡とすると，$M/M$ 型待ち行列モデルは

$$\lambda_i = \lambda, \quad \mu_{i+1} = \mu \quad (i = 0, 1, 2, \cdots)$$

の出生死滅過程で定式化でき，極限の推移確率 $p_j$ を求めることができる

極限の推移確率が存在するための必要十分条件は

$$\sum_{j=0}^{\infty} a_j < \infty, a_j = \frac{\lambda_{j-1} \lambda_{j=2} \cdots \lambda_0}{\mu_j \mu_{j-1} \cdots \mu_1} = (\frac{\lambda}{\mu})^j, \quad a_0 = 1$$

$\rho = \frac{\lambda}{\mu}$ とおくと，$\sum_{j=0}^{\infty} \rho^j < \infty$ であるから，$\rho < 1$ でなければならない．この時，

$$\sum_{j=0}^{\infty}\rho^j = \frac{1}{1 - \rho} < \infty$$

これは，到着率(=出生率) $\lambda$ がサービス率(=死亡率) $\mu$ より小さいときである

$\rho < 1$ の時，極限の推移確率は，

$$p_j = a_j p_0 = \rho^j p_0, \quad p_0 = (\sum_{j=0}^{\infty} a_j)^{-1} = (\sum_{j=0}^{\infty} \rho^j)^{-1} = 1 - \rho$$

これはシステム内に $j$ 人の客(1人のサービス中の客 $+ (j - 1)$ 人の待ち行列の客)がいる確率を表している．ここで，

$$\color{blue}{\rho = \frac{\lambda}{\mu} = \frac{\text{到着率}}{\text{サービス率}} = \frac{1/\mu}{1/\lambda} = \frac{\text{平均サービス時間}}{\text{平均到着時間間隔}}}$$

はトラフィック密度もしくは利用率と呼ばれる

システム内のいる客の平均値および分散は，

$$\color{blue}{L = E(X) = \sum_{j=0}^{\infty} j \times p_j = \frac{\rho}{1 - \rho}}$$

$$\color{blue}{\text{Var}(X) = E(X^2) - E(X)^2 = \frac{\rho}{(1 - \rho)^2}}$$

待ち行列の平均の長さは，サービス中の客を除いた平均の待ち行列の長さであるから，

$$\color{blue}{L_q = \sum_{j=1}^{\infty} (j - 1) \times p_j = L - (1 - p_0) = L - \rho = \frac{\rho^2}{1 - \rho}}$$

リトルの公式

待ち人数 = 待ち時間 $\times$ 到着率

システム内の客の平均待ち時間を $W$，待ち行列での客の平均待ち時間を $W_q$ とすると，

$$\begin{aligned} &L = \lambda W \\ &L_q = \lambda W_q \end{aligned}$$

が成り立つ．したがって

$$\begin{aligned} &\color{blue}{W = \frac{1}{\lambda}L = \frac{1}{\mu(1 - \rho)} \quad \text{（平均系内時間）}} \\ &\color{blue}{W_q = \frac{1}{\lambda}L_q = \frac{\rho}{\mu(1 - \rho)} \quad \text{（平均待ち時間）}} \end{aligned}$$

待ち行列で用いられる特性値

注：7的待ち行列での客の平均待ち時間为 $W_q$

M/M/1(N)

パラメータ $\lambda_i = \lambda, \mu_{i+1} = \mu$，有限状態 $i = 0, 1, \cdots, N$ からなる出生死滅過程を考える．

$j = 1, 2, \cdots, N - 1$ においては，

$$\begin{aligned} &\frac{d}{dt}P_{i, 0}(t) = -\lambda P_{i, 0}(t) + \mu P_{i, 1}(t) \\\\ &\frac{d}{dt}P_{i, j}(t) = -(\lambda + \mu)P_{i, j}(t) + \lambda P_{i, j-1}(t) + \mu P_{i, j+1}(t) \\\\ &P_{i, j}(0) = 1, \quad j = i \\\\ &P_{i, j}(0) = 0, \quad j \neq i \end{aligned}$$

が成り立つ．$j = N$ における境界条件を考えると

$$\color{blue}{\frac{d}{dt}P_{i, N}(t) = \lambda P_{i, N-1}(t) - \mu P_{i, N}(t)}$$

が成り立つ．

出生死滅過程の極限の推移行列が存在するための条件は，

$$\sum_{j=0}^{\infty} a_j < \infty, a_j = \frac{\lambda_{j-1} \lambda_{j=2} \cdots \lambda_0}{\mu_j \mu_{j-1} \cdots \mu_1} = (\frac{\lambda}{\mu})^j, \quad a_0 = 1$$

であるが，有限状態の出生死滅過程では常に満足することが明らか $\sum_{j=0}^N a_j < \infty$ である．従って，

$$\color{blue}{p_j = \rho^j p_0}$$

ただし，

$$p_0 + p_1 + \cdots + p_N = \sum_{j=0}^N p_j = 1$$

需要注意的是，与 $M/M/1(\infty)$ 不同的是，$M/M/1(N)$ 并没有 $\rho < 1$ 的条件

$\rho = 1$ の時，

$$p_0 (1 + N) = 1 \quad \leftrightarrow \quad p_0 = \frac{1}{1 + N}$$

$\rho \neq 1$ の時，

$$p_0(1 + \rho + \cdots + \rho^N) = \rho(\frac{1 - \rho^{N+1}}{1 - \rho}) = 1 \quad \leftrightarrow \quad p_0 = \frac{1 - \rho}{1 - \rho^{N+1}}$$

よって

$$\begin{aligned} p_j = \begin{cases} \frac{1}{1 + N}, \quad &\rho = 1 \\\\ \frac{1 - \rho}{1 - \rho^{N+1}} \rho^j, \quad &\rho \neq 1 \end{cases} \end{aligned}$$

$$\color{blue}{p_N = \frac{1 - \rho}{1 - \rho^{N+1}} \rho^N} \quad \text{呼損率(棄損率)}$$

システム内にいる客の平均値は $\rho \neq 1$ に対して，

$$\color{blue}{L = \sum_{j=0}^N j \times p_j = \frac{\rho}{1 - \rho} \frac{1 - (N + 1)\rho^N + N\rho^{N+1}}{1 - \rho^{N+1}}}$$

$\rho$ が十分小さく $\rho^N \simeq 0, \rho^{N+1} \simeq 0$ とできる場合は，

$$L = \frac{\rho}{1 - \rho} \frac{1 - (N + 1)0 + N0}{1 - 0}$$

となり近似的に $M/M/1(\infty)$ モデルの $L$ と同じになる．

待ち行列の平均長さは，

$$\color{blue}{L_q = \sum_{j=1}^N (j - 1) \times p_j = \frac{\rho^2}{1 - \rho} \frac{1 - N\rho^{N-1} + (N - 1) \rho^N}{1 - \rho^{N+1}}}$$

$\rho = 1$ に対しては，

$$\color{blue}{L = \sum_{j=0}^N j \times p_j = \frac{1}{1 + N} \frac{N(N+1)}{2} = \frac{N}{2}}$$

$$\color{blue}{L_q = \sum_{j=1}^N (j - 1) \times p_j = L - (1 - p_0) = \frac{N(N - 1)}{2(N + 1)}}$$

$M/M/1(N)$ 待ち行列モデルでもリトルの公式は成り立つ．ただし，システムに $N$ 人の客がいるとき，新たに待ち行列に加わることができないため，実質到着率 $\lambda_a$ は

$$\lambda_a = \sum_{j=0}^{N-1} p_j \lambda = (1 - P_N)\lambda = \frac{1 - \rho^N}{1 - \rho^{N+1} \lambda}, \quad \rho \neq 1$$

システム内の客の平均待ち時間を $W$，待ち行列での客の平均待ち時間を $W_q$ とすると，

$$\begin{aligned} &\color{blue}{W = \frac{1}{\lambda_a}L = \frac{1}{\mu(1 - \rho)} \frac{1 - (N + 1)\rho^N + N\rho^{N+1}}{1 - \rho^N} \quad \text{（平均系内時間）}} \\\\ &\color{blue}{W_q = \frac{1}{\lambda_a}L_q = \frac{\rho}{\mu(1 - \rho)} \frac{1 - N\rho^{N-1} + (N - 1)\rho^N}{1 - \rho^N} \quad \text{（平均待ち時間）}} \end{aligned}$$

例題4.1

複数待ち行列モデル

M/M/s(INF)

• 客の到着：パラメータ $\lambda$ のポアソン分布
• サービス時間：パラメータ $\mu$ の指数分布
• 窓口の数：$s(s = 2, 3, \cdots)$
• 行列の上限：制限なし

サービス率 $\mu_k$ は，窓口の数によって異なる．システム内に $k$ 人の客がいた場合，

$$\begin{aligned} \mu_k = \begin{cases} &k\mu, \quad k \leq s \\ &s\mu, \quad k > s \end{cases} \end{aligned}$$

となり，客の数が窓口数よりも多いか少ないかでサービス率が異なる

極限の推移確率が存在するための必要十分条件は

$$\sum_{j=0}^{\infty} a_j = \sum_{j=0}^{\infty} \prod_{k=1}^j \frac{\lambda_{k-1}}{\mu_k} = \sum_{j=0}^{s - 1} \frac{u^j}{j!} + \frac{u^s}{s!} \sum_{n=0}^{\infty} \rho^n < \infty, \quad \color{blue}{u = \frac{\lambda}{\mu}, \rho = \frac{\lambda}{s\mu}}$$

であるから，$\rho < 1$ でなければならない．この時，極限の推移確率は，

$$\begin{aligned} p_j = \begin{cases} &\frac{u^j}{j!}p_0, \quad j \leq s \\\\ &\frac{u^s}{s!} (\frac{u}{s})^{j-s}p_0, \quad j > s \end{cases} \end{aligned}$$

$$\color{blue}{p_0 = [\sum_{j=0}^{s-1} \frac{u^j}{j!} + \frac{u^s}{s!(1 - \rho)}]^{-1}}$$

待ち行列の平均の長さ $L_q$ は，窓口の個数が $s$ であるから，

$$\color{blue}{L_q = \sum_{j=s}^{\infty} (j - s)p_j = p_0 \frac{u^s}{s!}(0 + 1\rho + 2\rho^2 + \cdots) = \frac{p_0 u^s \rho}{s!(1 - \rho)^2}}$$

システム内にいる客の平均値 $L$ は

$$\color{blue}{L = \sum_{j=0}^{\infty} jp_j = \sum_{j=0}^{s-1} \frac{u^j}{j!} p_0 + \sum_{j=s}^{\infty} \frac{u^s}{s!} (\frac{u}{s})^{j-s} p_0 = u + L_q}$$

実質到着率 $\sum_{k=0}^{\infty} \lambda_k p_k = \lambda$ より，リトルの公式から

$$\begin{aligned} &\color{blue}{W = \frac{1}{\lambda}L \quad \text{（平均系内時間）}} \\ &\color{blue}{W_q = \frac{1}{\lambda}L_q \quad \text{（平均待ち時間）}} \end{aligned}$$

M/M/s(N)

• 客の到着：パラメータ $\lambda$ のポアソン分布
• サービス時間：パラメータ $\mu$ の指数分布
• 窓口の数：$s(s = 2, 3, \cdots)$
• 行列の上限：$N - s$

$1 \leq j < s$ のとき

$$\color{blue}{p_j = \frac{u^j}{j!} p_0, u = \frac{\lambda}{\mu}}$$

$s \leq j \leq N$ のとき

$$\color{blue}{p_j = \frac{u^s}{s!} (\frac{u}{s})^{j-s} p_0}$$

$$\color{blue}{p_0 = [\sum_{j=0}^{s-1} \frac{u^j}{j!} + \frac{u^s}{s!}(\frac{1 - \rho^{N-s+1}}{(1 - \rho)})]^{-1}}$$

待ち行列の平均の長さ $L_q$ は，窓口の個数が $s$ であるから，

$$\color{blue}{L_q = \sum_{j=s}^{\infty} (j - s)p_j = \frac{u^s}{s!} \frac{\rho}{(1 - \rho)^2} p_0 \lbrace 1 - [(N - s) (1 - \rho) + 1] \rho^{N - s} \rbrace}$$

システム内にいる客の平均値 $L$ は，

$$\color{blue}{L = \sum_{j=0}^{\infty} jp_j = L_q + \frac{\lambda P_N}{\mu}}$$

リトルの公式から

$$\begin{aligned} &\color{blue}{W = \frac{1}{\lambda}L \quad \text{（平均系内時間）}} \\ &\color{blue}{W_q = \frac{1}{\lambda}L_q \quad \text{（平均待ち時間）}} \end{aligned}$$

例題4.2

例題4.3

平均サービス率を固定して，平均到着率を変化させる. $\rho$ が大きくなるにつれて待ち行列は長くなる．特に0.9を超えると急激に増加する

例題4.4

乱数

エージェントモデルシミュレーション

参考

• 马尔可夫链模型是什么？
• 【数学之路】应用随机过程(马尔可夫链 上)