中華料理店過程

確率論において、中華料理店過程(ちゅうかりょうりてんかてい、Chinese Restaurant Process)とは離散確率過程の一種で、各時刻nにおいて集合{1,2,…,n}の分割B_nが次のようなルールで決定されるようなものを指す。時刻n=1では、B₁={1}であり、時刻nでの分割B_nから時刻n+1における分割B_n+1が次のように定まる。

1. B_nがm個の部分からなるとき、各部分の大きさを|b_i|, i=1,...,mとするなら、|b_i|/(n+1)の確率でb_iにn+1が追加される。
2. 確率 1 / (n+1)で、大きさが1でn+1のみを含むものが新たな部分として追加される。

このような計算によりランダムに生成された分割は{1,...,n}のラベルを付け直しても、その分割が生成される確率が変化しない。

定義

無限にたくさんの円卓が並べられた中華料理店を考える。各々の円卓もまた無限にたくさんの人が座ることが出来るものとする。1番目のお客が店に入ってくると、そのお客はまだ誰も座っていない円卓に確率1で座る。ある時刻n+1で現れるn+1番目の客は店内を見回し、より多くの人が座っている円卓に高確率で座ろうとする、あるいはまだ誰も座っていないテーブルに座ることもあるだろう。各々のテーブルが店にやってきた客の分割を与えるものだと考えたものが中華料理店過程の考え方である。前述の定義により与えられた分割B_nがとある分割Bと等しくなる確率は次の式で与えられる。

[math]Pr(B_n = B) = \frac{\Pi_{b \in B} (|b| - 1)!}{n!}[/math]

この式で、bはBに含まれる分割の部分を、|b|はその部分に含まれる要素の数を表すものとする。

一般化

前述の中華料理店モデルは2つのパラメータαとθにより一般化できる。このときαとθはそれぞれ割引率と強度のパラメータと呼ばれる。ある時刻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] 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 \\ \frac{c^b \Gamma (a / c + b)}{\Gamma (a/c)} & \mbox{otherwise} \end{cases} [/math]

と定める。

このように、θ>0の場合では分割が与えられる確率がガンマ関数により次のように与えられることが分かる。

[math]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]Pr(B_n = B) = \frac{\Gamma(\theta) \theta^{|B|}}{\Gamma(\theta + n)} \prod_{b \in B} \Gamma(|b|)[/math]

と書ける。あるいはθ=0であれば、

[math]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であるなら、このようにして作られるランダムな分割が自然数の分割に対応しており、パラメータとしてθを取るEwens分布と対応する。

関連項目

• ディリクレ分布
• ガウス過程
• ベイズ推定