(O+P)ut

アウトプット



(O+P)ut

エンジニアのアウトプット

【待ち行列理論】待ち人数の公式ρ/1-ρを導出する

スポンサーリンク

はじめに

基本情報技術者試験の範囲に「待ち行列理論(M/M/1モデル)」というものがあり、窓口利用率\rhoを用いて以下の公式で待ち行列に並んでいる人数を算出するよう記載があります。*1

\cfrac{\rho}{1-\rho}

そんな便利な式ですが、この式の導出は真面目に取り組むとかなり難しいです。が、せっかくなので「公式導出について理解した気になる」をゴールにして分かりやすく説明してみました。

所要時間目安:10分

以下は道中で利用する公式や前提です。

無限級数の公式

\displaystyle\sum_{k=0}^{\infty}ar^k=\cfrac{a}{1-r}
\displaystyle\sum_{k=1}^{\infty}kr^k=\cfrac{r}{(1-r)^2}

上記公式はrの絶対値が1未満の時に成り立ちます。理系の方は高校数学で見たはず。

微分方程式

\cfrac{f(t+{\Delta}t)-f(t)}{{\Delta}t}=\cfrac{df(t)}{dt}
かつ定常状態であれば\cfrac{df(t)}{dt}=0

要は関数fに時間変化がなくなれば、時間で微分した値は0

列に並んでいる人の公式を算出する

イメージ

最終的に算出したいゴールをまずはイメージします。
列に並んでいる人数の期待値が知りたければ、列に並んでいる人数のそれぞれの確率が分かれば算出できます

例えば、窓口に0人並んでいる確率が0.2、窓口に1人並んでいる確率が0.5、窓口に2人並んでいる確率が0.3、窓口に3人以上並んでいる確率は0だとすれば

> 1*0.5+2*0.3
[1] 1.1

つまり1.1人並んでいると算出できました。

これを一般化すれば窓口に k人並んでいる確率がp_{k}とすれば列に並ぶ人の数は
\displaystyle\sum_{k=1}^{\infty}kp_{k}
と書けます。

要は窓口にk人並んでいる確率p_{k}を求めることが肝となります。

窓口に0人並んでいる確率を状態遷移で考える

とっかかりのために、窓口に0人並んでいる確率p_{0}に関する式を求めます。
具体的にはある時刻tから微小時間{\Delta}tが経過した際に0人が並んでいる・・という状態を考えてみます。

上記で考えられるパターンは以下の2種類。

  • 時刻tに0人並んでいて微小時間の間に客が到着しない
  • 時刻tに1人並んでいて微小時間の間に客がサービスを受けていなくなる

これを数式で表すと以下になります。
p_{0}(t+{\Delta}t) = p_{0}(t)(1-{\lambda}{\Delta}t)+p_{1}(t){\mu}{\Delta}t

平均到着率\lambdaや平均サービス量\muに時間をかけることで確率として表現しています。
ちなみに時刻tに2人並んでいて微小時間の間に2人ともサービスを受けていなくなる確率は、微小時間を限りなく小さくすることで無視できる前提のもとで考慮に入れません。

上の状態方程式を整理すると
p_{0}(t+{\Delta}t)-p_{0}(t)= -p_{0}(t){\lambda}{\Delta}t+p_{1}(t){\mu}{\Delta}t

\cfrac{p_{0}(t+{\Delta}t)-p_{0}(t)}{{\Delta}t}= -p_{0}(t){\lambda}+p_{1}(t){\mu}

\cfrac{dp_{0}(t)}{dt}=-p_{0}(t){\lambda}+p_{1}(t){\mu}

ここで冒頭に記載した前提である"定常状態であれば\cfrac{df(t)}{dt}=0 "という部分を式に当てはめます。

この定常性は自明ではありませんが、サービス量と到着率が一定であればそれぞれの確率は時間に寄らず一定になりそうな感覚をイメージしてください。

そうすると上の式は
0=-p_{0}(t){\lambda}+p_{1}(t){\mu}

p_{1}(t)=p_{0}(t)\cfrac{{\lambda}}{\mu}

となりました。
次に窓口にn人並んでいる時の微小時間後というより一般的なケースを考えます。

