《待ち行列に対するアルゴリズム的解法》 - 版の履歴

2007年8月9日 (木) 10:30にOrsjwikiによる

2007-08-09T10:30:49Z

2007年8月9日 (木) 10:29にOrsjwikiによる

2007-08-09T10:29:48Z

2007年8月9日 (木) 10:21にOrsjwikiによる

2007-08-09T10:21:00Z

2007年8月9日 (木) 07:42にSakasegawaによる

2007-08-09T07:42:01Z

2007年8月9日 (木) 07:40にSakasegawaによる

2007-08-09T07:40:48Z

2007年8月9日 (木) 07:29にSakasegawaによる

2007-08-09T07:29:29Z

差分を表示

2007年8月9日 (木) 07:08にSakasegawaによる

2007-08-09T07:08:30Z

2007年8月9日 (木) 06:28にSakasegawaによる

2007-08-09T06:28:16Z

差分を表示

2007年8月9日 (木) 06:20にSakasegawaによる

2007-08-09T06:20:56Z

2007年8月8日 (水) 15:30にTetsuyatominagaによる

2007-08-08T15:30:23Z

差分を表示

← 古い版		2007年8月9日 (木) 10:30時点における版
321行目:		321行目:

	[8] 滝根哲哉，「構造化されたマルコフ連鎖と待ち行列」, 『システム／制御／情報』， '''43''' (1999), 135--140.		[8] 滝根哲哉，「構造化されたマルコフ連鎖と待ち行列」, 『システム／制御／情報』， '''43''' (1999), 135--140.
		+
		+	[[category:待ち行列\|まちぎょうれつにたいするあるごりずむてきかいほう]]

@@ 1行目: / 1行目: @@
 '''【まちぎょうれつにたいするあるごりずむてきかいほう(algorithmic solution of queues)】'''
-'''7.1 背景'''
+'''背景'''
 　従来の待ち行列研究では，多くのモデルに共通する普遍的性質の解明や各種モデルにおける陽な解の導出に主眼が置かれていたが，計算機が身近になると共に，数値計算による待ち行列モデルの分析を意図する研究が活発になってきた[6]．ここで共通する考え方は，(i) 待ち行列の挙動を，系内客数を表す変数と系の挙動を表現するために必要な補助的な変数の組で構成される２変数マルコフ連鎖で定式化し，(ii) その２変数マルコフ連鎖がもつ構造に注目して，マルコフ連鎖の定常分布を計算するための数値計算アルゴリズムを構築する，と言うものである[3, 7, 8]．このようなアプローチをアルゴリズム的解法（algorithmic solution）あるいは行列解析法（matrix-analytic method）と呼ぶ．
-'''7.2 相型分布とMAP'''
+'''相型分布とMAP'''
 　状態 0 が吸収状態，状態 <math>i \in M =\{1,2,\ldots,M\}\,</math> が一時的状態である連続時間有限状態吸収マルコフ連鎖 <math>X(t)\,</math> を考える．このとき <math>X(t)\,</math> の推移率行列は
@@ 29行目: / 29行目: @@
 <math>\mathbf{\pi}</math> を <math>\mathbf{\pi} (\mathbf{C} + \mathbf{D}) = {\mathbf 0}</math> を満たす確率ベクトルとしたとき，定常な MAP における客の到着間隔分布は <math>F(x)=1- \mathbf{\pi} \mathbf{D} \exp(\mathbf{C}x) \mathbf{e} / \mathbf{\pi} \mathbf{D} \mathbf{e}</math> となり，その平均は <math>1/\mathbf{\pi}\mathbf{D}\mathbf{e}</math> で与えられる．MAP はあらゆる定常点過程を任意の精度で近似できることが知られており，マルコフ変調ポワソン過程（Markov modulated Poisson process）や独立な相型再生過程の重畳などを特別な場合として含む．特に到着間隔が独立同一な表現 <math>(\mathbf{\alpha},\mathbf{T})</math> をもつ相型分布に従う場合は <math>\mathbf{C}=\mathbf{T}</math>, <math>\mathbf{D} =-\mathbf{T} \mathbf{e} \mathbf{\alpha}</math> である．
