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


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

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

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

> ・・・

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

Web上のリソースでいえば、[放送大学の説明・導出][7]が、「厳密すぎず、こうなるものと割り切りすぎず」で、一番わかりやすいと思う。[京大](http://www-optima.amp.i.kyoto-u.ac.jp/~takine/tmp/shiryou.pdf)とか[東大](http://ocw.u-tokyo.ac.jp/lecture_files/engin_10/5/notes/ja/04_Queuing_Theory.pdf)のM/M/1周辺の説明とくらべてみよう。
※大学で数学の基礎をしっかりやってたら京大・東大のほうがいいのかもしれない。

具体的には、[スライド](http://www.campus.ouj.ac.jp/%7Emaps17/11/11Queueing_pat.pdf)の以下箇所

- p35～39 : Pn(t)の各項の説明
- p40～44 : Pnの漸化式導出など
- p49 : Lw=ρ/(1-ρ)の導出
    - [講義ノート](http://www.campus.ouj.ac.jp/%7Emaps17/11/11Queueing_note.pdf)の対応部分も参照

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

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

```math
L=\sum_{n=0}^{\infty} nP_n=( 1 - \rho )\sum_{n=0}^{\infty} n \rho^{n}
```


- その期待値の計算で出てくる、等差×等比級数の和と無限とかどうするんだ

とか

> ここで、

> ```math
\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
```
として、いったん

```math
\begin{align}
S_n&=\sum_{k=0}^{n} k\rho^{k}\\
\end{align}
```

を考える。Σを展開していくと・・・

```math
\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にρをかけたものと並べる

```math
\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}
```

で、辺々引く

```math
(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}
```

となる。

```math
(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にρをかけたものとならべて、

```math
\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}\\
```

この辺々をひくと、

```math
(1 - \rho) \cdot T = \rho^{1} - \rho^{n+1}
```

[スライド](http://www.campus.ouj.ac.jp/%7Emaps17/11/11Queueing_pat.pdf)p32の「定常状態」を考えているので、0 < ρ=λ/μ < 1であり、0 < 1 - ρ < 1 なので、

```math
1 - \rho \neq 0 
```

で、両辺を割ると、

```math
T = \frac{\rho \cdot (1 - \rho^{n})}{1 - \rho}
```

Tが求められたので、もとに戻すと

```math
(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}\\
```
両辺を

```math
1 - \rho \neq 0 
```
で割って、

```math
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} )\\ 
```

もともと、

```math
\sum_{n=0}^{\infty} n\rho^{n} = \lim_{n \to \infty} S_n\\
```

のためにSnを求めていたことを思い出すと・・・

```math
\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)で置き換えると、

```math
\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)のほうが∞にいくのがはやいので

```math
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\\ 
```

であり(ロピタルの定理などなどで確かめられる)、

```math
\lim_{n \to \infty}(\frac{1}{b^{n}} + \frac{n}{b^{n}} - \frac{n}{b^{n+1}})=0
```

となる。これで、

```math
\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}\\
```

```math
\sum_{n=0}^{\infty} n\rho^{n} = \frac{ \rho }{(1 - \rho)^{2}}

```
で導出できた。

・・・間違ってたら、すみません。

# 参考
[問題解決の数理（’１７）第11章・第11回　待ち行列理論：待ちの数理- 放送大学][7]
[期待値の計算法と意味。その使い方と注意点 _ アタリマエ！][8]
[queuing model「待ち行列モデル」の直感的な理解のために](http://lise-sophia.net/kktm/Essay/queue.htm)
[三項間漸化式の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