待ち行列理論（M_M_1モデル）がようやく分かった（情報処理技術者試験レベルで） - pmekyky385の日記
個人的に覚えておけばいいと思う公式
・・・
- Lw (待ち行列の長さ(何人待っているか、が直感的と思う)) : Lw=ρ/(1-ρ)
・・・
**Lwは理屈は分からない（なぜ ρ/(1-ρ) となる？）**けど至るところで見るので間違ってはないと思う。
Web上のリソースでいえば、放送大学の説明・導出が、「厳密すぎず、こうなるものと割り切りすぎず」で、一番わかりやすいと思う。京大とか東大のM/M/1周辺の説明とくらべてみよう。
※大学で数学の基礎をしっかりやってたら京大・東大のほうがいいのかもしれない。
具体的には、スライドの以下箇所
- p35～39 : Pn(t)の各項の説明
- p40～44 : Pnの漸化式導出など
- p49 : Lw=ρ/(1-ρ)の導出
- 講義ノートの対応部分も参照
背景知識がちょっと必要で、
L=\sum_{n=0}^{\infty} nP_n=( 1 - \rho )\sum_{n=0}^{\infty} n \rho^{n}
- その期待値の計算で出てくる、等差×等比級数の和と無限とかどうするんだ
とか
ここで、
\sum_{n=0}^{\infty} n\rho^{n} = \frac{ \rho }{ ( 1 - \rho )^{2} }
って、どこから出てきたんだ・・・を埋める必要があります(下記「こんな感じでいいと思う」参照)。
が、
- 天下り的に公式を覚えられない人
- 式的にそれっぽく理解できないと、モヤモヤする人
にはいいかなと。
# こんな感じでいいと思う
[Qiitaの数式の書き方][9]の勉強を兼ねて、冗長に書いていく。
```math
\sum_{n=0}^{\infty} n\rho^{n} = \lim_{n \to \infty} \sum_{k=0}^{n} k\rho^{k} = \lim_{n \to \infty} S_n
として、いったん
\begin{align}
S_n&=\sum_{k=0}^{n} k\rho^{k}\\
\end{align}
を考える。Σを展開していくと・・・
\begin{align}
S_n &= 0 \cdot \rho^{0} + 1 \cdot \rho^{1} + 2 \cdot \rho^{2} + 3 \cdot \rho^{3} + \cdots + n \cdot \rho^{n}
\end{align}
で、Sにρをかけたものと並べる
\begin{eqnarray}
S_n &=& 0 \cdot \rho^{0} + 1 \cdot \rho^{1} + 2 \cdot \rho^{2} + 3 \cdot \rho^{3} + \cdots + n \cdot \rho^{n} \\
\rho \cdot S_n &=& \qquad\quad\,\, 0 \cdot \rho^{1} + 1 \cdot \rho^{2} + 2 \cdot \rho^{3} + \cdots + (n-1) \cdot \rho^{n}+ n \cdot \rho^{n+1}
\end{eqnarray}
で、辺々引く
(1-\rho) \cdot S_n = 1 \cdot \rho^{1} + 1 \cdot \rho^{2} + 1 \cdot \rho^{3} + \cdots + 1 \cdot \rho^{n} - n \cdot \rho^{n+1}
となる。
(1-\rho) \cdot S_n = (\rho^{1} + \rho^{2} + \rho^{3} + \cdots + \rho^{n}) - n \cdot \rho^{n+1}\\
ここで、T = \rho^{1} + \rho^{2} + \rho^{3} + \cdots + \rho^{n} とおいて、\\
(1-\rho) \cdot S_n = T - n \cdot \rho^{n+1}
Tを求めていく。Tにρをかけたものとならべて、
\begin{eqnarray}
T &=& \rho^{1} + \rho^{2} + \rho^{3} + \cdots + \rho^{n}\\
\rho \cdot T &=& \quad\quad\, \rho^{2} + \rho^{3} + \cdots + \rho^{n} + \rho^{n+1}
\end{eqnarray}\\
この辺々をひくと、
(1 - \rho) \cdot T = \rho^{1} - \rho^{n+1}
スライドp32の「定常状態」を考えているので、0 < ρ=λ/μ < 1であり、0 < 1 - ρ < 1 なので、
1 - \rho \neq 0
で、両辺を割ると、
T = \frac{\rho \cdot (1 - \rho^{n})}{1 - \rho}
Tが求められたので、もとに戻すと
(1-\rho) \cdot S_n = T - n \cdot \rho^{n+1}\\
\Leftrightarrow (1-\rho) \cdot S_n = \frac{\rho\cdot (1 - \rho^{n})}{1 - \rho} - n \cdot \rho^{n+1}\\
\Leftrightarrow (1-\rho) \cdot S_n = \frac{\rho\cdot (1 - \rho^{n})- (1 - \rho) \cdot n \cdot \rho^{n+1} }{1 - \rho}\\
\Leftrightarrow (1-\rho) \cdot S_n = \rho \cdot \frac{ (1 - \rho^{n})- (1 - \rho) \cdot n \cdot \rho^{n} }{1 - \rho}\\
\Leftrightarrow (1-\rho) \cdot S_n = \rho \cdot \frac{ 1 - \rho^{n}- (n \cdot \rho^{n} - n \cdot \rho^{n+1}) }{1 - \rho}\\
\Leftrightarrow (1-\rho) \cdot S_n = \rho \cdot \frac{ 1 - \rho^{n}- n \cdot \rho^{n} + n \cdot \rho^{n+1} }{1 - \rho}\\
\Leftrightarrow (1-\rho) \cdot S_n = \rho \cdot \frac{ 1 - (1+n)\cdot \rho^{n} + n \cdot \rho^{n+1} }{1 - \rho}\\
両辺を
1 - \rho \neq 0
で割って、
S_n = \rho \cdot \frac{ 1 - (1+n)\cdot \rho^{n} + n \cdot \rho^{n+1} }{(1 - \rho)^{2}}\\
\Leftrightarrow S_n = \frac{ \rho }{(1 - \rho)^{2}} \cdot ( 1 - (1+n)\cdot \rho^{n} + n \cdot \rho^{n+1} )\\
もともと、
\sum_{n=0}^{\infty} n\rho^{n} = \lim_{n \to \infty} S_n\\
のためにSnを求めていたことを思い出すと・・・
\begin{eqnarray}
\sum_{n=0}^{\infty} n\rho^{n} &=& \lim_{n \to \infty}\frac{ \rho }{(1 - \rho)^{2}} \cdot ( 1 - (1+n)\cdot \rho^{n} + n \cdot \rho^{n+1} ）\\
&=& \frac{ \rho }{(1 - \rho)^{2}} \lim_{n \to \infty}( 1 - (1+n)\cdot \rho^{n} + n \cdot \rho^{n+1} ) \\
&=& \frac{ \rho }{(1 - \rho)^{2}} + \frac{ \rho }{(1 - \rho)^{2}}\lim_{n \to \infty}(-(1+n)\cdot \rho^{n} + n \cdot \rho^{n+1} ) \\
&=& \frac{ \rho }{(1 - \rho)^{2}} - \frac{ \rho }{(1 - \rho)^{2}}\lim_{n \to \infty}((1+n)\cdot \rho^{n} - n \cdot \rho^{n+1} ) \\
&=& \frac{ \rho }{(1 - \rho)^{2}} - \frac{ \rho }{(1 - \rho)^{2}}\lim_{n \to \infty}(\rho^{n} + n \cdot \rho^{n} - n \cdot \rho^{n+1}) \\
\end{eqnarray}\\
となる。ここで、
0 < ρ < 1 ・・・定常状態
より、極限部分をわかりやすさのためにb=1/ρ (b > 1)で置き換えると、
\begin{eqnarray}
\sum_{n=0}^{\infty} n\rho^{n} &=& \frac{ \rho }{(1 - \rho)^{2}} - \frac{ \rho }{(1 - \rho)^{2}}\ lim_{n \to \infty}(\rho^{n} + n \cdot \rho^{n} - n \cdot \rho^{n+1})\\
&=& \frac{ \rho }{(1 - \rho)^{2}} - \frac{ \rho }{(1 - \rho)^{2}}\ lim_{n \to \infty}(\frac{1}{b^{n}} + \frac{n}{b^{n}} - \frac{n}{b^{n+1}})\\
\end{eqnarray}\\
nよりもb^n (b>1)のほうが∞にいくのがはやいので
lim_{n \to \infty} \frac{1}{b^{n}}=0\\
lim_{n \to \infty} \frac{n}{b^{n}}=0\\
lim_{n \to \infty} \frac{n}{b^{n+1}}=0\\
であり(ロピタルの定理などなどで確かめられる)、
\lim_{n \to \infty}(\frac{1}{b^{n}} + \frac{n}{b^{n}} - \frac{n}{b^{n+1}})=0
となる。これで、
\begin{eqnarray}
\sum_{n=0}^{\infty} n\rho^{n} &=& \frac{ \rho }{(1 - \rho)^{2}} - \frac{ \rho }{(1 - \rho)^{2}}\ lim_{n \to \infty}(\frac{1}{b^{n}} + \frac{n}{b^{n}} - \frac{n}{b^{n+1}})\\
&=& \frac{ \rho }{(1 - \rho)^{2}} - \frac{ \rho }{(1 - \rho)^{2}} \cdot 0 \\
&=& \frac{ \rho }{(1 - \rho)^{2}}
\end{eqnarray}\\
\sum_{n=0}^{\infty} n\rho^{n} = \frac{ \rho }{(1 - \rho)^{2}}
で導出できた。
・・・間違ってたら、すみません。
参考
問題解決の数理（’１７）第11章・第11回 待ち行列理論：待ちの数理- 放送大学
期待値の計算法と意味。その使い方と注意点 _ アタリマエ！
queuing model「待ち行列モデル」の直感的な理解のために
三項間漸化式の3通りの解き方 _ 高校数学の美しい物語
待ち行列の講座1 - An easy lecture of Math
待ち行列の講座2 - An easy lecture of Math
待ち行列の講座3 - An easy lecture of Math
ネットワークの数学 - Ｍ／Ｍ／１：ITpro
待ち行列理論（M_M_1モデル）がようやく分かった（情報処理技術者試験レベルで） - pmekyky385の日記
待ち行列 - まりんきょ学問所：音楽、ことば、コンピュータ
Qiitaの数式チートシート - Qiita