ネットワーク(スライド3)

というわけで、講義資料はよくわからないっ！！
やっとこさM/M/1までこぎつけたので、前回同様まとめることにする。
今回は待ち行列理論なので、レジに並ぶお客さんの例で考える。

今日一番書きたいのはM/M/1行列についてであるが、とりあえずその前に基礎知識を書いとく。

ポアソン到着
これは、行列に並ぶためにやってくるお客さんがやってくる確率がポアソン分布に従う(とする)というもの。
はい、ポアソン分布なんて懐かしすぎてなにも覚えてませんよね〜。
資料には証明も載ってるけど、読めばわかるのでとりあえず結論だけ。

到着率λ*1,時間t内に、k人の人がやってくる確率P(k)。
ポアソン分布では、
$P(k) = \frac{(\lambda t)^ke^{-\lambda t}}{k!}$

となる。
で、このとき平均、2乗平均、分散は

$E[X] = \sum_{k=0}^{\infty}k P(k) = ... = \lambda t$
$E[X^2] = \sum_{k=0}^{\infty}k^2 P(k) = ... =(\lambda t)^2+\lambda t$
$Var[X] = E[X^2] - (E[X])^2 = \lambda t$

となり、簡潔である。
また、時間t内にジョブが到着する確率は、

$F(t) = 1 - P(0) = 1-e^{-\lambda t}$

となり、(次に述べる)指数分布に従っている。

指数処理
これは、行列を処理してるレジの人がお客さん一人をさばくのにかかる時間の確率が指数分布に従う(とする)というもの。
はい、よくわかりませんね。とりあえず結論だけ。

処理率μ*2で処理をしているレジの店員が一人のお客さんを時間t以内にさばくことができる確率F(t)*3と、ちょうど時間tでさばき終わる確率f(t)*4
$F(t) = Prob[X\leq t] = 1-e^{-\mu t}$
$f(t) = \frac{dF(t)}{dt} = \mu e^{-\mu t}$

こんな感じ。

で、平均と分散は、

$E[X] = \int_{0}^{\infty}t f(t)dt = ... = \frac{1}{\mu}$
$Var[X] = \int_{0}^{\infty}(t-\frac{1}{\mu})^2f(t)dt = ... = \frac{1}{\mu^2}$

となり、これも簡潔である。

アーラン分布
処理率の同じn個の指数処理を連続しておこなう場合、n相アーラン分布に従い、確率密度関数f(t)は、

$f(t) = \frac{(n\mu)^nt^{n-1}e{-n\mu t}}{(n-1)!}}$

となるらしい。(でも覚えるのメンドくさいから多分覚えない。)

M/M/1待ち行列モデル
最初のMは、到着過程(客の到着確率分布)がポアソン到着であることを、
真ん中のMは処理時間分布(レジ処理)が指数処理であることを、
最後の1は、サーバ数(レジの数)が1つであることを表す。

状態iを、お客さんがレジにi人いる状態だとする。
ここで、待ち行列理論とは、定常状態を考えるものである。定常状態とは、時間によらず各状態への遷移確率が一定である安定した状態のことである(?)。一般に定常状態が存在するならば、初期状態から、時間→∞にいくに連れて定常状態に近づいていく(?)。

微小時間⊿tの間に状態iから状態遷移する確率を考える。

状態i→状態i+1となる確率は、λ⊿t　(1人お客が到着)
状態i→状態i-1となる確率は、μ⊿t　(1つ処理が終了)
これより、余事象
状態i→状態iの確率は、(1-λ-μ)⊿t

⊿t後に状態iとなる確率をPiとする。
定常状態であるから、Pi(t) = Pi(t+⊿t)であると考えられる。よって、

$P_i(t+\Delta t)\Delta t = (\lambda P_{i-1} + \mu P_{i+1} + (1-\lambda -\mu )P_{i})\Delta t$
$P_i = P_i(t) = P_i(t+\Delta t)$ より、
$(\lambda + \mu ) P_i = \lambda P_{i-1} + \mu P_{i+1}$
ただし、状態0に対しては、端であり、遷移が状態0→0, 状態1→0しか存在しないため、
$\lambda P_0 = \mu P_1$

となる。
以上より、 $\rho = \lambda /\mu$ とすれば、(ρをシステムの利用率という。)

$P_1 = \rho P_0$
$P_i = (\rho + 1)P_{i-1} - \rho P_{i-2} = ... = \rho^iP_0$

となる。

~~ここからがいいところなのに力尽きたので今日はこのくらいで明日追記しよう。~~
はい、明日とか言っといて一週間経ちました。~~バイト~~勉強の時間です。(1/30(火)17:24)

前回は、M/M/1待ち行列の漸化式をたてるところまでやりました。
今日は、一般式を求めるところからです。

当然
$\sum_{i=0}^{\infty}P_i = \sum_{i=0}{\infty}\rho^iP_0 = 1$
ですから、 $\rho$ < 1ならば、無限等比級数解いて、 $P_0 = 1-\rho$ より
$P_i = (1-\rho)\rho^i$

となる。
$\rho \geq 1$ ならば、処理するより、到着のほうが多いから、お客の列とストレスは無限に増え続け、定常状態とはならない。大繁盛である。

また、このとき( $\rho \lt 1$ )、平均ジョブ数(N)と平均待ちジョブ数(Nw)は、
※これ重要

$N = \sum_{n=0}^{\infty}nP_n = (1-\rho)\sum_{n=0}^{\infty}\frac{\rho}{(1-\rho^2)} = \frac{\rho}{1-\rho}$
$N_w = \sum_{n=0}^{\infty}(n-1)P_n = \sum_{n=0}^{\infty}nP_n-(1-P_0) = \frac{\rho^2}{1-\rho}$