M/G/∞ 待ち行列の系内数はポアソン分布に従う性質を１つずつわかりやすく解説！

どうも！初めましての方は初めまして、初心者のWebサイト勉強のとみーです！

待ち行列システムの中で、M/G/∞ 待ち行列の系内数はポアソン分布と密接な関係があります。

M/G/∞ 待ち行列とは－ケンドールの記号の確認

まず、M/G/∞ 待ち行列とは何かを確認しておきましょう。

ケンドールの記号について、詳しくは以下の記事で解説しています。

というケンドールの記号の表記にしたがうと、M/G/∞ 待ち行列は

1. M：到着の確率分布・確率過程
2. G：サービス時間の確率分布
3. ∞：サーバー数

となります。

到着の確率分布 M はマルコフ連鎖を表す

M はマルコフ連鎖を表しますが、ケンドールの記号では

を表します。

また、到着間隔の確率分布が指数分布なら確率過程はポアソン過程となるため、上のような組み合わせとなります。

サービスの確率分布 G は一般分布を表す

G は一般分布を表します。

つまり、特に指定がなくどの分布でもいいということです。

サーバー数が無限とはどういうことか

店舗のレジ待ちの場合、レジ（サーバー）が無限にあるということはありえないため、レジに列を作って並びます。

サーバーが無限にあるというのは、図書館のように並んで待たずに誰でも入れるようなシステムに対応します。

また、会員制のジムなど、収容人数は有限だけど全員が収容できる余裕があり、実質的に待ち時間なくサービスを利用できるシステムや、セルフサービスのシステムも「サーバー数∞」として考えられます。

M/G/∞ 待ち行列のまとめ

以上をまとめて M/G/∞ 待ち行列を整理すると、次のようになります。

M/G/∞ 待ち行列が理解できたら早速ポアソン分布との関係を見ていきましょう。

M/G/∞ 待ち行列の系内数はポアソン分布に従う

M/G/∞ 待ち行列には

という性質があります。

待ち行列の系内数とは

系内数はあまり聞き慣れない言葉ですが、待ち行列においては

を意味します。

サーバー数が無限の状況では列に並んで待つ時間はないので、サービスを利用中の人数と言い換えることもできます。

図書館を例にすると、ある時刻において図書館内にいる人数が系内数ということになります。

M/G/∞ 待ち行列におけるポアソン分布

M/G/∞ 待ち行列では「到着の確率分布が指数分布」であることは上で説明した通りですが、そのほかに「到着の確率分布が指数分布なら到着数はポアソン過程（ポアソン分布）」という性質があります。

その性質と合わせれば、M/G/∞ 待ち行列において

1. 到着数
2. 系内数

の２つがポアソン分布に従うということになります。

また、時間がどれくらい経ったらポアソン分布に従うと見なして良いのでしょうか？

M/G/∞ 待ち行列の系内数はなぜポアソン分布に従うのか

話をわかりやすくするために、ここでは客が来店しセルフサービス形式でサービスを利用する ATM を例に考えましょう。

重要な値を変数で表しましょう。

時刻 $x\in (0,t)$ に到着した客が時刻 $t$ で系内に留まっている確率

上の設定から時刻 $t$ までに $\mathrm{\Lambda }(t)$ 人が到着しますが、ここで

を考えましょう。

上で確認したように、M/G/∞ 待ち行列ではサービス時間（系内に滞在する時間）は一般分布 $G$ に従います。

したがって、サービスが時間 $t$ 以内に終わる確率は $G(t)$ と表されます。

「時刻 $x\in (0,t)$ に到着した客が時刻 $t$ でも系内に留まっている」のは、サービス時間が $t–x$ 以上のときなので、その確率は

となります。

到着時刻の確率分布

ここで、$i$ 番目に到着した人の到着時刻を $Z_i$（$i\in [[1,n]]$） とします。

図にすると次のようになります。

詳しくはこちらの記事で丁寧に解説していますが、ポアソン過程の到着時刻には次のような性質があります。

数式で表せば、$Z=(Z_1,\cdots ,Z_n)$ として

$${\displaystyle f_Z(t_1,\cdots ,t_n|\mathrm{\Lambda }(t)=n)=\frac{n!}{t^n}}$$

ということです。

$\mathrm{\Lambda }(t)=n$ 人の客の到着時刻

$Z_i$ は $i$ 番目の到着時刻を表しますが、$\mathrm{\Lambda }(t)=n$ 人の客の到着順は $n!$ 通り存在します。

よって、客 $j$ が時刻 $t_j$ に到着する確率は上の確率を $n!$ で割った

$${\displaystyle f_X(t_1,\cdots ,t_n|\mathrm{\Lambda }(t)=n)=\frac{1}{t^n}}$$

となります。

客が時刻 $t$ に到着する確率