-'''7.3 準出生死滅過程'''
+'''準出生死滅過程'''
 　到着間隔ならびにサービス時間がそれぞれ表現 (<math>\mathbf{\alpha}_A, \mathbf{T}_A\,</math>) ならびに表現 (<math>\mathbf{\alpha}_B, \mathbf{T}_B\,</math>) をもつ相型分布に従う PH/PH/1 待ち行列を考える．時刻 <math>t\,</math> における客数を <math>L(t)\,</math>，到着間隔が従う相型分布の相を <math>S_A(t)\,</math>，サービス中の場合はサービス時間が従う相型分布の相を <math>S_B(t)\,</math> とする．このとき，システムの状態は <math>(L(t), S_A(t),S_B(t))\,</math> で表される．ただし <math>L(t)=0\,</math> のときは <math>S_B(t)=0\,</math> とする．
@@ 135行目: / 135行目: @@
 に基づいて，<math>\mathbf{R}_0=\mathbf{O}\,</math> を初期値として順次 <math>\mathbf{R}_n\,</math> を求めるというものである．このとき <math>\mathbf{R}_n\,</math> は要素毎に単調に増加し，公比行列 <math>\mathbf{R}\,</math> に収束することが知られている．
-'''7.4 G/M/1型マルコフ連鎖'''
+'''G/M/1型マルコフ連鎖'''
 　客の到着間隔 <math>G\,</math> が独立で同一な分布 <math>G(x)=\Pr(G \leq x)\,</math> に従い，サービス時間が表現 (<math>\mathbf{\alpha}_B, \mathbf{T}_B\,</math>) をもつ相型分布に従う GI/PH/1 待ち行列を考える．<math>n\,</math> 番目の客の到着直前の系内客数を <math>X_n\,</math>，十
@@ 214行目: / 214行目: @@
 に基づいて，<math>\mathbf{R}_0=\mathbf{O}\,</math> を初期値として順次 <math>\mathbf{R}_n\,</math> を求めるというものである．このとき <math>\mathbf{R}_n\,</math> は要素毎に単調に増加し，公比行列 <math>\mathbf{R}\,</math> に収束することが知られている．
-'''7.5 M/G/1型マルコフ連鎖'''
+'''M/G/1型マルコフ連鎖'''
 　客の到着が表現 <math>(\mathbf{C},\mathbf{D})\,</math> をもつ MAP に従い，サービス時間 <math>H\,</math> が独立で同一な分布 <math>H(x)=\Pr(H \leq x)\,</math> に従うMAP/G/1 待ち行列を考える．<math>n\,</math> 番目の客のサービス終了直後の系内客数を <math>Y_n\,</math>，<math>n\,</math> 番目のサービス中に新たに到着する客数を <math>A_n\,</math> とすると

@@ 53行目: / 53行目: @@
 </center>
 ここで <math>\mathbf{Q}_m\,</math> ならびに <math>\overline{\mathbf{Q}}_m\,</math> (<math>m=1,2,3\,</math>)はクロネッカー積 <math>\otimes\,</math>，クロネッカー和 <math>\oplus\,</math> を用いて次式で与えられる．
 \mathbf{Q}_0 = (-\mathbf{T}_A) \mathbf{e} \mathbf{\alpha}_A \otimes \mathbf{I}_B,
+&
@@ 68行目: / 91行目: @@
+&
 \overline{\mathbf{Q}}_2 = \mathbf{I}_A \otimes (-\mathbf{T}_B)\mathbf{e}
-</math>
+-->
-</center>
 ただし <math>\mathbf{I}_X\,</math> (<math>X=A,B\,</math>) は <math>M_X\,</math> 次元の単位行列である．

@@ 167行目: / 167行目: @@
 <math>
 \mathbf{x}_k = \mathbf{x}_0 \mathbf{R}^k, \quad k=1,2,\ldots
-\, </math>　　　　　<math>(3)\,</math>
+\, </math>　　　　　<math>(4)\,</math>
 </center>
 で与えられる．さらに <math>\mathbf{x}_0\,</math> は
@@ 239行目: / 239行目: @@
 <math>
 \mathbf{G}=\sum_{k=0}^{\infty} \mathbf{A}_k \mathbf{G}^k
 \, </math>　　　　　<math>(5)\,</math>
 </center>

@@ 78行目: / 78行目: @@
 　エルゴード的な準出生死滅過程 <math>(L(t),S(t))\,</math> の定常分布を <math>\mathbf{q} =(\mathbf{q}_0, \mathbf{q}_1, \ldots)\,</math> とする．定常分布 <math>\mathbf{q}\,</math> は <math>\mathbf{q} \mathbf{Q}={\mathbf 0}\,</math> を満たすことに注意．このとき，
 <center>
 <math>
 \mathbf{Q}_0 + \mathbf{R}\mathbf{Q}_1 + \mathbf{R}^2 \mathbf{Q}_2 = \mathbf{O}
