待ち行列５．M/M/1における待ち行列の基本方程式の導出

確率 待ち行列 基本情報処理試験

パラメーター\lambdaのポアソン到着、窓口が1人でパラメーター\muの指数サービスの待ち行列M/M/1において長さjであるとき、この待ち行列は状態E_jにあるという。したがって系は常にE_0,E_1,\cdotsのいずれか1つの状態をとる。時刻tで状態E_jにある確率をP_j(t)で表す。時刻tにおける系の長さをQ(t)とすれば、P_j(t)=P(Q(t)=j)である。

ある時刻t_0で状態E_jにあったとする。その時刻後の系の状態の分布の移り変わりは以下の要因によって決定される。

(1)時刻t_0における系の長さ。

(2)時刻t_0における客のサービス終了時刻。

(3)時刻t_0以降の到着時刻の分布。

(4)時刻t_0以降に到着する客のサービス時間。

ある時刻を0とし、系の長さQ(t),(t \lt 0)を考察する。任意のt,t'\lt 0に対して

P(Q(t+t')=k|Q(t)=j)=P(Q(t')=k|Q(0)=j)である。遷移確率を

\begin{equation}\left\{ \begin{array}{l} P_{i,j}(t)=P(Q(t)=j|Q(0)=i) \\ P_{i,j}(0)=\delta_{i,j} \left\{ \begin{array} {l} 1,(i=j) \\ 0,(i\ne j) \end{array} \right.\end{array} \right. \end{equation}

と表す。i,j のいずれかが負のときはP_{ij}(t)=0とおく。微小な時間区間(t,t+dt)をとるとき1人到着する確率は\lambda dt + o(dt^2)であり、サービス中の客がこの区間内で終了して立ち去る確率は同様に\mu dt + o(dt^2)であるから

\begin{equation}\left\{ \begin{array}{l} P_{i,i+1}(dt)=\lambda dt + o(dt^2) \\P_{i,i-1}(dt)=\mu dt + o(dt^2) \\ P_{i,i}(dt)=1-\lambda(dt)-(1-\delta_{i0})\mu dt + o(dt^2) \\ P_{i,j}(dt)= o(dt^2),(|i-j|\geqq 2) \end{array}\right.\end{equation}

最初の式は時刻tでi人おり、それから微小時間dt後1人増えてi+1 人になる確率であるから、

P(dt\mbox{内でサービスが終了せず1人到着する})

=(1-\mu dt + o(dt^2))(\lambda dt + o(dt^2))= \lambda dt + o(dt^2)

と

\displaystyle{ \sum_{n=1}^\infty P(dt\mbox{内でサービスが}n\mbox{人終了して}n+1\mbox{人到着する})}

\displaystyle{ \leqq \sum_{n=1}^\infty P(dt\mbox{内に}n+1\mbox{人到着する}) = P(dt \mbox{内に2人以上到着する})=o(dt^2)}

の和で得られる。上から2式目も同様である。4式目は自明である。

上から3式目についてはi=0 のとき誰も来ない確率であるから

P_{0,0}(t)=1-\lambda dt + o(dt^2)

i \gt 0のときはdt時間内にn\geq 0としてn人来てn人帰る確率の総和だから、0人来て0人帰る確率は

(1-\lambda dt + o(dt^2))(1-\mu dt  + o (dt^2))=1-\lambda dt -\mu dt + o(dt^2)

1人来て1人帰る確率は

(\lambda dt + o(dt^2))(\mu dt + o(dt^2))=o(dt^2)

2人以上来て同じ人数帰る確率は無視できるから3式目も正しい。

時刻0で系の長さがiなるとき、それから時刻t+dtでjとなる遷移確率P_{ij}(t+dt)は時刻t=0の状態E_iから時刻tで状態E_kに移り、それから時刻t+dtで状態E_jになる互いに排反な事象の確率を加え合わせたものである。さらに時刻tで状態E_kであるとき、時刻t+dtで状態E_jになる遷移確率は時刻t以前の状態に独立であるから、

\displaystyle{P_{i,j}(t+dt) =\sum_{k=0}^\infty P(Q(t+dt)=j,Q(t)=k|Q(0)=i) }

\displaystyle{= \sum_{k=0}^\infty P(Q(t)=k|Q(0)=i)P(Q(t+dt)=j|Q(t)=k)} 

\displaystyle{= \sum_{k=0}^\infty P_{i,k}(t)P_{k,j}(dt)} 

\begin{equation} = \left\{ \begin{array}{ll} P_{i,j-1}(t) \lambda dt + P_{i,j}(t) \{1-(\lambda+\mu)dt\} +P_{i,j+1}(t) \mu dt + o(dt^2) & ,(j \gt 0)\\  P_{i,0}(t) (1-\lambda)dt +P_{i,1}(t) \mu dt + o(dt^2)  & ,(j=0) \end{array} \right.\end{equation}

最後の変形はP_{i,i}(dt),P_{i,i-1}(dt),P_{i,i+1}(dt),P_{i,j}(dt)の式を使った。したがって

\begin{equation} \frac{d P_{i,j}(t)}{dt}= \left\{ \begin{array}{ll}  \lambda P_{i,j-1}(t)+  -(\lambda+\mu) P_{i,j}(t) +\mu P_{i,j+1}(t) & ,(j \gt 0)  \\  -\lambda P_{i,0}(t) +\mu P_{i,1}(t)  &  ,(j=0)\end{array} \right.\end{equation}

以上で待ち行列の基本方程式の導出が終わった。微分方程式の各項の意味はj-1人いるところへ1人来る場合、j人いるところへ1人の増減も無い場合、j+1人いるところから1人減る場合となる。dt時間内では2人以上の変化は無視できるということである。ちなみにt\to \inftyでの極限は方程式の解がベッセル関数を使って解けることから、ベッセル関数の漸近表示を用いて示される。時間があれば後述しようと思います。

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

わかりやすい待ち行列システム 理論と実践 [ 高橋敬隆 ]
価格：3080円（税込、送料無料) (2020/9/9時点)

楽天で購入

 

待ち行列４．ポアソン到着

確率 待ち行列 基本情報処理試験

ポアソン分布に従う到着の定義

条件1．（到着の定常性）相重ならないようにとられた’任意のn個の時間区間I_1,I_2,\cdots,I_nに対して、各区間にk_1人、k_2人、\cdots、k_n人到着する結合確率が時間区間I_iをすべて同一時間ずらしても、その位置に関係なくその区間の長さとそこでの到着数k_iのみによって定まるものとする。この条件から特に1つの時間区間(t_0,t_0+t)をとるときそこにk人到着する確率はt_0に無関係でkと長さtのみに関係する。

条件２．（到着に残留効果がないこと）1つの任意の時間区間(t_0,t_0+t)をとるとき、そこにk人到着する確率はt_0以前のどの時間でどれだけとうちゃくしたかに何の影響も受けない。t_0以前の客の到着のあり方について何か与えられても、そのもとでこの時間区間内にk人到着する条件付確率は条件を外した確率に等しい。

条件３．（到着の整列性）長さtの任意の時間区間内に2人以上到着する確率をP(t,\geqq 2)で表せば

\displaystyle{\frac{P(t,\geqq 2)}{t} \to 0 (t \to 0)}

あるいは同じことであるが、P(t,\geqq 2) = o(t^2) ( t\to 0)が成立すること、この条件は同一時刻に2人以上の客が重なって到着する可能性がないことを意味し、客はある時間はなれて1人ずつ順序良く到着することを意味している。

 

長さ1のある時間区間を考え、この区間内に誰も到着しない確率を\phi =P_0(1)とする。この時間区間をnに等分割すれば上述の時間区間にだれも到着しないということはこれら分割されたn個の区間のどれにも到着がないということと同じであるから条件１．２．によって

\displaystyle{\phi = \left[ P_0 \left( \frac{1}{n} \right)\right]^n}

したがって長さ1/nの時間区間内に誰も到着しない確率は

\displaystyle{ P_0 \left( \frac{1}{n} \right) = \phi^{\frac{1}{n}} }

長さk/nの時間区間内に到着しない確率は

\displaystyle{P_0 \left( \frac{k}{n} \right) = \phi^{\frac{k}{n}} }

である。tを非負の実数、nを自然数として

\displaystyle{\frac{k-1}{n} \leqq t \lt \frac{k}{n} }

なる自然数kを定める。このような自然数の組n,kは無数に存在する。またP_0(t)はtの減少関数である。なぜならt_1 \leqq t_2なるとき、区間(0,t_2)に到着がなければそれに含まれる(0,t_1)には当然到着がないからP_0(t_2) \leqq P_0 (t_1)よって

\displaystyle{P_0 \left( \frac{k-1}{n} \right) \geqq P_0(t) \geqq P_0 \left( \frac{k}{n}\right)}

したがって

\displaystyle{\phi^{\frac{k-1}{n}} \geqq P_0(t) \geqq \phi^{\frac{k}{n}}}

ここで\displaystyle{\lim_{n \to \infty}\frac{k}{n} = \lim_{n \to \infty} \frac{k-1}{n} = t}なるように極限をとると

P_0 (t) = \phi^t

P_0 (t)は確率であるから0 \geqq P_0(t) \geqq 1を満足し、したがって次の3つの場合が考えられる。

(1) \phi =0 (2) \phi = 1 (3) 0 \lt \phi \lt 1

(1)の場合は任意の区間の長さtに対してP_0(t)=0となり、任意の時刻で1人以上の客が到着する確率が1であることに反する。(2)の場合には任意の区間の長さt に対しずっと到着がおこらないことを意味する。(3)の場合にはe^{-\lambda}(\lambdaは正数)とおけるからP_0(t)=e^{-\lambda t}と書ける。

長さtの時間区間に誰も到着しない事象、ただ1人到着する事象および2人以上到着する事象は互いに排反であり、なおかつこれらの事象は全事象であるから、

P_0(t) + P_1(t)+P(t,\geqq 2)=1

これと条件３．から

P_1(t)=1-e^{-\lambda t} + o(t^2) = \lambda t + o(t^2) (t \to 0)

 

長さt+hの時間区間内にちょうどk人到着する確率を求める。これは次のk+1個の排反事象の和事象である。

0)長さtの時間区間内にちょうどk人到着し、残りのhの時間区間内には誰も到着しない。

1)長さtの時間区間内にちょうどk-1人到着し、残りのhの時間区間内には1人到着する。

\vdots

k)長さtの時間区間内にちょうど0人到着し、残りのhの時間区間内にはk人到着する。

したがって

\displaystyle{ P_k(t+h)=\sum_{i=0}^k P_{k-i}(t) P_i(h)=\sum_{i=0}^k P_i(t) P_{k-i}(h)}

P_i (t) \leqq 1 ( i=0,1,\cdots,k-2)であるから

\displaystyle{ \sum_{i=0}^{k-2} P_i(t) P_{k-i}(h) = \sum_{i=0}^{k-2} P_{k-i}(h)= \sum_{i=2}^k P_i (h) = \sum_{i=2}^\infty P_i (h) = o(h^2), (h\to 0) } 

したがって

P_k(t+h) = P_k(t) P_0(h)+P_{k-1}(t)P_1(h)+o(h^2),(h \to 0)

これにP_0(h)=e^{-\lambda h}= 1 - \lambda h + o(h^2)とP_1(h)=\lambda h + o(h^2),(h\to 0)を代入して

P_k(t+h) = P_k(t)(1 - \lambda h)+ P_{k-1}\lambda h + o(h^2)

すなわち

\displaystyle{ \frac{P_k(t+h) - P_k(t)}{h}=-\lambda P_k(t) + \lambda P_{k-1}(t) + o(h)}

ここでh\to 0とすれば

\displaystyle{\frac{d P_k(t)}{dt} = \lambda P_k(t) + \lambda P_{k-1}(t)}

この連立微分方程式を解けば

\displaystyle{ P_k(t) = \frac{(\lambda t)^k}{k!} e^{-\lambda t}}

というパラメーター\lambda tのポアソン分布を得る。

条件１．から条件３．を満たす到着をポアソン到着という。

 

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

待ち行列理論 [ 大石進一 ]
価格：1980円（税込、送料無料) (2020/9/9時点)

