中華料理店過程のソースを表示

確率論において、'''中華料理店過程'''（ちゅうかりょうりてんかてい、{{lang-en-short|Chinese restaurant process}}）とは[[離散]][[確率過程]]の一種で、各時刻''n''において集合{1,2,…,''n''}の分割''B''<sub>''n''</sub>が次のようなルールで決定されるようなものを指す。時刻''n''=1では、''B''<sub>1</sub>={1}であり、時刻''n''での分割''B''<sub>''n''</sub>から時刻''n''+1における分割''B''<sub>''n''+1</sub>が次のように定まる。
# ''B''<sub>''n''</sub>が''m''個の部分からなるとき、各部分の大きさを|''b''<sub>''i''</sub>|, ''i''=1,...,''m''とするなら、|''b''<sub>''i''</sub>|/(''n''+1)の確率で''b''<sub>''i''</sub>に''n''+1が追加される。
# 確率 1 / (''n''+1)で、大きさが1で''n''+1のみを含むものが新たな部分として追加される。
このような計算によりランダムに生成された分割は{1,...,''n''}のラベルを付け直しても、その分割が生成される確率が変化しない。

==定義==
無限にたくさんの[[円卓]]が並べられた[[中華料理店]]を考える。各々の円卓もまた無限にたくさんの人が座ることが出来るものとする。1番目の客が店に入ってくると、その客はまだ誰も座っていない円卓に確率1で座る。ある時刻''n''+1で現れる''n''+1番目の客は店内を見回し、より多くの人が座っている円卓に高確率で座ろうとする、あるいはまだ誰も座っていないテーブルに座ることもあるだろう。各々のテーブルが店にやってきた客の分割を与えるものだと考えたものが中華料理店過程の考え方である。前述の定義により与えられた分割''B''<sub>''n''</sub>がとある分割''B''と等しくなる確率は次の式で与えられる。
:<math>\mathrm{Pr}(B_n = B) = \frac{1}{n!} \prod_{b \in B} (|b| - 1)!</math>
この式で、''b''は''B''に含まれる分割の部分を、|''b''|はその部分に含まれる要素の数を表すものとする。

==一般化==
前述の中華料理店モデルは2つのパラメータ''α''と''θ''により一般化できる。このとき''α''と''θ''はそれぞれ割引率と強度のパラメータと呼ばれる<ref>{{cite journal
 |first=Jim |last=Pitman
 |title=Exchangeable and Partially Exchangeable Random Partitions
 |journal=Probability Theory and Related Fields
 |volume=102 |issue=2 |pages=145&ndash;158
 |year=1995
 |mr=1337249 |doi=10.1007/BF01213386
}}</ref><ref name=Pitman2006>{{cite book|last=Pitman|first=Jim|title=Combinatorial Stochastic Processes|url=http://works.bepress.com/jim_pitman/1/|publisher=Springer-Verlag|year=2006|location=Berlin}}</ref>。ある時刻''n''+1において新たに来店した客が|''B''|個のテーブルに人がいるのを確認して、まだ誰も座っていないテーブルに座る確率を、
:<math>\frac{\theta + |B| \alpha}{n + \theta}</math>
とし、すでに|''b''|人が座っているテーブルに座る確率を
:<math>\frac{|b| - \alpha}{n + \theta}</math>
とする。この定義において正しく確率測度を定義するためには「''α''<0かつ''θ''=-''Lα'', ''L'' ∈{1,2,...}」あるいは「0 ≤ ''α'' ≤ 1かつ''θ''>-''α''」のいずれかが成り立たなければならない。

このモデルを仮定すると、''n''人の客のいずれの分割も[[ポッホハマー記号]]の意味で
:<math> \mathrm{Pr}(B_n = B) = \frac{(\theta + \alpha)_{|B|-1,\alpha}}{(\theta+1)_{n-1,1}} \prod_{b \in B} (1-\alpha)_{|b|-1,1}</math>
と表される。ただし<math>(\alpha)_{0,c}=1</math>であり、任意の''b''>0に対して、
:<math>
(a)_{b,c} = \prod_{i=0}^{b-1} (a+ic) = \begin{cases}
a^b & \mbox{if } c= 0 \\
\displaystyle \frac{c^b \Gamma (a / c + b)}{\Gamma (a/c)} & \mbox{otherwise}
\end{cases}
</math>
と定める。

このように、''θ''>0の場合では分割が与えられる確率が[[ガンマ関数]]により次のように与えられることが分かる。
:<math>\mathrm{Pr}(B_n = B) = \frac{\Gamma(\theta)}{\Gamma(\theta + n)} \frac{\alpha^{|B|} \Gamma (\theta/\alpha + |B|)}{\Gamma(\theta/\alpha)} \prod_{b \in B} \frac{\Gamma (|b| - \alpha)}{\Gamma(1-\alpha)}</math>
パラメータが1つの場合、すなわち''α''=0の場合においては単純に
:<math>\mathrm{Pr}(B_n = B) = \frac{\Gamma(\theta) \theta^{|B|}}{\Gamma(\theta + n)} \prod_{b \in B} \Gamma(|b|)</math>
と書ける。あるいは''θ''=0であれば、
:<math>\mathrm{Pr}(B_n = B) = \frac{\alpha^{|B|-1} \Gamma(|B|)}{\Gamma(n)} \prod_{b \in B} \frac{\Gamma (|b| - \alpha)}{\Gamma(1-\alpha)}</math>
と書ける。

このようにいずれの分割に対しても、その分割が与えられる確率は分割が含む部分の大きさのみに依存する。はじめに、ラベルの順番が入れ替わっても与えられる確率が変わらないといったのはこのためである。もし''α''=0であるなら、このようにして作られるランダムな分割が[[自然数の分割]]に対応しており、パラメータとして''θ''を取る{{仮リンク|エヴェンス分布|en|Ewens_distribution}}と対応する。

==出典==
{{reflist}}

==関連項目==
* [[ディリクレ分布]]
* [[ガウス過程]]
* [[ベイズ推定]]

{{math-stub}}
{{確率論}}

{{デフォルトソート:ちゆうかりようりてんかてい}}
[[Category:確率過程]]
[[category:ノンパラメトリック・ベイズ統計学]]
[[Category:数学に関する記事]]