-\label{rate-matrix-QBD}
+\, </math>　　　　　<math>(1)\,
 </math>
 </center>
 を満たす最小の非負行列 <math>\mathbf{R}\,</math> を用いて <math>\mathbf{q}_k\,</math> (<math>k=2,3,\ldots\,</math>) は
 <center>
 <math>
 \mathbf{q}_k = \mathbf{q}_1 \mathbf{R}^{k-1}, \quad k=2,3,\ldots
-\label{matrix-geometric-QBD}
+\, </math>　　　　　<math>(2)\,</math>
 </center>
 で与えられる．さらに <math>\mathbf{q}_0\,</math>, <math>\mathbf{q}_1\,</math> は
@@ 164行目: / 160行目: @@
 <math>
 \mathbf{R} = \sum_{k=0}^{\infty} \mathbf{R}^k \mathbf{B}_k
-\label{rate-matrix-GM1}
+\, </math>　　　　　<math>(3)\,</math>
 </center>
 を満たす最小の非負行列 <math>\mathbf{R}\,</math> を用いて <math>\mathbf{x}_k\,</math> (<math>k=1,2,\ldots\,</math>) は
+<center>
-\begin{equation}
+<math>
 \mathbf{x}_k = \mathbf{x}_0 \mathbf{R}^k, \quad k=1,2,\ldots
-\label{matrix-geometric-GM1}
+\, </math>　　　　　<math>(3)\,</math>
 </center>
 で与えられる．さらに <math>\mathbf{x}_0\,</math> は
@@ 247行目: / 238行目: @@
 <center>
 <math>
 \mathbf{G}=\sum_{k=0}^{\infty} \mathbf{A}_k \mathbf{G}^k
 \label{matrix-G}
 \end{equation}
-</math>
+\, </math>　　　　　<math>(5)\,</math>
 </center>
 を満たす確率行列を <math>\mathbf{G}\,</math> とし，<math>\mathbf{K}=\sum_{k=0}^{\infty}\overline{\mathbf{A}}_k \mathbf{G}^k\,</math> を定義する．行列 <math>\mathbf{K}\,</math> は確率行列であることに注意．このとき <math>\mathbf{\kappa} = \mathbf{\kappa} \mathbf{K}\,</math>を満たす確率ベクトル <math>\mathbf{\kappa}\,</math> を用いて <math>\mathbf{y}_0\,</math> は次式で与えられる．

@@ 23行目: / 23行目: @@
 　表現 <math>(\mathbf{\alpha}, \mathbf{T})</math> をもつ相型分布を用いて客の到着間隔の列，すなわち相型再生過程（phase-type renewal process）を生成するには次のようにすればよい．時刻 0 において初期状態分布 <math>(0,\mathbf{\alpha})</math> に従い相を選ぶ．その後初めて吸収が起こったとき，1 番目の客が到着する．一般に，<math>n</math> 番目（<math>n=1,2,\ldots</math>）の客の到着が起こると，直ちに過去の履歴とは独立に初期状態分布 <math>(0, \mathbf{\alpha})</math> に従い相を選び，その後吸収が起こった時点で <math>n+1</math> 番目の客が到着する．このようにして生成された客の到着間隔は独立で同一な確率変数列となる．