楽天で購入

 

待ち行列３．窓口は1つ行列の長さ無制限の場合の平均人数

確率 待ち行列 基本情報処理試験

表題の場合P_nについての基本方程式がそのまま成り立つからすべてのn\geqq 1に対して\displaystyle{P_n = \left( \frac{\lambda}{\mu} \right)^n P_0}が成り立つ。

平均到着率\lambdaと平均サービス率\muに対して\lambda \lt \muという条件をつける。\lambda \geqq \muならば1時間当たり到着する人数の平均値がサービスを終える人数の平均値より大きいから窓口に並ぶ人は増加する一方になるからである。

\displaystyle{\rho =\frac{\lambda}{\mu}}とおけば、P_n = \rho^n P_0であり、\displaystyle{\sum_{n=0}^\infty P_n = 1}であるから、

\displaystyle{\sum_{n=0}^\infty P_n = P_0 \sum_{n=0}^\infty \rho^n = \frac{P_0}{1-\rho} =1}

したがってP_0=1-\rhoこうしてP_n=(1-\rho)\rho^nが得られる。

P_0はサービスステーションに誰もいない確率すなわち窓口が空いている確率だから\rho = 1-P_0は窓口が使われている確率である。その意味で\rhoは平均利用率とも呼ばれる。

ステーションの中にいる平均人数は

