WATAPEDIA
--
数学
-- M/M/1
Last updated Jan. 30, 2011
Home
Return
PDFを表示
記事が表示されない場合は,ブラウザが非対応です.
上のPDFを表示をクリックしてください.
comp -MYPEDIA Math- M/M/1 M/M/1 1 概要 M/M/1 システムは応用数学の待ち行列理論において,最もシンプルな待ち行列 モデルの一つである.到着間隔とサービス時間が指数分布に従い,サーバ数は 1 で, キュー長の限界はない.M/M/1 は到着レートを λ (> 0),サービスレートを µ (> 0) とし,ρ = λ/µ とすると,ρ < 1 で定常状態を持つ. 2 系内客数の確率的性質 ここでは,M/M/1 システムの系内客数の確率的挙動についてまとめる. 系内客数の定常確率はマルコフモデルを用いることにより,以下のように算出で きる. M/M/1 システムの系内客数の定常状態確率 系内客数 N が,定常状態において k である確率 pk は以下の通り,幾何 分布で与えられる. pk = Pr(N = k) = (1 − ρ)ρk (k = 1, 2, · · · ) よって,M/M/1 システムの系内客数の平均と分散は以下の通り. M/M/1 システムの系内客数の平均と分散 系内客数 N の定常状態における平均と分散は E [N] = ρ 1 − ρ , Var [N] = ρ (1 − ρ)2 となる. また,異なる時刻の系内客数の関係を表す自己共分散関数についての性質は以下 のようになる. 1 Math 一覧へ . . comp -MYPEDIA Math- M/M/1 システムの系内客数の自己共分散関数 時刻 t における系内客数 N(t) の自己共分散関数 R(τ) は以下のとおり与 えられることが知られている. R(τ) = Cov(N(t), N(t + τ)) = λµ(µ − λ) π ∫ 2π 0 sin2 θ e−wτ w3 dθ ここで w = λ + µ − 2 √ λµ cos θ 系内客数の過程 N(t) が定常であることから,自己共分散関数が t の関数になって いないことに注意する. これらは複雑な形をしているが,その区間 [0, ∞) での積分は比較的簡単な形で得 られることが知られている. M/M/1 システムの系内客数の自己共分散関数の積分 M/M/1 の系内客数過程の自己共分散関数 R(τ) の区間 [0, ∞) での積分 は以下の通りになる. ∫ ∞ 0 R(τ)dτ = λµ(λ + µ) (µ − λ)4 これにより ρ < 1 で有限値に収束することから,M/M/1 の系内客数の過程は短期 依存性1を持つことがわかる. また,自己共分散関数 R(τ) は µ = 1 とすることで,比較的簡単な形に近似できる. M/M/1 システムの系内客数の自己共分散関数の近似 M/M/1 の系内客数過程の自己共分散関数 R(τ) は µ = 1 のとき,以下の 通り近似できる. R(τ) ≅ ρ 2(1 − ρ)2 { e−Aτ + e−Bτ } (τ > 0) ここで,A と B はそれぞれ以下で与えられる. A = (1 − ρ)2 1 + ρ + √ ρ , B = (1 − ρ)2 1 + ρ − √ ρ 1非整数ブラウン運動 . . 2 Math 一覧へ . . comp -MYPEDIA Math- λ = 0.5 の場合の R(τ) と近似式を以下に示す. ! !"# !"$ !"% !"& ' '"# '"$ '"% '"& # ! ( '! '( #! )*+,-./012 34567 8.92 :;< 図 1: 自己共分散関数の近似 3 その他の確率的性質 M/M/1 の系内滞在時間の確率的性質は以下の通り. M/M/1 システムの系内滞在時間の平均と分散 系内滞在時間 T の定常状態における平均は,リトルの公式を用いること により, E [T] = λE [N] = 1/µ 1 − ρ となる. M/M/1 の (サービス中の客を含まない) キュー長の確率的性質は以下の通り. M/M/1 システムのサービス中の客を含まないキュー長の平均と分散 サービス中の客を含まないキュー長 B の定常状態における平均と分散 は,上述の定常状態確率から, E [B] = ρ2 1 − ρ , Var [B] = ρ2 (1 − ρ)2 となる. M/M/1 の (サービス中の客のサービス時間を含まない) 待ち時間の確率的性質は 以下の通り. 3 Math 一覧へ . . comp -MYPEDIA Math- M/M/1 システムの待ち時間の平均と分散 待ち時間 W の定常状態における平均は,サービス時間と系内客数の独 立性と PASTA 則から, E [W] = 1 µ E[N] = ρ/µ 1 − ρ となる.また,分散は,条件付き分散に関する i.i.d. の確率変数個の和 の分散の性質2より Var [W] = 1 µ2 {E[N] + Var[N]} となる. 2期待値と分散 . . 4 Math 一覧へ . .