カテゴリーアーカイブ: 待ち行列理論

PASTA (Poisson Arrivals See Time Averages) (2)

投稿日: 作成者:

今回は，PASTA (Poisson Arrival See Time Averages)を数学的に表現し，定理の形で述べることにします[1,2]。

N \equiv \{ N(t) \}_{t \geq 0}を，ある状態空間上の値を取る確率過程とします。
この確率過程のことを「システム」と呼ぶことにします。
BをNの状態空間の任意の集まりとします。
さらに，率\lambda>0のポアソン過程\Lambda \equiv \{ \Lambda(t) \}_{t \geq 0}を考えます。このポアソン過程とシステムの間には，相互作用があるものとします。
その相互作用は，たとえば，待ち行列システムへの適用においては，Nをシステム内客数を表す確率過程，\Lambdaを客のシステムへの到着を表すポアソン過程と考えて，客の各到着時点でNが1だけ増加するというような相互作用です。

 

システムがBにある時間の割合とシステムがBにあるのを見る到着の割合を考えます。この目的のためにt \geq 0で以下のものを定義します。

U(t) = 1_{\{ N(t) \in B \}}

\overline{U}(t) = \frac{1}{t} \int_{0}^{t} U(s) \; ds

A(t) = \int_{0}^{t} U(s) \; d \Lambda(s)

\overline{A}(t) = \frac{A(t)}{\Lambda(t)}

Uのサンプルパスは，確率1で左連続で右極限を持つとします。
この左連続性は，上記の待ち行列システムの例で言えば，到着がシステム内客数に影響を及ぼすのは(すなわちシステム内客数が+1されるのは)，その到着直後であると考えることに相当します。

上記の定義で，\overline{U}(t)はシステムNが[0,t]の間にBにある時間割合を示し，\overline{A}(t)は[0,t]の間に発生する到着でシステムNがBにあることを見る到着の割合を示しています。

到着は何らかの形でシステムに影響を及ぼすことを想定しているので，\LambdaとN，したがって，\LambdaとUは依存した確率過程になります。しかし，どのような形での相互作用や影響を許すわけではありません。ここでは，システムが予見(anticipation)を持たない，すなわち，\Lambdaの将来の増分とUの履歴が独立であることを仮定します。この仮定はLAA (Lack of Anticipation Assumption)と呼ばれ，きっちり書くと以下のようになります。

仮定　Lack of Anticipation Assumption (LAA).
各t \geq 0において，\{ \Lambda(t+u) - \Lambda(t): \; u \geq 0 \}は，\{U(s): \; 0 \leq s \leq t \}と独立である。

 

このLAAのもとで，以下の定理が成立します。

定理 PASTA.
LAAのもとで，t \rightarrow \inftyのとき，\overline{U}(t) \rightarrow \overline{U}(\infty) w.p.1 ならば，かつそのときに限り，\overline{A}(t) \rightarrow \overline{U}(\infty) w.p.1である。

 

以下に仮定と定理に関するコメントを述べます。

1. \overline{U}(\infty)は，システムがエルゴード的であるような場合には定数になりますが，そうである必要はありません。例えば，システムNが吸収状態をいくつかもつ連続時間マルコフ連鎖であるとし，システムの初期状態N(0)=iは過渡状態であるとします。ここでBがある吸収状態であれば，\overline{U}(\infty)は確率変数になり，Bの吸収状態に吸収されれば\overline{U}(\infty)=1，そうでなければ\overline{U}(\infty)=0となります。

2. Wolffの本[1]においては，LAAに上記の仮定に加えて，各t \geq 0において，\{ \Lambda(t+u) - \Lambda(t): \; u \geq 0 \}が\{ \Lambda(s): 0 \leq s \leq t \}と独立であるという，\Lambdaに関する独立増分性が仮定されています。
しかしながら，この仮定は，\Lambdaがポアソン過程のとき独立増分性を持つので，本来不要です。そのため，このブログにおけるLAAは[3]に記述のあるLAAと同様のものをLAAとして記述してあります。このブログに記述してあるLAAはPASTAが成立するための十分条件になります。

次回から，数回に分けて定理 PASTAを証明します。

 

[参考文献]
[1] R.W.Wolff, Stochastic modeling and the theory of queues, Prentice-Hall, 1989.
[2] R.W.Wolff, “Poisson Arrivals See Time Averages,” Operations Research, vol.33,
pp.223-231, 1982.
[3] B.Melamed and D.D.Yao, “The ASTA property,” in Frontiers in queueing: models and problems, (J.Dshalalow, Ed), CRC press, 1995.

PASTA (Poisson Arrivals See Time Averages) (1)

投稿日: 作成者:

これから何回かに分けてPASTAについて議論したいと思います。
PASTAと言っても，私が大好きでよく食べる食物のパスタのことではありません^^;;
ここで言うPASTAとは，待ち行列理論においてよく知られているポアソン到着に関する性質、
「Poisson Arrivals See Time Averages」，略してPASTAと呼ばれる性質のことです。

PASTAとは，大まかに簡単に言うと

定常ポアソン到着が，到着時にシステムの状態がある状態にあることを
観察する割合は，システムがそのある状態にある時間割合に一致する

ということになります。言い換えると，PASTAとは，

定常ポアソン過程の増加点でシステムを観測したとき
観測時点直前での事象平均は，時間平均に一致する

という性質のことです。

 
PASTAは，待ち行列の解析においては，到着が定常ポアソン過程にしたがう待ち行列システムにおいて，待ち行列長の定常分布を客の到着直前の待ち行列長の分布に関連付けるためによく使われます。
待ち行列システムの解析おいては，待ち行列長の定常分布を得ることの方が客の待ち時間の分布を得ることよりも簡単であることが多いです。そのため，まず解析によって，待ち行列長の定常分布を得て，それにPASTAを適用して，客の到着直前の待ち行列長の分布を得て，そこから客の待ち時間の分布を得るというアプローチがよくとられます。

 

次回から，数学的な定式化をきっちり行ってPASTAについて議論したいと思います。