\displaystyle{\sum_{n=1}^\infty n P_n =\sum_{n=1}^\infty  n ( 1 - \rho ) \rho^n=(1 - \rho)\rho \sum_{n=1}^\infty n \rho^{n-1}}

\displaystyle{1 + 2 \rho + 3 \rho^2 + \cdots = (1 + \rho + \rho^2+ \cdots)+\rho(1 + \rho+ \rho^2 + \cdots) + \rho^2(1 + \rho +\cdots)}

\displaystyle{=\frac{1}{1-\rho}(1+\rho+\rho^2+\cdots)=\frac{1}{(1-\rho)^2}}

したがってステーションの中にいる平均人数は

\displaystyle{(1-\rho)\rho \frac{1}{( 1 - \rho)^2}=\frac{\rho}{1-\rho}}

で与えられる。


 

待ち行列２．待ち行列の基本方程式

確率 待ち行列 基本情報処理試験

来た人がサービスを受ける場所を窓口とよぶ。1つの窓口でのサービス時間の長さの分布がパラメーター\mu\gt 0の指数分布であると仮定して話を進める。サービス時間の分布の密度関数はg(t)=\mu e^{-\mu t} ,t \gt 0である。すると、出口への到着時間間隔も同じ指数分布になり、このとき出口へ到着した人数の分布はポアソン分布になる。t時間内にn人サービスを終える確率を\Psi_n (t)とすれば、\displaystyle{\Psi_n (t)=\frac{(\mu t)^n}{n!} e^{-\mu t}},t \gt 0となる。\muは単位時間当たりのサービス終了人数（平均サービス率）を与える。これは、