窓口にn人並んでいる確率を状態遷移で考える

考えられるパターンは以下の3種類。

  • 時刻tn-1人並んでいて微小時間の間に客が到着する
  • 時刻tn人並んでいて微小時間の間に客は到着しないしサービスも受けない
  • 時刻tn+1人並んでいて微小時間の間に客がサービスを受けていなくなる

それらを上と同じように式にして変形すると以下のようになります。
\cfrac{dp_{n}(t)}{dt}=p_{n-1}(t){\lambda}-p_{n}(t)({\lambda}+{\mu})+p_{n+1}(t){\mu}
これもまた定常状態を仮定すれば左辺は0になります。
0=p_{n-1}(t){\lambda}-p_{n}(t)({\lambda}+{\mu})+p_{n+1}(t){\mu}
上の式は任意のnで成り立つので、例えばn=1を代入してみます。

0=p_{0}(t){\lambda}-p_{1}(t)({\lambda}+{\mu})+p_{2}(t){\mu}

ここで先ほど窓口0人の状態式で導出したp_{1}(t)=p_{0}(t)\cfrac{{\lambda}}{\mu}が使えます。これを代入すると
0=p_{0}(t){\lambda}-\cfrac{p_{0}(t){\lambda}}{{\mu}}({\lambda}+{\mu})+p_{2}(t){\mu}

p_{2}(t)=p_{0}(t)(\cfrac{{\lambda}}{\mu})^{2}

新たな関係式が出てきました。

次はn=2を代入してみると...?

なんと、これを繰り返えして行けば、窓口にn人並んでいる確率は以下の式で表現できます。
p_{n}(t)=p_{0}(t)(\cfrac{{\lambda}}{\mu})^{n}

前半部分で述べた「窓口にk人並んでいる確率p_{k}を求めることができれば並んでいる人数は求められる」のゴールが近づいてきました。あとはp_{0}(t)が算出できればゴールは目の前です。

確率の全体は1

窓口に0人並んでいる確率と窓口に1人並んでいる確率と... 窓口に∞人並んでいる確率の合計は100%である1になります

この情報を数式で表現したのが以下。
\displaystyle\sum_{k=0}^{\infty}p_{0}(t)(\cfrac{{\lambda}}{\mu})^{k}=1が成り立ちます。

そして冒頭の前提に書いた\displaystyle\sum_{k=0}^{\infty}ar^k=\cfrac{a}{1-r}を利用すると

1=\cfrac{p_{0}(t)}{1-\rho}
p_{0}(t)=1-\rho

\rho=\cfrac{\lambda}{\mu}を利用して式をスッキリさせました。

p_{n}(t)=p_{0}(t)(\cfrac{{\lambda}}{\mu})^{n}
p_{n}(t)=(1-\rho){\rho}^nになりました。最後は期待値を求めます。

いよいよゴールです。

列に並んでいる人数の期待値

k人並んでいる確率がp_{k}(t)=(1-\rho){\rho}^kなので
\displaystyle\sum_{k=1}^{\infty}k(1-\rho){\rho}^kが求める値です。

\cfrac{\rho}{1-\rho}になるのでしょうか。

ここでも無限級数の公式\displaystyle\sum_{k=1}^{\infty}kr^k=\cfrac{r}{(1-r)^2}を利用すると
\displaystyle\sum_{k=1}^{\infty}k(1-\rho){\rho}^k=\cfrac{\rho(1-\rho)}{(1-\rho)^2}=\cfrac{\rho}{1-\rho}
となりました。長い道のりでした...

終わりに

今回はかなりざっくりした説明で、ポアソン分布や指数分布といった本来の議論の前提をすっ飛ばしてエッセンスだけを紹介しました。

ITパスポートや基本情報技術者の参考書で公式だけを覚えておくようにして切り上げるのも納得のボリュームの本内容ですが、あの公式はどっから来ているのだろうか?という素朴な疑問を持たれた方の理解の一助になれば幸いです。

*1:\rho=\cfrac{\lambda}{\mu}\lambdaは平均到着率で\muは平均サービス量


他の記事を読む