1. M/M/1モデル

  • 最も基礎的な待ち行列モデル。
  • サーバが1つで、単位時間あたりの要求の発生回数の確率分布がポアソン分布に従い、また要求の処理時間(サービス時間)が指数分布に従うシステムを対象とする。
  • 例えば、行列に並んでいる人たちを1つの窓口で処理しているような状況。
  • M/M/1のMは「マルコフ連鎖」、1は窓口が1つであることを示している。

2. ポアソン過程モデル

ランダムに生起する事象を表す確率過程。待ち行列モデルM/M/cでは要求の発生がポアソン過程に従うとしている。

  • 独立性: 出来事が起きるのは互いに独立
  • 定常性: 出来事が起きる確率は時間に依らず普遍
  • 希少性: 観測時間の間に出来事が2回以上起きる確率はo(Δt)
    • (つまりΔtを十分小さく取れば2回以上起きる確率は無視できる…ということ？)

3. モデルに使用する確率分布

3-1. ポアソン分布

\( P(x) = e ^ {- \lambda} \lambda ^ x / x! \)

  • 単位時間あたり平均 \( \lambda \) 回ランダムに起こる事象がx回起こる確率はポアソン分布 \( P(x) \) に従う。
  • 平均: \( \lambda \), 分散: \( \lambda \)
  • 二項分布 \( \binom {n} {x} p^x (1-p)^{n-x} \) において、大量観察、希少現象を仮定した場合に導かれる。
    • つまり \( np \to \lambda, n \to \infty, p \to 0 \)

3-2. 指数分布

\( f(x) = \mu e ^ {- \mu x} \)

  • 単位時間当たり平均 \( \mu \) 回ランダムに起こる事象の発生間隔は指数分布 \( f(x) \) に従う。
  • 平均: \( 1 / \lambda \), 分散: \( 1 / \lambda ^ 2 \)

4. 平均待ち時間の導出

手順は待ち行列理論（M/M/1モデル）の定理とその証明を参照。

ただ、「平均 \( 1/\mu \) に従う指数分布において、微小時間 \( \Delta t \) の間に窓口が1人処理する確率は \( \mu \Delta t \)」という点が直感的には理解できなかったため、そこだけ補足。

前回処理してから微小時間の間に1人処理する確率:
\( \int_{0}^{\Delta t} \mu e ^ {- \mu x} dx \)
\( = 1 - e ^ {- \mu \Delta t} \)
\( = 1 - \left( 1 + \frac {(- \mu)} {1!} \Delta t + \frac {(- \mu)^2} {2!} (\Delta t)^2 + … \right) \)
\( = \mu \Delta t + o(\Delta t) \)

よって、\( \Delta t \)が十分に小さければ\( \mu \Delta t \)となる。

参考