-　相型分布に従う確率変数の列に対して相関を導入可能にしたものにマルコフ型到着過程（Markovian arrival process：MAP）がある[2, 3]．相型分布を用いた確率変数列の生成では，到着が起こる度に過去の履歴とは独立に初期分布を選んでいたが，MAP では一時的状態 <math>i \in \M</math> から吸収されたとき，確率 <math>p_{i,j}</math> (<math>j \in \M</math>) で次の初期状態 <math>j</math> を選ぶ．ただし，全ての <math>i \in \M</math> に対して<math>\sum_{j \in \M} p_{i,j} =1<math> である．
+　相型分布に従う確率変数の列に対して相関を導入可能にしたものにマルコフ型到着過程（Markovian arrival process：MAP）がある[2, 3]．相型分布を用いた確率変数列の生成では，到着が起こる度に過去の履歴とは独立に初期分布を選んでいたが，MAP では一時的状態 <math>i \in M</math> から吸収されたとき，確率 <math>p_{i,j}\,</math> (<math>j \in M</math>) で次の初期状態 <math>j\,</math> を選ぶ．ただし，全ての <math>i \in M</math> に対して<math>\sum_{j \in M} p_{i,j} =1</math> である．
-　通常，MAP は二つの <math>M \times M</math> 行列 <math>\mathbf{C},\mathbf{D}</math> を用いて表現される．ここで行列 <math>\mathbf{C}</math> は一時的状態間の推移を表し，相型分布の行列 <math>\mathbf{T}</math> に対応する．一方，行列 <math>\mathbf{D}</math> の <math>(i,j)</math> 要素は状態 <math>i</math> で吸収が起こり，次の初期状態が <math>j</math> である率 <math>[-\mathbf{C}\mathbf{e}]_i p_{i,j}</math> で与えられる．なお，<math>\mathbf{C}+\mathbf{D}</math> は規約であり，<math>\mathbf{D} \neq \mathbf{O}</math> である．<math>\mathbf{\pi}</math> を <math>\mathbf{\pi} (\mathbf{C} + \mathbf{D}) = {\bf 0}</math> を満たす確率ベクトルとしたとき，定常な MAP における客の到着間隔分布は <math>F(x)=1- \mathbf{\pi} \mathbf{D} \exp(\mathbf{C}x) \mathbf{e} / \mathbf{\pi} \mathbf{D} \mathbf{e}</math> となり，その平均は <math>1/\mathbf{\pi}\mathbf{D}\mathbf{e}</math> で与えられる．MAP はあらゆる定常点過程を任意の精度で近似できることが知られており，マルコフ変調ポワソン過程（Markov modulated Poisson process）や独立な相型再生過程の重畳などを特別な場合として含む．特に到着間隔が独立同一な表現 <math>(\mathbf{\alpha},\mathbf{T})</math> をもつ相型分布に従う場合は <math>\mathbf{C}=\mathbf{T}</math>, <math>\mathbf{D} =-\mathbf{T} \mathbf{e} \mathbf{\alpha}</math> である．
+　通常，MAP は二つの <math>M \times M</math> 行列 <math>\mathbf{C},\mathbf{D}</math> を用いて表現される．ここで行列 <math>\mathbf{C}</math> は一時的状態間の推移を表し，相型分布の行列 <math>\mathbf{T}</math> に対応する．一方，行列 <math>\mathbf{D}</math> の <math>(i,j)</math> 要素は状態 <math>i</math> で吸収が起こり，次の初期状態が <math>j</math> である率 <math>[-\mathbf{C}\mathbf{e}]_i p_{i,j}</math> で与えられる．なお，<math>\mathbf{C}+\mathbf{D}</math> は規約であり，<math>\mathbf{D} \neq \mathbf{O}</math> である．
 '''7.3 準出生死滅過程'''
@@ 69行目: / 70行目: @@
 　上記の２変数マルコフ連鎖 <math>(L(t),S(t))\,</math> は次の性質をもつ．(i) 境界部分を除いて空間的に同質（例えばレベルが1以上（<math>L(t) \geq 1\,</math>）のとき，一回の推移でレベルが一つ増加する率は <math>\mathbf{Q}_0\,</math> の要素で与えられる），(ii) 一回の推移でレベルは高々一つしか増減しない．このような性質をもつ２変数連続時間マルコフ連鎖を準出生死滅過程（quasi birth-and-death process:QBD）という[1, 3, 4]．
