中華料理店過程 中華料理店過程の概要

ウィキペディア

中華料理店過程

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/13 08:56 UTC 版)

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と等しくなる確率は次の式で与えられる。

${\displaystyle \mathrm {Pr} (B_{n}=B)={\frac {1}{n!}}\prod _{b\in B}(|b|-1)!}$

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

一般化

前述の中華料理店モデルは2つのパラメータαとθにより一般化できる。このときαとθはそれぞれ割引率と強度のパラメータと呼ばれる^[1][2]。ある時刻n+1において新たに来店した客が|B|個のテーブルに人がいるのを確認して、まだ誰も座っていないテーブルに座る確率を、

${\displaystyle {\frac {\theta +|B|\alpha }{n+\theta }}}$

とし、すでに|b|人が座っているテーブルに座る確率を

${\displaystyle {\frac {|b|-\alpha }{n+\theta }}}$

とする。この定義において正しく確率測度を定義するためには「α<0かつθ=-Lα, L ∈{1,2,...}」あるいは「0 ≤ α ≤ 1かつθ>-α」のいずれかが成り立たなければならない。

このモデルを仮定すると、n人の客のいずれの分割もポッホハマー記号の意味で

${\displaystyle \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}}$

と表される。ただし${\displaystyle (\alpha )_{0,c}=1}$であり、任意のb>0に対して、

${\displaystyle (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}}}$

と定める。

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

${\displaystyle \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 )}}}$

パラメータが1つの場合、すなわちα=0の場合においては単純に

${\displaystyle \mathrm {Pr} (B_{n}=B)={\frac {\Gamma (\theta )\theta ^{|B|}}{\Gamma (\theta +n)}}\prod _{b\in B}\Gamma (|b|)}$

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

${\displaystyle \mathrm {Pr} (B_{n}=B)={\frac {\alpha ^{|B|-1}\Gamma (|B|)}{\Gamma (n)}}\prod _{b\in B}{\frac {\Gamma (|b|-\alpha )}{\Gamma (1-\alpha )}}}$

と書ける。

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