ある客 $j$ が時刻 $t$ に到着する確率は、上の確率を周辺化することで次のように求められます。

$$\begin{array}{rl}\mathbb{P}(X_j=t_j)& =\int f_X(t_1,\cdots ,t_{j-1},t_{j+1},\cdots ,t_n|\mathrm{\Lambda }(t)=n)d{X}_1\cdots d{X}_{j-1}d{X}_{j+1}\cdots d{X}_n\\ & =\int \frac{1}{t^n}d{X}_1\cdots d{X}_{j-1}d{X}_{j+1}\cdots d{X}_n\\ & =\frac{1}{t^n}{\int }_0^t\cdots {\int }_0^{t}d{X}_1\cdots d{X}_{j-1}d{X}_{j+1}\cdots d{X}_n\\ & =\frac{1}{t}\end{array}$$

つまり、

となります。

客が時刻 $t$ で系内に留まっている確率

以上のことから、ある客が時刻 $t$ で系内に留まっている確率 $p_t$ は次のようになります。

$$\begin{array}{rl}{p}_t& ={\int }_0^t\mathbb{P}(\text{時刻 }x\text{ に到着 かつ 時刻}t\text{ に留まっている})dx\\ & ={\int }_0^t\mathbb{P}(\text{時刻 }t\text{ に留まっている}|\text{時刻 }x\text{ に到着})\mathbb{P}(\text{時刻 }x\text{ に到着})dx\\ & ={\int }_0^t(1–G(t–x))\frac{1}{t}dx\\ & =\frac{1}{t}{\int }_0^t(1–G(t–x))dx\end{array}$$

分布によって $G$ は異なるのでこれ以上計算を進めることはできませんが、ここから $\mathrm{\Lambda }(t)$ 人の客は

の２つに分かれることがわかります。

これは、ポアソン過程の到着をベルヌーイ試行で振り分けることに他なりません。

ポアソン過程の到着をベルヌーイ試行で振り分ける

詳しくはこちらの記事で解説していますが、到着率 $\lambda$ のポアソン過程 $\mathrm{\Lambda }(t)$ を

のように２つのグループに分ける場合、グループ１、２の人数 $Y_1(t),Y_2(t)$ について

が成り立ちます。

この性質を使うと、今回はポアソン過程を確率 $p_t,1–p_t$ で振り分けるので

となります。

したがって、系内数がポアソン分布に従うことが導かれました。

M/G/∞ 待ち行列における系内数の極限分布

最後に $t$ が十分に大きくなった場合の系内数の分布を見てみましょう。

系内数が従うポアソン分布のパラメータの極限

系内数が従うポアソン分布のパラメータ $\lambda t{p}_t$ の極限は

$$\begin{array}{r}\underset{t\to \mathrm{\infty }}{lim}\lambda t{p}_t=\lambda \underset{t\to \mathrm{\infty }}{lim}{\int }_0^t(1–G(t–x))du\end{array}$$

で求められます。

積分については、確率密度関数 $g(u)$ とすると、次のように変形できます。

$$\begin{array}{rl}\underset{t\to \mathrm{\infty }}{lim}{\int }_0^t(1–G(t–x))du& =\underset{t\to \mathrm{\infty }}{lim} {\int }_0^t\mathbb{P}(U\ge u)du\\ & =\underset{t\to \mathrm{\infty }}{lim} {\int }_0^t{\int }_u^{\mathrm{\infty }}g(v)dvdu\\ & =\underset{t\to \mathrm{\infty }}{lim} {\int }_u^{\mathrm{\infty }}{\int }_0^{t}g(v)dudv\\ & =\underset{t\to \mathrm{\infty }}{lim} {\int }_u^{\mathrm{\infty }}{\int }_0^{t}vg(v)dv\\ & =\mathbb{E}[U]\end{array}$$

$U$ はサービス時間を表す確率変数です。

待ち行列のサービス率

サービス時間の期待値の逆数

$$\mu =\frac{1}{\mathbb{E}[U]}$$

はサービス率と呼ばれます。

サービス率 $\mu$ を使うと、系内数が従うポアソン分布のパラメータ $\lambda t{p}_t$ の極限は

と表せます。

つまり、十分時間が経った状態の系内数はパラメータ $\frac{\lambda }{\mu }$ のポアソン分布に従います。

十分時間が経ったかどうかを判断する

「十分時間が経った」かどうかの判断を行う際は、

という事実が一つの基準となります。

$G(u)$ は累積分布関数なので単調増加であり、その値が $1$ に十分近いのであれば $t\ge u$ となる $t$ に対して積分の中身はほぼ $0$ となるからです。

このような $t$ を考える場合は ${\int }_0^t(1–G(t–x))du$ を計算することなく

として考えることができます。

まとめ

今回は、M/G/∞ 待ち行列の系内数についてご紹介しました。