-　推移率行列 <math>\mathbf{Q}\,</math> をもつ準出生死滅過程において <math>\mathbf{Q}_*=\mathbf{Q}_0+\mathbf{Q}_1+\mathbf{Q}_2\,</math> が規約である場合，<math>\mathbf{\eta}\mathbf{Q}_*={\bf0}\,</math>, <math>\mathbf{\eta}\mathbf{e}=1\,</math> なる正のベクトル <math>\mathbf{\eta}\,</math> が一意に定まり，<math>\mathbf{\eta}\mathbf{Q}_2\mathbf{e} > \mathbf{\eta}\mathbf{Q}_0\mathbf{e}\,</math> のとき準出生死滅過程 <math>(L(t),S(t))\,</math> はエルゴード的となる．PH/PH/1 待ち行列の場合，この条件は平均到着間隔 <math>\mathbf{\alpha}_A (-\mathbf{T}_A)^{-1}\mathbf{e}\,</math> が平均サービス時間 <math>\mathbf{\alpha}_B (-\mathbf{T}_B)^{-1}\mathbf{e}\,</math> より大きいことと等価である．
+　推移率行列 <math>\mathbf{Q}\,</math> をもつ準出生死滅過程において <math>\mathbf{Q}_*=\mathbf{Q}_0+\mathbf{Q}_1+\mathbf{Q}_2\,</math> が規約である場合，<math>\mathbf{\eta}\mathbf{Q}_*={\mathbf0}\,</math>, <math>\mathbf{\eta}\mathbf{e}=1\,</math> なる正のベクトル <math>\mathbf{\eta}\,</math> が一意に定まり，<math>\mathbf{\eta}\mathbf{Q}_2\mathbf{e} > \mathbf{\eta}\mathbf{Q}_0\mathbf{e}\,</math> のとき準出生死滅過程 <math>(L(t),S(t))\,</math> はエルゴード的となる．PH/PH/1 待ち行列の場合，この条件は平均到着間隔 <math>\mathbf{\alpha}_A (-\mathbf{T}_A)^{-1}\mathbf{e}\,</math> が平均サービス時間 <math>\mathbf{\alpha}_B (-\mathbf{T}_B)^{-1}\mathbf{e}\,</math> より大きいことと等価である．
-　エルゴード的な準出生死滅過程 <math>(L(t),S(t))\,</math> の定常分布を <math>\mathbf{q} =(\mathbf{q}_0, \mathbf{q}_1, \ldots)\,</math> とする．定常分布 <math>\mathbf{q}\,</math> は <math>\mathbf{q} \mathbf{Q}={\bf 0}\,</math> を満たすことに注意．このとき，
+　エルゴード的な準出生死滅過程 <math>(L(t),S(t))\,</math> の定常分布を <math>\mathbf{q} =(\mathbf{q}_0, \mathbf{q}_1, \ldots)\,</math> とする．定常分布 <math>\mathbf{q}\,</math> は <math>\mathbf{q} \mathbf{Q}={\mathbf 0}\,</math> を満たすことに注意．このとき，
+%
 \begin{equation}
@@ 145行目: / 146行目: @@
 一つしか増加しない．このような性質をもつ２変数離散時間マルコフ連鎖をG/M/1型（Markov chain of G/M/1 type）と呼ぶ[3, 4, 7, 8]．
-　遷移確率行列 <math>\mathbf{P}_{\rm G/M/1}\,</math> をもつG/M/1型マルコフ連鎖において，<math>\mathbf{B}=\sum_{k=0}^{\infty} \mathbf{B}_k\,</math> が規約である場合，<math>\mathbf{b}\mathbf{B}=\mathbf{b}\,</math>，<math>\mathbf{b}\mathbf{e}=1\,</math> となるような正のベクトル <math>\mathbf{b}\,</math> が一意に定まり，<math>\sum_{k=2}^{\infty} (k-1)\mathbf{b}\mathbf{B}_k\mathbf{e} > \mathbf{b}\mathbf{B}_0\mathbf{e}\,</math> ならば G/M/1型マルコフ連鎖はエルゴード的である．GI/PH/1 待ち行列の場合，この条件は平均到着間隔 <math>\E[G]\,</math> が平均サービス時間 <math>\mathbf{\alpha}_B(-\mathbf{T}_B)^{-1}\mathbf{e}\,</math> より大きいことと等価である．
+　遷移確率行列 <math>\mathbf{P}_{\rm G/M/1}\,</math> をもつG/M/1型マルコフ連鎖において，<math>\mathbf{B}=\sum_{k=0}^{\infty} \mathbf{B}_k\,</math> が規約である場合，<math>\mathbf{b}\mathbf{B}=\mathbf{b}\,</math>，<math>\mathbf{b}\mathbf{e}=1\,</math> となるような正のベクトル <math>\mathbf{b}\,</math> が一意に定まり，<math>\sum_{k=2}^{\infty} (k-1)\mathbf{b}\mathbf{B}_k\mathbf{e} > \mathbf{b}\mathbf{B}_0\mathbf{e}\,</math> ならば G/M/1型マルコフ連鎖はエルゴード的である．GI/PH/1 待ち行列の場合，この条件は平均到着間隔 <math>E[G]\,</math> が平均サービス時間 <math>\mathbf{\alpha}_B(-\mathbf{T}_B)^{-1}\mathbf{e}\,</math> より大きいことと等価である．
-　エルゴード的なG/M/1型マルコフ連鎖 <math>(X_n,S_n^-)\,</math> の定常分布を <math>\mathbf{x}=(\mathbf{x}_0, \mathbf{x}_1, \ldots)\,</math> とする．定常分布 <math>\mathbf{x}\,</math> は <math>\mathbf{x} = \mathbf{x} \mathbf{P}_{\rm G/M/1}\,</math> を満たすことに注意．このとき，
+　エルゴード的なG/M/1型マルコフ連鎖 <math>(X_n,S_n^-)\,</math> の定常分布を <math>\mathbf{x}=(\mathbf{x}_0, \mathbf{x}_1, \ldots)\,</math> とする．定常分布 <math>\mathbf{x}\,</math> は <math>\mathbf{x} = \mathbf{x} \mathbf{P}_{\mathrm G/M/1}\,</math> を満たすことに注意．このとき，
+%
 \begin{equation}
