17 出生死滅過程

出生死滅過程では，時刻 \(t\) における生物集団の個体数を \(X_t\) で表す．これを状態（state）とも呼ぶ．状態 \(X_t\) は状態空間 \(\{0, 1, 2, \ldots\}\) 上に値をとる．状態遷移（state transition）は，個体の出生または死滅によって引き起こされる．出生死滅過程では，状態遷移は隣接する状態間でのみ発生する．状態 \(n\) から状態 \(n+1\) に遷移する確率を \(\lambda_n\)，状態 \(n \geq 1\) から状態 \(n-1\) に遷移する確率を \(\mu_n\) と表す．すなわち，

\[ \lambda_n = P(X_{t+1} = n+1 | X_t = n), \] \[ \mu_n = P(X_{t+1} = n-1 | X_t = n). \]

出生死滅過程の遷移確率図は以下に示す．

出生死滅過程とマルコフ連鎖

出生死滅過程はマルコフ連鎖の一種である．

17.1 定常状態

時刻 \(t\) においてに，状態 \(n\) に入る回数を \(E_n(t)\)，状態 \(n\) を出る回数を \(L_n(t)\) と表すとき， \[ |E_n(t) - L_n(t)| \leq 1 \] が成り立つ．これを \(t\) で割ると， \[ \left| \frac{E_n(t)}{t} - \frac{L_n(t)}{t} \right| \leq \frac{1}{t} \] となる．\(t \to \infty\) としたとき，

\[ \lim_{t \to \infty} \frac{E_n(t)}{t} - \lim_{t \to \infty} \frac{L_n(t)}{t} = 0 \] が得られる．すなわち，\(t \to \infty\) としたとき，状態 \(n\) に入る遷移率と状態 \(n\) を出る遷移率は等しい．

システムが状態 \(n\) に滞在する確率（あるいは，時間比）を \(\pi_n\) と表すとき，

\[\begin{align*} \pi_0 \lambda_0 & = \pi_1 \mu_1 \\ \pi_1 (\lambda_1 + \mu_1) & = \pi_0 \lambda_0 + \pi_2 \mu_2 \\ \pi_2 (\lambda_2 + \mu_2) & = \pi_1 \lambda_1 + \pi_3 \mu_3 \\ & \vdots \end{align*}\]

が成り立つ．これらの式は，一般に次のようにまとめられる．

\[\begin{align*} \pi_0 \lambda_0 & = \pi_1 \mu_1 & \\ \pi_n (\lambda_n + \mu_n) & = \pi_{i-1} \lambda_{i-1} + \pi_{i+1} \mu_{i+1} & (i = 1, 2, \ldots) \end{align*}\]

これらの方程式を大域平衡方程式（global balance equation）と呼ぶ．

さらに，\(\pi_0 \lambda_0 = \pi_1 \mu_1\) を \(\pi_1 (\lambda_1 + \mu_1) = \pi_0 \lambda_0 + \pi_2 \mu_2\) に代入して整理すると，\(\pi_1 \lambda_1 = \pi_2 \mu_2\) が得られる．同様にして，他の状態についてもこのような変形を行うと，一般に，

\[ \pi_n \lambda_n = \pi_{n+1} \mu_{n+1}, \quad (n = 0, 1, 2, \ldots) \] が得られる．これらの方程式を局所平衡方程式（local balance equation）と呼ぶ．

局所平衡方程式より，\(\pi_0\) を用いて，\(n \geq 1\) に対して，

\[ \pi_n = \pi_0 \frac{\lambda_0 \lambda_1 \cdots \lambda_{n-1}}{\mu_1 \mu_2 \cdots \mu_n}, \quad (n = 1, 2, \ldots) \]

が得られる．また，\(\sum_{n=0}^{\infty} \pi_n = 1\) であるから，

\[ \pi_0 + \sum_{n=1}^{\infty} \pi_0 \frac{\lambda_0 \lambda_1 \cdots \lambda_{n-1}}{\mu_1 \mu_2 \cdots \mu_n} = 1 \] となる．これにより，\(\pi_0\) は次のように与えられる．

\[ \pi_0 = \left( 1 + \sum_{n=1}^{\infty} \frac{\lambda_0 \lambda_1 \cdots \lambda_{n-1}}{\mu_1 \mu_2 \cdots \mu_n} \right)^{-1} \]