\displaystyle{\frac{d q_n(t)}{dt}=-\mu q_n (t) + \mu q_{n-1} (t),n \geqq 1}

\displaystyle{\frac{d q_0(t)}{dt}=-\mu q_0 (t)}

なる連立微分方程式の解である。これらの関係から、t時点でサービスステーションの中にいる人数をn人とするときの確率をP_n(t)とおくと、

\displaystyle{\frac{d P_0(t)}{dt}=-\lambda P_0(t) + \mu P_1(t)=0}

\displaystyle{\frac{d P_n(t)}{dt}=-(\lambda+\mu)P_n(t) +\lambda P_{n-1}(t) + \mu P_{n+1}(t) ,n\geqq 1}

となる（後述）。解P_n(t)はt\to \inftyのとき極限をもつ。その極限をP_nとする。P_nはtに依存しない定数であるから

-\lambda P_0 + \mu P_1 =0

-(\lambda+\mu)P_n + \lambda P_{n-1} + \mu P_{n+1} =0,n \geqq 1

最初の式は\mu P_1 - \lambda P_0 =0であり、2番目の式は\mu P_{n+1} -\lambda P_n = \mu P_n - \lambda P_{n-1}と変形できる。すべてのn\geqq 1でこの関係式が成り立つから

\mu P_n - \lambda P_{n-1}=\mu P_{n-1} - \lambda P_{n-2}=\cdots =\mu P_1 - \lambda P_0=0