@@ 189行目: / 190行目: @@
 \]
+%
-が成立する．よって <math>n\,</math> 番目のサービス直後における客の到着が従うMAPの相を <math>S_n^+\,</math> とすると，<math>(Y_n, S_n^+)\,</math> は下記の遷移確率行列 <math>\mathbf{P}_{\rmM/G/1}\,</math> をもつ２変数離散時間マルコフ連鎖となる．
+が成立する．よって <math>n\,</math> 番目のサービス直後における客の到着が従うMAPの相を <math>S_n^+\,</math> とすると，<math>(Y_n, S_n^+)\,</math> は下記の遷移確率行列 <math>\mathbf{P}_{\mathrm M/G/1}\,</math> をもつ２変数離散時間マルコフ連鎖となる．
+%
 \[
@@ 221行目: / 222行目: @@
 ルは高々一つしか減少しない．このような性質をもつ２変数離散時間マルコフ連鎖をM/G/1型（Markov chain of M/G/1 type）と呼ぶ[3, 5, 7, 8]．
-　遷移確率行列 <math>\mathbf{P}_{\rm M/G/1}\,</math> をもつM/G/1型マルコフ連鎖において，<math>\mathbf{A}=\sum_{k=0}^{\infty} \mathbf{A}_k\,</math> が規約である場合，<math>\mathbf{a}\mathbf{A}=\mathbf{a}\,</math>，<math>\mathbf{a}\mathbf{e}=1\,</math> となるような正のベクトル <math>\mathbf{a}\,</math> が一意に定まり，<math>\sum_{k=1}^{\infty} k \mathbf{a}\mathbf{A}_k \mathbf{e}< 1\,</math> かつ <math>\sum_{k=1}^{\infty} k \overline{\mathbf{A}}_k \mathbf{e}\,</math> の各要素が有限ならば M/G/1型マルコフ連鎖はエルゴード的である．MAP/G/1 待ち行列の場合，この条件は平均到着間隔 <math>1/\mathbf{\pi}\mathbf{D}\mathbf{e}\,</math> が平均サービス時間 <math>\E[H]\,</math> より大きいことと等価である．
+　遷移確率行列 <math>\mathbf{P}_{\mathrm M/G/1}\,</math> をもつM/G/1型マルコフ連鎖において，<math>\mathbf{A}=\sum_{k=0}^{\infty} \mathbf{A}_k\,</math> が規約である場合，<math>\mathbf{a}\mathbf{A}=\mathbf{a}\,</math>，<math>\mathbf{a}\mathbf{e}=1\,</math> となるような正のベクトル <math>\mathbf{a}\,</math> が一意に定まり，<math>\sum_{k=1}^{\infty} k \mathbf{a}\mathbf{A}_k \mathbf{e}< 1\,</math> かつ <math>\sum_{k=1}^{\infty} k \overline{\mathbf{A}}_k \mathbf{e}\,</math> の各要素が有限ならば M/G/1型マルコフ連鎖はエルゴード的である．MAP/G/1 待ち行列の場合，この条件は平均到着間隔 <math>1/\mathbf{\pi}\mathbf{D}\mathbf{e}\,</math> が平均サービス時間 <math>E[H]\,</math> より大きいことと等価である．
 　エルゴード的なM/G/1型マルコフ連鎖 <math>(Y_n,S_n^+)\,</math> の定常分布を <math>\mathbf{y}=(\mathbf{y}_0, \mathbf{y}_1, \ldots)\,</math> とする．定常分布 <math>\mathbf{y}\,</math> は <math>\mathbf{y} = \mathbf{y} \mathbf{P}_{\rm M/G/1}\,</math> を満たすことに注意．ここで

@@ 7行目: / 7行目: @@
 '''7.2 相型分布とMAP'''
-　状態 0 が吸収状態，状態 <math>i \in \M =\{1,2,\ldots,M\}</math> が一時的状態である連続時間有限状態吸収マルコフ連鎖 <math>X(t)</math> を考える．このとき <math>X(t)</math> の推移率行列は
+　状態 0 が吸収状態，状態 <math>i \in M =\{1,2,\ldots,M\}\,</math> が一時的状態である連続時間有限状態吸収マルコフ連鎖 <math>X(t)\,</math> を考える．このとき <math>X(t)\,</math> の推移率行列は
+%
 \[
@@ 17行目: / 17行目: @@
 \]
+%
-の形に書ける．ただし <math>\bm{e}</math> はすべての要素が 1 の列ベクトルである．このマルコフ連鎖の初期状態分布を <math>(0, \bm{\alpha})</math> としたとき，<math>X(t)</math> が吸収されるまでの時間は <math>(0,\infty)</math> 上の確率分布を定め，これを表現<math>(\bm{\alpha}, \bm{T})</math> をもつ相型分布（phase-type distribution）という[1, 4]．以下ではマルコフ連鎖 <math>X(t)</math> の一時的状態を相と呼ぶ．
+の形に書ける．ただし <math>\mathbf{e}</math> はすべての要素が 1 の列ベクトルである．このマルコフ連鎖の初期状態分布を <math>(0, \mathbf{\alpha})</math> としたとき，<math>X(t)</math> が吸収されるまでの時間は <math>(0,\infty)</math> 上の確率分布を定め，これを表現<math>(\mathbf{\alpha}, \mathbf{T})</math> をもつ相型分布（phase-type distribution）という[1, 4]．以下ではマルコフ連鎖 <math>X(t)</math> の一時的状態を相と呼ぶ．
-　定義より，表現 <math>(\bm{\alpha}, \bm{T})</math> をもつ相型分布の分布関数は <math>F(x) = 1 - \bm{\alpha} \exp(\bm{T} x) \bm{e}</math> となり，その平均は<math>\bm{\alpha} (-\bm{T})^{-1}\bm{e}</math> である．相の数 <math>M</math> を十分に大きく取ることにより，相型分布は <math>(0,\infty)</math> で定義されたあらゆる確率分布を任意の精度で近似できることが知られており，指数分布，アーラン分布，超指数分布など，待ち行列で頻繁に用いられる確率分布を特別な場合として含む．
+　定義より，表現 <math>(\mathbf{\alpha}, \mathbf{T})\,</math> をもつ相型分布の分布関数は <math>F(x) = 1 - \mathbf{\alpha} \exp(\mathbf{T} x) \mathbf{e}</math> となり，その平均は<math>\mathbf{\alpha} (-\mathbf{T})^{-1}\mathbf{e}</math> である．相の数 <math>M</math> を十分に大きく取ることにより，相型分布は <math>(0,\infty)</math> で定義されたあらゆる確率分布を任意の精度で近似できることが知られており，指数分布，アーラン分布，超指数分布など，待ち行列で頻繁に用いられる確率分布を特別な場合として含む．
 　表現 <math>(\bm{\alpha}, \bm{T})</math> をもつ相型分布を用いて客の到着間隔の列，すなわち相型再生過程（phase-type renewal process）を生成するには次のようにすればよい．時刻 0 において初期状態分布 <math>(0,\bm{\alpha})</math> に従い相を選ぶ．その後初めて吸収が起こったとき，1 番目の客が到着する．一般に，<math>n</math> 番目（<math>n=1,2,\ldots</math>）の客の到着が起こると，直ちに過去の履歴とは独立に初期状態分布 <math>(0, \bm{\alpha})</math> に従い相を選び，その後吸収が起こった時点で <math>n+1</math> 番目の客が到着する．このようにして生成された客の到着間隔は独立で同一な確率変数列となる．