17.2 評価指標

出生死滅過程に基づいた待ち行列モデルにおいて，状態はシステム内の客数を表す．\(\pi_n\) は，システム内に \(n\) 人の客が存在する確率を表す．平均系内客数 \(\mathbb{E}(L)\)，平均待ち行列長 \(\mathbb{E}(L_q)\) は，それぞれ次のように与えられる．

\[ \mathbb{E}[L] = \sum_{n=0}^{\infty} n \pi_n, \quad \mathbb{E}[L_q] = \sum_{n=c}^{\infty} (n - c) \pi_n. \]

平均滞在時間 \(\mathbb{E}[W]\)，平均待ち時間 \(\mathbb{E}[W_q]\) は，リトルの法則により，次のように与えられる． \[ \mathbb{E}[W] = \frac{\mathbb{E}[L]}{\bar{\lambda}}, \quad \mathbb{E}[W_q] = \frac{\mathbb{E}[L_q]}{\bar{\lambda}}, \]

ここで，\(\bar{\lambda}\) は平均到着率であり， \[ \bar{\lambda} = \sum_{n=0}^{\infty} \lambda_n \pi_n \] で与えられる．

17.3 \(M/M/1\) モデル

\(M/M/1\) モデルを考える．到着間隔が指数分布に従い，平均到着率が \(\lambda\) である．サービス時間も指数分布に従い，平均サービス率が \(\mu\) である．サーバ数は1である．

\(M/M/1\) モデルを出生死滅過程として表すと，すべての状態において，出生率が \(\lambda\)，死滅率が \(\mu\) となる．すなわち，\(M/M/1\) モデルは \(n \geq 0\) に対して，\(\lambda_n = \lambda\)，\(\mu_n = \mu\) で表される出生死滅過程である．

17.3.1 \(M/M/1\) モデルの定常状態

\(M/M/1\) モデルにおいて，\(\rho = \lambda / \mu < 1\) のとき，定常状態が存在する．このとき，\(\pi_0\) は \[ \pi_0 = \left( 1 + \sum_{n=1}^{\infty} \frac{\lambda^n}{\mu^n} \right)^{-1} = \left( 1 + \sum_{n=1}^{\infty} \rho^n \right)^{-1} = \left( 1 + \frac{\rho}{1-\rho} \right)^{-1} = 1 - \rho \]

で与えられる．

ヒント

\(|x| < 1\) に対して，次の式が成り立つ．

\[ \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \quad (|x| < 1) \]

これを用いると，

\[ \sum_{n=1}^{\infty} x^n = \sum_{n=0}^{\infty} x^n - 1 = \frac{1}{1-x} - 1 = \frac{x}{1-x} \quad (|x| < 1) \]

が得られる．

\(\pi_0\) を用いると，任意の \(n \geq 0\) に対して， \[ \pi_n = \pi_0 \frac{\lambda^n}{\mu^n} = (1 - \rho) \rho^n, \quad (n = 0, 1, 2, \ldots) \] が得られる．

結論として，\(M/M/1\) モデルにおいて，\(\rho = \lambda / \mu < 1\) のとき，\(\pi_n\) は \[ \pi_n = (1 - \rho) \rho^n, \quad (n = 0, 1, 2, \ldots) \] である．

17.3.2 \(M/M/1\) モデルの評価指標

\(M/M/1\) モデルにおける平均系内客数 \(\mathbb{E}[L]\) は次のように計算される．

\[\begin{align*} \mathbb{E}[L] & = \sum_{n=0}^{\infty} n \pi_n \\ & = \sum_{n=0}^{\infty} n (1 - \rho) \rho^n \\ & = (1 - \rho) \sum_{n=0}^{\infty} n \rho^n \\ & = (1 - \rho) \cdot \frac{\rho}{(1 - \rho)^2} \\ & = \frac{\rho}{1 - \rho} \\ & = \frac{\lambda}{\mu - \lambda} \end{align*}\]

ヒント

\(\sum_{n=0}^{\infty} n \rho^n = \frac{\rho}{(1 - \rho)^2}\) の導出を示す．