したがって\displaystyle{P_n = \frac{\lambda}{\mu} P_{n-1}=\left( \frac{\lambda}{\mu} \right)^n P_0}が成り立つ。このP_nの関係式を待ち行列論の基本方程式とよぶ。


 

待ち行列１．到着する人数の確率分布と到着間隔の分布

確率 待ち行列 基本情報処理試験

s時点からs+t時点までの間にn人到着する確率は時間間隔tだけの関数であって、sとは無関係である。この確率をtだけの関数としてq_n(t)と書くことにするとパラメーター\lambda tのポアソン分布を満たし、\displaystyle{q_n(t)=\frac{(\lambda t)^n}{n!} e^{-\lambda t}=P_{\lambda t}(n)}と書ける。期待値は\lambda tであり、\lambda tはt時間内に到着する人数の平均値であるから、\lambdaは単位時間あたりの平均到着人数（平均到着率）を表す。この到着のパターンをポアソン到着という。これは、

\displaystyle{\frac{d q_n(t)}{dt}=-\lambda q_n (t) + \lambda q_{n-1} (t),n \geqq 1}

\displaystyle{\frac{d q_0(t)}{dt}=-\lambda q_0 (t)}

なる連立微分方程式の解である。

次にポアソン到着の場合の到着時間間隔の分布を調べてみる。1人到着してから次の人が到着するまでの時間間隔をあらわす確率変数をTとおく。このときT\gt tという事象はt時間以内に1人も到着しないということを意味する。ということはt時間以内の到着人数は0ということと同じであり、その確率はq_n(t)のn=0の場合である。したがってP(T\gt t)=q_0(t)=e^{-\lambda t}となるから、F(t)=P(T \leqq t)=1-e^{-\lambda t}から密度関数\displaystyle{f(t)=\frac{d F(t)}{dt}=\lambda e^{-\lambda t}}となって指数分布となる。t時間以内にn人到着する確率はq_n(t)であるが、この確率はまた区間(0,t)のどこかの時点\tauと\tau+d\tauの間で最初の1人が来て、あとのt-\tau時間の間に残りのn-1人が来るという事象の確率を\tauについて0からtまで積分したものと考えてもよい。こう考えればP(\tau \lt T \leqq \tau +d\tau)=\lambda e^{-\lambda \tau}d \tauであり、t-\tau時間の間にn-1人来る確率はq_n(t-\tau)であるから

\displaystyle{q_n(t)=\int_0^t \lambda e^{-\lambda \tau}q_{n-1}(t-\tau) d\tau}

という関係式が得られる。

\displaystyle{q_1(t)=\int_0^t \lambda e^{-\lambda \tau} q_0 (t-\tau) d\tau=\int_0^t \lambda e^{-\lambda \tau} e^{-\lambda(t-\tau)}d\tau = \lambda t e^{-\lambda t}}

\displaystyle{q_2(t)=\int_0^t \lambda e^{-\lambda \tau} q_1 (t-\tau) d\tau=\int_0^t \lambda e^{-\lambda \tau} \lambda (t-\tau) e^{-\lambda(t-\tau)}d\tau }

\displaystyle{=\int_0^t \lambda^2 (t-\tau) e^{-\lambda t}d\tau= \frac{(\lambda t)^2}{2} e^{-\lambda t}} 以下同様に\displaystyle{q_{n-1}(t)=\frac{(\lambda t)^{n-1}}{(n-1)!} e^{-\lambda t}}と成立しているとすると、

\displaystyle{q_n(t)=\int_0^t \lambda e^{-\lambda \tau} q_{n-1} (t-\tau) d\tau=\int_0^t \lambda e^{-\lambda \tau} \frac{\lambda^{n-1}}{(n-1)!} (t-\tau)^{n-1} e^{-\lambda(t-\tau)}d\tau }

 \displaystyle{=\int_0^t \frac{\lambda^n}{(n-1)!} (t-\tau)^{n-1} e^{-\lambda t}d\tau= \frac{(\lambda t)^n}{n!}e^{-\lambda t}}

以上で到着人数の分布がポアソン分布であることと、到着間隔の分布が指数分布であることは同値であることがわかった。

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

例題でわかる待ち行列理論入門 [ 北岡正敏 ]
価格：2860円（税込、送料無料) (2020/9/9時点)

