なんで待ち行列の長さは、ρ/(1-ρ)なのか？・・・を理解するのによさそうな資料

[待ち行列理論（M_M_1モデル）がようやく分かった（情報処理技術者試験レベルで） - pmekyky385の日記][2]

個人的に覚えておけばいいと思う公式

・・・

• Lw (待ち行列の長さ(何人待っているか、が直感的と思う)) : Lw=ρ/(1-ρ)

・・・

Lwは理屈は分からない（なぜ ρ/(1-ρ) となる？）けど至るところで見るので間違ってはないと思う。

Web上のリソースでいえば、[放送大学の説明・導出][7]が、「厳密すぎず、こうなるものと割り切りすぎず」で、一番わかりやすいと思う。京大とか東大のM/M/1周辺の説明とくらべてみよう。
※大学で数学の基礎をしっかりやってたら京大・東大のほうがいいのかもしれない。

具体的には、スライドの以下箇所

• p35～39 : Pn(t)の各項の説明
• p40～44 : Pnの漸化式導出など
• p49 : Lw=ρ/(1-ρ)の導出
  • 講義ノートの対応部分も参照

背景知識がちょっと必要で、

• [漸化式って特性方程式を用いた解法があったなぁ][5]
• [期待値って、確率と値を掛け算したやつのΣだったなぁ][8]

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]の勉強を兼ねて、冗長に書いていく。

\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回　待ち行列理論：待ちの数理- 放送大学][7]
[期待値の計算法と意味。その使い方と注意点 _ アタリマエ！][8]
queuing model「待ち行列モデル」の直感的な理解のために
[三項間漸化式の3通りの解き方 _ 高校数学の美しい物語][5]
[待ち行列の講座1 - An easy lecture of Math][6-1]
[待ち行列の講座2 - An easy lecture of Math][6-2]
[待ち行列の講座3 - An easy lecture of Math][6-3]
[ネットワークの数学 - Ｍ／Ｍ／１：ITpro][3]
[待ち行列理論（M_M_1モデル）がようやく分かった（情報処理技術者試験レベルで） - pmekyky385の日記][2]
[待ち行列 - まりんきょ学問所：音楽、ことば、コンピュータ][1]
[Qiitaの数式チートシート - Qiita][9]

[9]:http://qiita.com/PlanetMeron/items/63ac58898541cbe81ada
[8]:http://atarimae.biz/archives/14396
[7]:http://www.campus.ouj.ac.jp/~maps17/11/
[6]:http://www.geocities.co.jp/Technopolis-Mars/5427/mathtrtop.html
[6-1]:http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque1.html
[6-2]:http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque2.html
[6-3]:http://www.geocities.co.jp/Technopolis-Mars/5427/math/sw_waitque2.html
[5]:http://mathtrain.jp/sankoukan
[4]:http://d.hatena.ne.jp/tanachhi/20090723/1248363583
[3]:http://itpro.nikkeibp.co.jp/article/COLUMN/20060920/248528/?rt=nocnt
[2]:http://d.hatena.ne.jp/pmekyky385/20120923/1348371120
[1]:http://www.ne.jp/asahi/music/marinkyo/js/starvico.html.ja