《待ち行列における希少事象の評価》

【まちぎょうれつにおけるきしょうじしょうのひょうか (rare event evalution of queueing systems) 】

　待ち行列理論は, 電話トラヒックの輻輳を解析することから始まったのであるが, ここで述べる「待ち行列における溢れ確率 (overflow probability) 近似」は, 近年普及してきたマルチメディア通信ネットワークの輻輳を解析する必要性から始まったと言える [5]. それでは従来の待ち行列と何が異なるか？ 一つは, 従来良く用いられたポアソン入力や再生過程入力とは異なり, 強い相関を持つ入力トラヒックを対象にしたこと, もう一つは, 評価すべき溢れ確率が$10^{-7}\sim 10^{-9}\,$のオーダの極めて稀な確率事象を対象にしたことである. 以下, これらの課題から生まれた新たな入力モデルや解析手法について簡単に述べる.

流体近似モデル　待ち行列モデルとしてマルチメディア通信ネットワークで用いられる穴あきバケツモデル (bucket-with-hole model) の離散時間版を考える. 時刻$n\,$の入力率 (input rate) を$X_{n}\,$, 出力率を$C\,$とすると, 時刻$n\,$での待ち行列長構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle Q_{n}\, } は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle Q_{n}=\max\{Q_{n-1}+ U_n, 0\}, \qquad U_n=X_n-C, \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (1)\, }

で表される. ここで, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{X_n\}\, } をE$(X_{n})<C\,$の定常過程とすると, 定常状態における溢れ確率P$(Q>x)\,$は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{P}(Q>x)=\mbox{P}\left(\sup_{n\geq 0}\{A_n\}>x \right) \, } 　　　　　$(2)\,$

で与えられる. 但し, $\textstyle A_{n}=\sum _{i=1}^{n}U_{-i}\,$, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_0=0\, } である. $U_{n}\,$を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 番目の客のサービス時間構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S_n\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 番目と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n+1\, } 番目の客の到着間隔構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle T_n\, } の差構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S_n-T_n\, } と考えるならば, (2) は先着順サービスのG/G/1待ち行列における待ち時間分布の裾 (tail of waitingtime distribution)となる. これは, (1) で表される待ち行列モデルが特殊なモデルではなく, 従来から議論されている待ち行列モデルと基本的に変わらないことを意味している. 従来と大きく異なるところは, 入力として強い相関をもつマルコフ型入力過程や長期依存型入力過程 (long-rangedependent input process)が議論されるようになったことである.

漸近解析　ところで, 溢れ確率の解析手法については, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle Q_n\, } が閾値$x\,$を越える事象が極めて稀な場合を考えているため, 大偏差理論 (large deviation theory)を用いた漸近解析 (asymptotic analysis)が注目を浴びるようになった. ここでは, 長期依存型入力を含む一般的な入力過程の場合の漸近解析を説明する [3].

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \psi (\theta)\equiv \lim_{n\rightarrow \infty} v(n)^{-1} \log \mbox{E}[\mathrm{e}^{\theta A_nv(n)/a(n)}], \;\;\;\; g(y)\equiv \lim_{n\rightarrow \infty}\frac{v(a^{-1}(n/y))}{h(n)} \, }

が存在するように適当な増加数列構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{v(n)\}, \{a(n)\}, \{h(n)\}\, } を与える. 但し, $a^{-1}(z)\,$ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \equiv\sup\{n:a(n)\leq z\}\, } . このとき, 大偏差理論のGärtner-Ellisの定理 [1] から, 任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y>0\, } に対して

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lim_{n\rightarrow \infty}v(n)^{-1}\log \mbox{P}(A_n/a(n)>y)=-\psi^{*}(y) \, }

が成り立つ. 但し, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \psi^{*}(y)\equiv \sup_{\theta}\{\theta y - \psi (\theta)\}\, } . 更に

$\sup _{n\geq 0}{\mbox{P}}(A_{n}>x)\leq {\mbox{P}}(\sup _{n\geq 0}\{A_{n}\}>x)\leq \sum _{n}{\mbox{P}}(A_{n}>x)\,$

の不等式において, $x\,$が十分大きいところではオーダの意味で

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sup_{n\geq 0} \mbox{P}(A_n >x)\approx \sum_{n}\mbox{P}(A_n>x) \approx \mbox{P}(A_{a^{-1}(x/y^{*})}>x) \, }

となる. ここで, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle y^{*}=\arg\inf_{y>0}g(y) \psi^{*}(y)\, } である. これは, 大偏差理論における稀な事象が生起するときの基本的な性質である. つまり, (2)の右辺は負のドリフトを持つ確率過程構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{A_n\}\, } が閾値構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\, } にヒットする確率と解釈できるが, もしヒットするならば最も可能性の高い時点構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } , ここでは構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a^{-1}(x/y^{*})\, } , でヒットすることを意味する. これらの議論から溢れ確率に関して

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lim_{x\rightarrow \infty} h(x)^{-1} \log \mbox{P}(Q>x ) = - g(y^{*}) \psi^{*}(y^{*}) \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (3)\, }

が得られる. (3) は緩やかに変動する関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B(x)\, } が存在して

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{P}(Q>x)=B(x)\mathrm{e}^{-\kappa h(x)}, \qquad \kappa=g(y^{*}) \psi^{*}(y^{*}), \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (4)\, }

であることを意味する. 具体的な入力過程で計算するならば, 短期依存型であるマルコフ型入力過程のときは, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h(x)=x\, } となり, 溢れ確率は指数的に減衰する. 一方, 長期依存型入力過程の多くは構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h(x)=x^{\beta}, \beta\in (0, 1)\, } となり, 溢れ確率が指数より緩やかに減衰する.

　入力の多重数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L\, } とそれに比例して出力率, 閾値を増加させたときの溢れ確率 ${\mbox{P}}(Q^{L}>Ly)\,$も同様な考え方で漸近解析が行なわれている [2]. 多重数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L\, } の入力率は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L\, } 個の入力率構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X_n^{(l)}, l=1, \cdots, L\, } を単純に足したものである. 結果だけを記述すると任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y>0\, } に対して

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lim_{L\rightarrow \infty}L^{-1}\log \mbox{P}(Q^L>Ly)= -\inf_{n>0}\psi^{*}_n (y) \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (5)\, }

となる. 但し, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \psi_n (\theta)= \lim_{L\rightarrow \infty} L^{-1}\log \mbox{E}[\mathrm{e}^{\theta A_n^L}]\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \psi_n^{*}(y)\equiv\sup_{\theta}\{\theta y - \psi_n (\theta)\}\, } である.

　本結果も，長期依存型入力に適用できる.

　以上, 離散時間の場合を議論してきたが, 連続時間のモデルに対しても同様な結果が得られる. なお，本内容については参考文献 [4] にも書かれている.

---

参考文献

[1] A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Jones and Bartlett Publishers, 1993.

[2] N. G. Duffield, "Economies of Scale for Long-Range Dependent Traffic in Short Buffers," Telecommunication Systems, 7 (1997), 267-280.

[3] N. G. Duffield and N. O'Connell, "Large Deviations and Overflow Probabilities for the General Single-Server Queue, with Ppplications," Mathematical Proceedings of the Cambridge Philosophical Society, 118 (1995), 363-374.

[4] A. Ganesh, N. O'Connell and D. Wischik, Big Queues, Springer, 2004.

[5] 小林和朝, 「マルチメディア情報流に対する流体近似」, 『応用数理』, 9 (1999), 46-59.