\[\begin{align*} \sum_{n=0}^{\infty} n x^n & = x + 2x^2 + 3x^3 + \cdots \\ & = x (1 + 2x + 3x^2 + \cdots) \\ & = x \sum_{n=1}^{\infty} n x^{n-1} \\ & = x \sum_{n=1}^{\infty} \frac{d}{dx} x^n \\ & = x \frac{d}{dx} \sum_{n=1}^{\infty} x^n \\ & = x \frac{d}{dx} \left(\frac{x}{1-x}\right) \\ & = x \cdot \frac{1}{(1-x)^2} \\ & = \frac{x}{(1-x)^2} \end{align*}\]

同様にして，平均待ち行列長 \(\mathbb{E}[L_q]\) は次のように計算される．

\[\begin{align*} \mathbb{E}[L_q] & = \sum_{n=1}^{\infty} (n - 1) \pi_n \\ & = \sum_{n=1}^{\infty} n \pi_n - \sum_{n=1}^{\infty} \pi_n \\ & = \mathbb{E}[L] - (1 - \pi_0) \\ & = \frac{\rho}{1 - \rho} - \rho \\ & = \frac{\rho^2}{1 - \rho} \\ & = \frac{\lambda^2}{\mu (\mu - \lambda)} \end{align*}\]

ヒント

ここでは， \[ \sum_{n=1}^{\infty} n \pi_n = \sum_{n=0}^{\infty} n \pi_n = \mathbb{E}[L] \] および， \[ \sum_{n=1}^{\infty} \pi_n = 1 - \pi_0 = 1 - (1 - \rho) = \rho \] を用いている．

\(M/M/1\) モデルにおける平均滞在時間 \(\mathbb{E}[W]\)，平均待ち時間 \(\mathbb{E}[W_q]\) は，リトルの法則により，次のように与えられる． \[ \mathbb{E}[W] = \frac{\mathbb{E}[L]}{\lambda} = \frac{1}{\mu - \lambda}, \quad \mathbb{E}[W_q] = \frac{\mathbb{E}[L_q]}{\lambda} = \frac{\lambda}{\mu (\mu - \lambda)} \]

\(M/M/1\) モデル

\(M/M/1\) モデルにおいて，\(\rho = \lambda / \mu < 1\) のとき，\(\mathbb{E}[L]\)，\(\mathbb{E}[L_q]\)，\(\mathbb{E}[W]\)，\(\mathbb{E}[W_q]\) はそれぞれ次のように与えられる． \[ \mathbb{E}[L] = \frac{\rho}{1 - \rho} = \frac{\lambda}{\mu - \lambda}, \] \[ \mathbb{E}[L_q] = \frac{\rho^2}{1 - \rho} = \frac{\lambda^2}{\mu (\mu - \lambda)}, \] \[ \mathbb{E}[W] = \frac{1}{\mu - \lambda}, \] \[ \mathbb{E}[W_q] = \frac{\lambda}{\mu (\mu - \lambda)}. \]

下図は，\(M/M/1\) モデルにおける利用率 \(\rho\) と平均系内客数 \(\mathbb{E}[L]\) の関係を示している．

コード

# rho vs L plot for M/M/1 model
import numpy as np
import matplotlib.pyplot as plt

rho = np.linspace(0.01, 0.99, 100)
L = rho / (1 - rho)
plt.plot(rho, L)
plt.ylim(0, 50)
plt.xlim(0, 1.1)
plt.xlabel("Utilization ρ")
plt.ylabel("Average number of customers in system L")
plt.title("M/M/1 Model: Utilization vs Average Number of Customers in System")
plt.grid()
plt.show()

17.3.3 待ち時間分布

客の滞在時間 \(W\) と待ち時間 \(W_q\) の確率分布を分析する．ここで，サービス規律は FCFS （First-Come, First-Served）と仮定する．

\(T_1, T_2, \ldots, T_n\) を，サービス時間を表す確率変数とする．ある客が到着したときに，システム内に \(n\) 人の客が存在するとする．このとき，この客の待ち時間は \[ Y_n = T_1 + T_2 + \cdots + T_n \] であり，滞在時間は \[ Y_{n+1} = T_1 + T_2 + \cdots + T_n + T_{n+1} \] である．

17.4 文献案内

Bertsekas と Tsitsiklis (2008) の「Introduction to Probability」では，確率過程とマルコフ連鎖を含めた確率論の基礎が解説されている．

もっと詳しく待ち行列理論を学びたい場合は，Shortle ほか (2018) の「Fundamentals of Queueing Theory」が参考になる．