楽天で購入

 

2項分布、ポアソン分布

確率

Eという事象が起こるか起こらないかだけを問題とする。

定義　1回の試行でEの起こる確率をp起こらない確率をq(つまりq=1-p)とする。N回の試行でEがr回起こる確率B_{N,p}(r)を2項分布という。

命題　B_{N,p}(r)={_N}C_r p^rq^{N-r}で与えられる。

証明　\displaystyle{(p+q)^N=\sum_{r=0}^N {_N}C_r p^r q^{N-r}=1}であるから、確率pの事象Eがr回、確率qの事象がN-r回起こる確率B_{N,p}(r)={_N}C_r p^rq^{N-r}で与えられる。 

命題　2項分布B_{N,p}(r)の平均はNpである。

証明　平均\displaystyle{m_r=\sum_{r=0}^N r B_{N,p} (r)=\sum_{r=0}^N r {_N}C_r p^r q^{N-r}}である。

\displaystyle{(p+q)^N=\sum_{r=0}^N {_N}C_r p^r q^{N-r}}の両辺をpで微分して両辺にpをかけると

\displaystyle{Np(p+q)^{N-1}=Np=\sum_{r=0}^N r {_N}C_r p^r q^{N-r}}

したがって平均はNpである。

 

定義　\displaystyle{P_\lambda (r)=\frac{e^{-\lambda}\lambda^r}{r!}}で定義される0以上の実数の分布をポアソン分布という。

命題　2項分布B_{N,p}(r)でNp=\lambdaを一定に保ってNを大きくする極限をとるとポアソン分布になる。

証明　\displaystyle{B_{N,p}(r)={_N}C_r p^r q^{N-r}=\frac{N!}{r!(N-r)!}\left(\frac{\lambda}{N}\right)^r\left(1-\frac{\lambda}{N}\right)^{N-r}}

\displaystyle{=\frac{\lambda^r}{r!}\frac{N}{N}\frac{(N-1)}{N}\cdots \frac{(N-r+1)}{N}\left(1-\frac{\lambda}{N}\right)^{-r}\left(1-\frac{\lambda}{N}\right)^N}

\displaystyle{\frac{N-1}{N},\frac{N-2}{N}\cdots\frac{N-r+1}{N},\left(1-\frac{\lambda}{N}\right)^{-r}}はNを大きくする極限で1に収束する。

\displaystyle{\left(1-\frac{\lambda}{N}\right)^N=\left(1-\frac{\lambda}{N}\right)^{(-\frac{N}{\lambda})(-\lambda)}}であり、\displaystyle{\left(1-\frac{\lambda}{N}\right)^{-\frac{N}{\lambda}}}はNが無限大の極限でeに収束するから

\displaystyle{B_{N,p}(r) \to \frac{\lambda^r e^{-r}}{r!}=P_\lambda(r)}

 

長さNの線分にN個の粒子を落とすことを考える。単位長さあたり平均1個である。どこに落ちるかは均等と仮定する。長さ\lambdaの特定の線分上に何個落ちるかを考えると1個の粒子がそこに落ちる確率は\displaystyle{\frac{\lambda}{N}}ちょうどr個落ちる確率は

\displaystyle{B_{N,\frac{\lambda}{N}}(r)={_N}C_r \left(\frac{\lambda}{N}\right)^r \left( 1 - \frac{\lambda}{N}\right)^{N-r}}

であり、ここでNを無限大にした無限に長い線分に無限に多くの粒子を落とす状態を考えるのだが単位長さあたりに1個という割合をかえないとするとポアソン分布に近づくので、単位長さあたり平均1個の粒子を落としたとき特定の\lambda個の区画上に実際にr個落ちる確率ということになる。また期待値はNp=\lambdaである。


 

ファイアウォール以外の監視システム

名称 内容
IDS 侵入検知システム。ファイアウォールでは防ぐことができない不正アクセスを検知できる。ただし、侵入を防止することはできない。検知には次の方法がある。
・不正検出：不正侵入を示す特定のシグネチャパターンの一致による検知
・平常時から逸脱する動作による動作による検知
IPS 侵入防止システム。IDSの機能に加え、不正アクセスをリアルタイムで防止することができる。