「出生死滅過程」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(4人の利用者による、間の4版が非表示)
1行目: 1行目:
 
'''【しゅっしょうしめつかてい (birth and death process)】'''
 
'''【しゅっしょうしめつかてい (birth and death process)】'''
 +
 +
=== 概要 ===
  
 
状態空間 <math>\{0, 1, ...\}\,</math> 上の連続時間マルコフ連鎖 <math>\{X(t)\}\,</math> で, 推移速度行列 <math>Q = (q_{ij})\,</math> が次で与えられる確率過程.  
 
状態空間 <math>\{0, 1, ...\}\,</math> 上の連続時間マルコフ連鎖 <math>\{X(t)\}\,</math> で, 推移速度行列 <math>Q = (q_{ij})\,</math> が次で与えられる確率過程.  
9行目: 11行目:
 
\left\{
 
\left\{
 
\begin{array}{l}\\\\\\\\\\\\\end{array} \right. </math> </td>  
 
\begin{array}{l}\\\\\\\\\\\\\end{array} \right. </math> </td>  
<td><math>\lambda_i,\,</math></td><td><math>i \geq 0\,</math></td><td>かつ</td><td><math>j=i+1\,</math></td>  
+
<td><math>\lambda_i,\,</math></td><td><math>i \geq 0\,</math> かつ <math>j=i+1\,</math></td>  
 
</tr>  
 
</tr>  
 
<tr>  
 
<tr>  
<td><math>\mu_i,\,</math></td><td><math>i \geq 1\,</math></td><td>かつ</td><td><math>j=i-1\,</math></td>  
+
<td><math>\mu_i,\,</math></td><td><math>i \geq 1\,</math> かつ <math>j=i-1\,</math></td>  
 
</tr>  
 
</tr>  
 
<tr>  
 
<tr>  
<td><math>-\lambda_0,\,</math></td><td><math>i=j=0\,</math></td><td></td><td></td>  
+
<td><math>-\lambda_0,\,</math></td><td><math>i=j=0\,</math></td>
 
</tr>  
 
</tr>  
 
<tr>  
 
<tr>  
<td><math>-(\lambda_i+\mu_i),\,</math></td><td><math>i\ge 1\,</math></td><td>かつ</td><td><math>j=i\,</math></td>
+
<td><math>-(\lambda_i+\mu_i),\,</math></td><td><math>i\ge 1\,</math> かつ <math>j=i\,</math></td>
 
</tr>  
 
</tr>  
 
<tr>  
 
<tr>  
<td><math>0,\,</math></td><td>その他</td><td></td><td></td><td></td>  
+
<td><math>0,\,</math></td><td>その他</td>
 
</tr>  
 
</tr>  
 
</table>
 
</table>
 +
 +
 +
=== 詳説 ===
 +
 +
 [[ポアソン過程]] (Poisson process) は, ランダムに生起する事象を表す基本的な[[確率過程]]で, 客の到着や故障の発生, 個体の出生など様々な現象のモデル化に使われる. 一方, [[出生死滅過程]]は個体の出生だけでなくランダムな死滅も考慮した確率過程で, [[待ち行列モデル|待ち行列理論]]をはじめ広く利用されている.
 +
 +
'''ポアソン過程''' 事象の生起時点列を <math>0 \le T_1 \le T_2 \le ...\, </math> とし, <math>N(t)\, </math> を区間 <math>[0, t]\, </math> における事象の生起数, <math>N(u,v) = N(v) - N(u)\, </math> を区間 <math>(u, v]\, </math> での生起数とする. このような確率過程<math>\{N(t), t\ge 0\}\, </math> は一般に計数過程と呼ばれる. 計数過程 <math>\{N(t)\}\, </math> がポアソン過程であるとは, 正の実数 <math>\lambda\, </math> が存在して任意の <math>t\ge 0\, </math> および <math>h>0\, </math> に対して
 +
 +
 +
<center>
 +
<math>
 +
\begin{array}{lll}
 +
&\mathrm{P}(N(t,t+h) = 1 \ | \ T_1,...,T_{N(t)}) = \lambda h + o(h), & \qquad (1)\\
 +
\\
 +
&\mathrm{P}(N(t,t+h) \geq 2 \ | \ T_1,...,T_{N(t)}) = o(h). & \qquad (2)
 +
\end{array}
 +
</math>
 +
</center>
 +
 +
 +
が成り立つことである.
 +
 +
 (1), (2) はランダムな事象の生起を3つの点で特徴付けている. 第1は, 微小区間 <math>(t, t+h]\, </math> に事象が生起する確率は時刻 <math>t\, </math> 以前の挙動に独立であるという点, 第2は, 微小区間に2つ以上の事象が生起する確率は無視できるという点, 第3は, 微小区間に事象の生起する確率が時刻によらない点である. 式 (1) の <math>\lambda\, </math> を強度 (intensity)  または生起率と呼ぶ. これは単位時間あたりの平均生起数を表す. 強度を時間の関数 <math>\lambda(t)\, </math> に拡張したものは[[ポアソン過程|非定常ポアソン過程]]と呼ばれる. 以下はポアソン過程の性質であり, それぞれがポアソン過程の同値な定義でもある.
 +
 +
'''性質1''' ポアソン過程 <math>\{N(t)\}\, </math> において,事象の生起間隔の列 <math>U_i =T_{i+1} - T_i\, </math> は互いに独立で平均 <math>1/\lambda\, </math> の
 +
[[指数分布]]に従う.
 +
\medskip
 +
 +
'''性質2''' ポアソン過程 <math>\{N(t)\}\, </math> は[[独立増分過程]]で, 任意の <math>s<t\, </math> に対して <math>N(s,t)\, </math> は平均 <math>\lambda (t-s)\, </math> の[[ポアソン分布]]に従う.
 +
 +
 性質1は[[無記憶性 (指数分布の)|指数分布の無記憶性]]から自然に導かれる. また, 性質2より複数の独立なポアソン過程の重ね合わせは, それぞれの強度の和を強度に持つポアソン過程となることが分かる. また, 次の定理は確率変数の和に対する[[少数の法則]]の確率過程版である.
 +
 +
 +
'''定理1''' 各 <math>k\, </math> に対して <math>\ell_k\, </math> 個の計数過程 <math>\{N_{k1}(t)\}, \cdots, \{N_{k\ell_k}(t)\}\, </math> を考え, その重ね合わせを <math>N_k(t) =N_{k1}(t)+ \cdots +N_{k\ell_k}(t)\, </math> とする. <math>\textstyle \lim_{k\to\infty} \ell_k=\infty\, </math> で, かつ (a) <math>\{N_{ki}(t)\}, \, i=1, \ldots , \ell_k\, </math> は互いに独立, (b) 任意の <math>u<v\, </math> に対して <math>\textstyle \lim_{k\to\infty} \sup_{1\le i \le \ell_k} \mathrm{P}(N_{ki}(u,v) \ge 1) = 0\, </math> が成り立つとすると, <math>\textstyle k\to\infty\, </math> のとき <math>\{N_k(t)\}\, </math> が[[ポアソン過程|平均測度]] <math>\{\Lambda(t)\}\, </math> の (非定常) ポアソン過程に収束するための必要十分条件は, 任意の <math>u<v\, </math> に対して, <math>\textstyle \lim_{k\to\infty} \sum_{i=1}^{\ell_k} \mathrm{P}(N_{ki}(u,v)=1) =\Lambda(v) - \Lambda(u)\, </math> および <math>\textstyle \lim_{k\to\infty} \sum_{i=1}^{\ell_k} \mathrm{P}(N_{ki}(u,v)>1) = 0\, </math>が成り立つことである. なお, <math>\Lambda(t)\, </math> が微分可能ならば強度は <math>\lambda(t) = \mbox{d}\Lambda(t)/\mbox{d}t\, </math> となる.
 +
 +
 定理1は, 実際に起こる様々な現象をポアソン過程を用いて表わすことの妥当性を示唆している. 例えば, 電話網のある回線群への接続要求 (呼) は非常に多くの電話機からかかってくる呼の重ね合わせとみなせる. この場合, 各電話機は独立に使われており (仮定 (a)), その頻度は十分小さい (仮定 (b)) と考えられるため, この回線群への呼の発生はポアソン過程としてモデル化できるであろう. この他にも, [[マルチンゲール]]によるポアソン過程の特徴付けや, 事象平均と時間平均の同等性を示す[[PASTA]] (Poisson arrivals see time averages) など, ポアソン過程には興味深い性質が多い.
 +
 +
 +
'''ポアソン過程の一般化''' ポアソン過程を特徴付ける3つの条件のうち第2の条件を緩め, 事象の生起時点列はポアソン過程であるが, 各生起時点で同時に発生する事象の数は独立で同一の分布に従う確率変数である場合, <math>N(t)\, </math> は複合ポアソン過程と呼ばれる. また, 非定常ポアソン過程の強度 <math>\lambda(t)\, </math> を確率過程に拡張したものは2重確率ポアソン過程 (doubly stochastic Poisson process) と呼ばれる. 例えば, [[マルコフ変調ポアソン過程]]は <math>\lambda(t)\, </math> が連続時間マルコフ連鎖に従う例である.
 +
 +
 +
'''出生過程''' 性質1より, ポアソン過程は[[状態空間]] <math>\{0, 1, ...\}\, </math> 上の[[マルコフ連鎖|連続時間マルコフ連鎖]]であることがわかる. [[推移速度行列]]を <math>\boldsymbol{Q} =(q_{ij})\, </math> とすると, 性質1から <math>q_{i,i+1} = -q_{ii} = \lambda, \, i\ge 0\, </math> でその他の <math>\boldsymbol{Q}\, </math> の要素は全て0となる. これを一般化して, <math>i\, </math> から <math>i+1\, </math> への推移速度が <math>i\, </math> に依存して <math>\lambda_i\, </math> で定まるマルコフ連鎖を[[出生過程]] (birth process)と呼ぶ. 出生過程の推移速度行列は<math>q_{i,i+1} = -q_{ii} = \lambda_i, \, i\ge 0\, </math> で, その他の要素は0である.
 +
 +
 +
'''出生死滅過程''' 出生過程では, 状態は <math>i\, </math> から <math>i+1\, </math> というように1ずつ進んでいくが, <math>i\, </math> から <math>i-1\, </math> へ戻ることも許すように一般化すると, <math>q_{i,i+1} = \lambda_i, \, q_{i+1,i} = \mu_{i+1}, \, i\ge 0\, </math> かつ <math>q_{00} =-\lambda_0, \, q_{ii} = -(\lambda_i + \mu_i), \, i\ge 1\, </math> で, その他の要素は0の推移速度行列が得られる. このような3重対角の推移速度行列に従う連続時間マルコフ連鎖を[[出生死滅過程]] (birth and death process) という. また, <math>\lambda_i\, </math>, <math>\mu_i\, </math> はそれぞれ状態 <math>i\, </math> での出生率, 死滅率と呼ばれる. 出生死滅過程では, 状態 <math>i\; (\ge 1)\, </math> に滞在する時間の長さはパラメータ <math>\lambda_i+\mu_i\, </math> の指数分布に従い, 滞在時間を終えると確率 <math>\lambda_i/(\lambda_i+\mu_i)\, </math> で状態 <math>i+1\, </math> へ, 確率 <math>\mu_i/(\lambda_i+\mu_i)\, </math> で状態 <math>i-1\, </math> へ推移する.
 +
 +
 出生死滅過程は隣り合う状態間でのみ[[推移]]が起きるという特徴を持つため, [[定常分布]]などの特性量が陽な形で得られる. 例えば, 応用上重要な <math>\lambda_i=\lambda\, </math>, <math>\mu_i=\mu\, </math> の出生死滅過程は, <math>\lambda < \mu\, </math> のとき[[再帰確率|正再帰的]]で, <math>\rho=\lambda/\mu\, </math> とすると状態 <math>j\, </math> にいる定常確率は <math>\pi_j = (1 - \rho)\rho^j, \; j=0,1,\ldots\, </math> という[[幾何分布]]となる. なお, <math>\lambda = \mu\, </math> のときは零再帰的, <math>\lambda > \mu\, </math> のときは一時的となり定常分布は存在しない. この例は[[待ち行列モデル M/M/1|M/M/1 待ち行列モデル]]に相当する出生死滅過程であるが, 出生死滅過程はより一般的な[[待ち行列モデル M/M/c|M/M/c 待ち行列モデル]] (M/M/<math>c\, </math> 待ち行列モデル) などのマルコフ型の待ち行列モデルや, [[機械修理工モデル|機械修理モデル]]を解析する上でも重要な確率過程となっている.
 +
 +
 +
 +
----
 +
'''参考文献'''
 +
 +
[1] P. Br&eacute;maud, ''Point Processes and Queues'', Springer-Verlag, 1981.
 +
 
 +
[2] D. R. Cox and V. Isham, ''Point Processes'', Chapman and Hall, 1980.
 +
 +
[3] R. W. Wolff, ''Stochastic Modeling and the Theory of Queues'', Prentice-Hall, 1989.
 +
 +
[4] 宮沢政清, 『確率と確率過程』, 近代科学社, 1993.
 +
 +
[[category:確率と確率過程|しゅっしょうしめつかてい]]
 +
 +
[[category:待ち行列|しゅっしょうしめつかてい]]

2008年11月9日 (日) 18:44時点における最新版

【しゅっしょうしめつかてい (birth and death process)】

概要

状態空間 上の連続時間マルコフ連鎖 で, 推移速度行列 が次で与えられる確率過程.


かつ
かつ
かつ
その他


詳説

 ポアソン過程 (Poisson process) は, ランダムに生起する事象を表す基本的な確率過程で, 客の到着や故障の発生, 個体の出生など様々な現象のモデル化に使われる. 一方, 出生死滅過程は個体の出生だけでなくランダムな死滅も考慮した確率過程で, 待ち行列理論をはじめ広く利用されている.

ポアソン過程 事象の生起時点列を とし, を区間 における事象の生起数, を区間 での生起数とする. このような確率過程 は一般に計数過程と呼ばれる. 計数過程 がポアソン過程であるとは, 正の実数 が存在して任意の および に対して



が成り立つことである.

 (1), (2) はランダムな事象の生起を3つの点で特徴付けている. 第1は, 微小区間 に事象が生起する確率は時刻 以前の挙動に独立であるという点, 第2は, 微小区間に2つ以上の事象が生起する確率は無視できるという点, 第3は, 微小区間に事象の生起する確率が時刻によらない点である. 式 (1) の を強度 (intensity) または生起率と呼ぶ. これは単位時間あたりの平均生起数を表す. 強度を時間の関数 に拡張したものは非定常ポアソン過程と呼ばれる. 以下はポアソン過程の性質であり, それぞれがポアソン過程の同値な定義でもある.

性質1 ポアソン過程 において,事象の生起間隔の列 は互いに独立で平均 指数分布に従う. \medskip

性質2 ポアソン過程 独立増分過程で, 任意の に対して は平均 ポアソン分布に従う.

 性質1は指数分布の無記憶性から自然に導かれる. また, 性質2より複数の独立なポアソン過程の重ね合わせは, それぞれの強度の和を強度に持つポアソン過程となることが分かる. また, 次の定理は確率変数の和に対する少数の法則の確率過程版である.


定理1 各 に対して 個の計数過程 を考え, その重ね合わせを とする. で, かつ (a) は互いに独立, (b) 任意の に対して が成り立つとすると, のとき 平均測度 の (非定常) ポアソン過程に収束するための必要十分条件は, 任意の に対して, および が成り立つことである. なお, が微分可能ならば強度は となる.

 定理1は, 実際に起こる様々な現象をポアソン過程を用いて表わすことの妥当性を示唆している. 例えば, 電話網のある回線群への接続要求 (呼) は非常に多くの電話機からかかってくる呼の重ね合わせとみなせる. この場合, 各電話機は独立に使われており (仮定 (a)), その頻度は十分小さい (仮定 (b)) と考えられるため, この回線群への呼の発生はポアソン過程としてモデル化できるであろう. この他にも, マルチンゲールによるポアソン過程の特徴付けや, 事象平均と時間平均の同等性を示すPASTA (Poisson arrivals see time averages) など, ポアソン過程には興味深い性質が多い.


ポアソン過程の一般化 ポアソン過程を特徴付ける3つの条件のうち第2の条件を緩め, 事象の生起時点列はポアソン過程であるが, 各生起時点で同時に発生する事象の数は独立で同一の分布に従う確率変数である場合, は複合ポアソン過程と呼ばれる. また, 非定常ポアソン過程の強度 を確率過程に拡張したものは2重確率ポアソン過程 (doubly stochastic Poisson process) と呼ばれる. 例えば, マルコフ変調ポアソン過程 が連続時間マルコフ連鎖に従う例である.


出生過程 性質1より, ポアソン過程は状態空間 上の連続時間マルコフ連鎖であることがわかる. 推移速度行列 とすると, 性質1から でその他の の要素は全て0となる. これを一般化して, から への推移速度が に依存して で定まるマルコフ連鎖を出生過程 (birth process)と呼ぶ. 出生過程の推移速度行列は で, その他の要素は0である.


出生死滅過程 出生過程では, 状態は から というように1ずつ進んでいくが, から へ戻ることも許すように一般化すると, かつ で, その他の要素は0の推移速度行列が得られる. このような3重対角の推移速度行列に従う連続時間マルコフ連鎖を出生死滅過程 (birth and death process) という. また, , はそれぞれ状態 での出生率, 死滅率と呼ばれる. 出生死滅過程では, 状態 に滞在する時間の長さはパラメータ の指数分布に従い, 滞在時間を終えると確率 で状態 へ, 確率 で状態 へ推移する.

 出生死滅過程は隣り合う状態間でのみ推移が起きるという特徴を持つため, 定常分布などの特性量が陽な形で得られる. 例えば, 応用上重要な , の出生死滅過程は, のとき正再帰的で, とすると状態 にいる定常確率は という幾何分布となる. なお, のときは零再帰的, のときは一時的となり定常分布は存在しない. この例はM/M/1 待ち行列モデルに相当する出生死滅過程であるが, 出生死滅過程はより一般的なM/M/c 待ち行列モデル (M/M/ 待ち行列モデル) などのマルコフ型の待ち行列モデルや, 機械修理モデルを解析する上でも重要な確率過程となっている.



参考文献

[1] P. Brémaud, Point Processes and Queues, Springer-Verlag, 1981.

[2] D. R. Cox and V. Isham, Point Processes, Chapman and Hall, 1980.

[3] R. W. Wolff, Stochastic Modeling and the Theory of Queues, Prentice-Hall, 1989.

[4] 宮沢政清, 『確率と確率過程』, 近代科学社, 1993.