中華料理店過程

同義語:中華レストラン過程Chinese restaurant process

概要

中華料理店過程(Chinese restaurant process)とは、$\theta>0$ について、客 $1,2,\dots$ を順に座らせ、$n$ 人のあとの客は $n_i$ 人のテーブルに確率 $\frac{n_i}{n+\theta}$ で加わり、確率 $\frac{\theta}{n+\theta}$ で新しいテーブルを開く規則で作る、自然数のランダムな分割の列である。分割の確率は $\frac{\theta^k\prod(n_i-1)!}{\theta(\theta+1)\cdots(\theta+n-1)}$(Ewens の分布)で、組の大きさだけで決まり番号の付け替えで変わらず、$\theta=1$ は一様な置換の巡回置換分解にあたる。テーブルの数は $\theta\log n$ のまわりに正規分布で揺らぎ、小さいテーブルの数は独立な Poisson 分布に近づく。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 確率測度, Pólyaの壺, Dirichlet過程, 巡回置換

中華料理店過程(Chinese restaurant process)とは、パラメータ $\theta>0$ を一つ決めて、自然数の集合のランダムな分割を 1 個ずつ順に作る規則である。無数の丸テーブルのある店に客 $1,2,3,\dots$ が順に入ってくる。最初の客は空いたテーブルに座る。$n$ 人が座ったあとに来た客は、$n_i$ 人が座っているテーブルに確率 $\frac{n_i}{n+\theta}$ で加わり、確率 $\frac{\theta}{n+\theta}$ で新しいテーブルに座る。同じテーブルの客を 1 つの組にまとめると、$\{1,\dots,n\}$ の分割 $\Pi_n$ ができる。
「混んでいるテーブルほど人を引き寄せる」という単純な規則なのに、できる分割の分布は客の番号の付け替えで変わらない(交換可能)。その分布は Ewens の分布 と呼ばれる明示的な式で書け、$\theta=1$ のときは一様にランダムな置換の巡回置換分解そのものになる。テーブルの数は $n$ の対数の速さでしか増えず、$\theta\log n$ に近い。同じ分割は、Dirichlet過程 から独立に取った観測の値の一致のしかたとしても現れる。名は L. Dubins と J. Pitman による(Pit02 §3.1, p. 62)。
この記事では次を証明する。

  • 分割の分布の公式(Ewens の分布)と、交換可能性(thm-crp-ewens)。組の大きさの個数の分布(Ewens の抽出公式)と、テーブルの数の分布。
  • $\theta=1$ の場合と一様な置換の巡回置換の対応。
  • テーブルの数の大数の強法則と中心極限定理(thm-crp-tables)。
  • 小さいテーブルの数が独立な Poisson 分布に近づくこと。
  • Dirichlet 過程の予測の規則との一致と、2 パラメータの拡張。

定義

$[n]:=\{1,\dots,n\}$ と書く。$[n]$ の 分割 とは、空でなく互いに交わらない部分集合(組)の集まりで、和が $[n]$ になるものをいう。組は最小の元の小さい順に並べ、$\pi=\{B_1,\dots,B_k\}$、$n_i:=\lvert B_i\rvert$ と書く。$x>0$ と整数 $m\ge0$ について、上昇階乗を $x^{(m)}:=x(x+1)\cdots(x+m-1)$($x^{(0)}:=1$)とおく。

中華料理店過程

$\theta>0$ とする。$[n]$ のランダムな分割の列 $\Pi_1,\Pi_2,\dots$ を次のように作る。$\Pi_1:=\{\{1\}\}$ とする。$\Pi_n=\{B_1,\dots,B_k\}$ が決まったとき、それまでの経過によらず、

  • 確率 $\dfrac{\lvert B_i\rvert}{n+\theta}$ で $n+1$ を $B_i$ に加え($i=1,\dots,k$)、
  • 確率 $\dfrac{\theta}{n+\theta}$ で新しい組 $\{n+1\}$ を作る。
    こうしてできた列 $(\Pi_n)_{n\ge1}$ を、パラメータ $\theta$ の 中華料理店過程 といい、$\mathrm{CRP}(\theta)$ と書く。組を「テーブル」、$[n]$ の元を「客」と呼ぶ。

確率の和は $\frac{n+\theta}{n+\theta}=1$ である。$\Pi_{n+1}$ から $n+1$ を取り除くと $\Pi_n$ に戻る(整合性)。

Ewens の分布

Ewens の分布

$(\Pi_n)$ を $\mathrm{CRP}(\theta)$ とする。$[n]$ の分割 $\pi$ の組の大きさを $n_1,\dots,n_k$ とすると
$$ P(\Pi_n=\pi)=\frac{\theta^k}{\theta^{(n)}}\prod_{i=1}^k(n_i-1)! $$
である。特に、右辺は組の大きさだけで決まり、$[n]$ の置換 $\sigma$ で $\pi$ を写した分割 $\sigma(\pi)$ についても同じ値をとる($\Pi_n$ は 交換可能)。

座らせ方の確率を掛け合わせる

$\pi$ を $[n]$ の分割とし、$m=1,\dots,n$ について、$\pi$ を $[m]$ に制限した分割を $\pi|_{[m]}$ とする。$\Pi_n=\pi$ となるのは、各 $m$ で $\Pi_m=\pi|_{[m]}$ となるときで、そのとき客 $m$ の座り方はただ一つに決まる。客 $m$ が座る確率を、客 $1$ について $\frac{\theta}{\theta}$($=1$)と書けば、どの客の確率も分母は $m-1+\theta$ である。よって分母の積は
$$ \prod_{m=1}^n(m-1+\theta)=\theta^{(n)} $$
である。分子は組ごとにまとめられる。組 $B_i$ の客のうち、最初の客($B_i$ の最小の元)は新しいテーブルを開くので分子は $\theta$ である。残りの客は、座る時点で $B_i$ にすでに $1,2,\dots,n_i-1$ 人がいるので、分子はこの順に $1,2,\dots,n_i-1$ である。$B_i$ の分子の積は $\theta\,(n_i-1)!$ で、全体の積は $\theta^k\prod_i(n_i-1)!$ である。$\sigma(\pi)$ の組の大きさの多重集合は $\pi$ と同じなので、確率も同じである。$\square$

$n=3$ では、$\{\{1,2,3\}\}$ の確率が $\frac{2}{(\theta+1)(\theta+2)}$、組の大きさが $2,1$ の 3 つの分割はどれも $\frac{\theta}{(\theta+1)(\theta+2)}$、$\{\{1\},\{2\},\{3\}\}$ が $\frac{\theta^2}{(\theta+1)(\theta+2)}$ で、和は $\frac{2+3\theta+\theta^2}{(\theta+1)(\theta+2)}=1$ である。$\{1,2\},\{3\}$ と $\{1,3\},\{2\}$ のように「早く来た客がまとまる」分割も「離れた客がまとまる」分割も同じ確率になることが、規則からはすぐには見えない交換可能性である。
整合的で交換可能な分割の列は、自然数全体のランダムな分割を定める。thm-crp-ewens の式は、そのような分割の分布を組の大きさの関数で表したもの(交換可能な分割確率関数、EPPF)の最も基本的な例である(Pit02 §2.2 Exercise 7, (124), p. 41)。
組の大きさごとの個数を $C_j:=\#\{i:n_i=j\}$($j=1,\dots,n$)とする。$\sum_jjC_j=n$、$\sum_jC_j=k$ である。

Ewens の抽出公式

$a_1,\dots,a_n\ge0$ が $\sum_jja_j=n$ を満たすとき、
$$ P\bigl(C_j(\Pi_n)=a_j\ (j=1,\dots,n)\bigr)=\frac{n!}{\theta^{(n)}}\prod_{j=1}^n\frac{(\theta/j)^{a_j}}{a_j!}. $$

大きさの型ごとに分割を数える

大きさ $j$ の組を $a_j$ 個ずつもつ $[n]$ の分割の個数は $\frac{n!}{\prod_j(j!)^{a_j}a_j!}$ である。実際、$[n]$ の並べ方 $n!$ 通りを、前から $1$ 個ずつの組 $a_1$ 個、$2$ 個ずつの組 $a_2$ 個、… と切り分けると、すべての分割が、組の中の並べ替え($\prod(j!)^{a_j}$ 通り)と同じ大きさの組どうしの並べ替え($\prod a_j!$ 通り)の分だけ重複して現れる。thm-crp-ewens によりこれらの分割はどれも確率 $\frac{\theta^{k}}{\theta^{(n)}}\prod_j((j-1)!)^{a_j}$($k=\sum a_j$)をもつので、掛けると
$$ \frac{n!}{\theta^{(n)}}\prod_j\frac{\theta^{a_j}((j-1)!)^{a_j}}{(j!)^{a_j}a_j!}=\frac{n!}{\theta^{(n)}}\prod_j\frac{(\theta/j)^{a_j}}{a_j!} $$
である。$\square$

この式は集団遺伝学で W. J. Ewens が選択的に中立な対立遺伝子の標本の理論(1972)の中で扱ったもので、Ewens の抽出公式(Ewens sampling formula)と呼ばれる(式は Pit02 §2.2 Exercise 7, (125), p. 41。Ewens の論文はその文献表の [122])。
テーブルの数 $K_n$ の分布も式で書ける。$n$ 個の元の置換のうち巡回置換がちょうど $k$ 個のものの個数を $c(n,k)$(第1種Stirling数、符号なし)とする。

テーブルの数の分布

$P(K_n=k)=\dfrac{c(n,k)\,\theta^k}{\theta^{(n)}}$($1\le k\le n$)である。

thm-crp-ewens を、組がちょうど $k$ 個の分割について足すと、$P(K_n=k)=\frac{\theta^k}{\theta^{(n)}}\sum_\pi\prod_i(n_i-1)!$ である。大きさ $m$ の組の上の巡回置換は $(m-1)!$ 個あるので、和は $k$ 個の巡回置換からなる $[n]$ の置換の個数 $c(n,k)$ である。$\square$

$k$ について足すと $\theta^{(n)}=\sum_kc(n,k)\theta^k$ という第 1 種 Stirling 数の母関数の等式が確率の言葉で出る。

θ = 1 と一様な置換

$\theta=1$ の規則は、一様にランダムな置換を 1 文字ずつ作る手順と同じである(Pit02 §3.1, p. 58)。客 $n+1$ は、すでに座った $n$ 人のうち誰か 1 人の すぐ左 に確率 $\frac1{n+1}$ ずつ座るか、確率 $\frac1{n+1}$ で新しいテーブルに 1 人で座る。座り終えた $n$ 人について、客 $i$ が同じテーブルの客 $j$ のすぐ左に座っていれば $\sigma_n(i):=j$、客 $i$ が 1 人で座っていれば $\sigma_n(i):=i$ と定める。客 $n+1$ が客 $j$ のすぐ左に座ると、それまで $j$ のすぐ左にいた客 $h$($\sigma_n(h)=j$)との間に入るので、巡回置換 $(\cdots h\,j\cdots)$ が $(\cdots h\ n{+}1\ j\cdots)$ に変わる。

一様な置換の巡回置換分解

$\sigma_n$ は $[n]$ の置換で、$n!$ 個の置換のどれにも確率 $\frac1{n!}$ でなる。$\sigma_n$ の巡回置換は各テーブルの客を座った円の向きに並べたもので、巡回置換の分割は $\mathrm{CRP}(1)$ の $\Pi_n$ と同じ分布をもつ。

座らせ方の列と置換の 1 対 1

客 $m$ の座り方は $m$ 通りあり、どれも確率 $\frac1m$ なので、座らせ方の列は $1\cdot2\cdots n=n!$ 通りで、どれも確率 $\frac1{n!}$ である。各テーブルの客を円の向きにたどった巡回置換の積が $\sigma_n$ なので $\sigma_n$ は置換である。異なる座らせ方の列は異なる置換を与える。実際、$\sigma_n$ の巡回置換から $n$ を抜いた置換が $\sigma_{n-1}$ で、$n$ が 1 人で座っていたか($\sigma_n(n)=n$)、誰のすぐ左に座ったか($\sigma_n(n)=j$)は $\sigma_n(n)$ から読める。$n$ についての帰納法で、$\sigma_n$ から座らせ方の列全体が復元できる。$n!$ 通りの列が $n!$ 個の置換に 1 対 1 に対応するので、$\sigma_n$ は一様である。客 $n+1$ が $n_i$ 人のテーブルに加わる確率は $\frac{n_i}{n+1}$、新しいテーブルを開く確率は $\frac1{n+1}$ なので、テーブルの分割の列は $\mathrm{CRP}(1)$ の規則に従う。$\square$

$\theta=1$ のとき cor-crp-esf は「一様な置換で長さ $j$ の巡回置換が $a_j$ 個ある確率は $\prod_j\frac{1}{j^{a_j}a_j!}$」という Cauchy の公式になる。cor-crp-stirling は、巡回置換が $k$ 個の置換が $c(n,k)$ 個あることの言い換えである。

テーブルの数

客 $i$ が新しいテーブルを開く事象の指示関数を $Z_i$ とすると、$K_n=Z_1+\dots+Z_n$ である。

テーブルの数の極限定理

$\mathrm{CRP}(\theta)$ について、次が成り立つ。

  1. $Z_1,Z_2,\dots$ は独立で、$P(Z_i=1)=\dfrac{\theta}{\theta+i-1}$ である。
  2. $E[K_n]=\displaystyle\sum_{i=1}^n\frac{\theta}{\theta+i-1}=\theta\log n+O(1)$、$\mathrm{Var}(K_n)=\displaystyle\sum_{i=1}^n\frac{\theta(i-1)}{(\theta+i-1)^2}=\theta\log n+O(1)$。
  3. 確率 $1$ で $\dfrac{K_n}{\log n}\to\theta$ である。
  4. $\dfrac{K_n-\theta\log n}{\sqrt{\theta\log n}}$ は標準正規分布に 分布収束 する。
新しいテーブルを開く確率は過去によらない

1. 客 $1,\dots,i-1$ の座り方のどの経過のもとでも、客 $i$ が新しいテーブルを開く条件付き確率は $q_i:=\frac{\theta}{\theta+i-1}$ で一定である。よって $Z_1,\dots,Z_{i-1}$ の値のどの組 $\epsilon$ についても $P(Z_i=1,\ (Z_1,\dots,Z_{i-1})=\epsilon)=q_i\,P((Z_1,\dots,Z_{i-1})=\epsilon)$ で、$i$ についての帰納法で $Z_1,\dots,Z_n$ は独立である。
2. 平均と分散は $q_i$、$q_i(1-q_i)=\frac{\theta(i-1)}{(\theta+i-1)^2}$ の和である。$t\mapsto\frac{\theta}{\theta+t}$ は減少関数なので
$$ \theta\log\Bigl(1+\frac n\theta\Bigr)=\int_0^n\frac{\theta\,dt}{\theta+t}\le\sum_{i=1}^n\frac{\theta}{\theta+i-1}\le1+\int_0^{n-1}\frac{\theta\,dt}{\theta+t}=1+\theta\log\Bigl(1+\frac{n-1}\theta\Bigr) $$
で、$E[K_n]=\theta\log n+O(1)$ である。$E[K_n]-\mathrm{Var}(K_n)=\sum_iq_i^2\le\sum_i\frac{\theta^2}{(\theta+i-1)^2}$ は有界なので、分散も $\theta\log n+O(1)$ である。
3. $b_i:=\log(i+1)$ とおく。$\sum_i\mathrm{Var}(Z_i/b_i)\le\sum_i\frac{\theta}{(\theta+i-1)\log^2(i+1)}< \infty$ なので、Kolmogorovの三級数定理 の補題「二級数の定理」により $\sum_i(Z_i-q_i)/b_i$ は確率 $1$ で収束する。$b_i$ は増加して $\infty$ に発散するので、Kroneckerの補題(級数) により確率 $1$ で $\frac{K_n-E[K_n]}{\log(n+1)}\to0$ である。2 により $\frac{E[K_n]}{\log n}\to\theta$ なので、$\frac{K_n}{\log n}\to\theta$ である。
4. $s_n^2:=\mathrm{Var}(K_n)\to\infty$ で、$\lvert Z_i-q_i\rvert\le1$ である。$\varepsilon>0$ について $\varepsilon s_n>1$ となる $n$ では、$\sum_iE[(Z_i-q_i)^2;\lvert Z_i-q_i\rvert>\varepsilon s_n]=0$ なので Lindeberg の条件が成り立ち、Lindeberg–Fellerの中心極限定理 により $\frac{K_n-E[K_n]}{s_n}$ は標準正規分布に分布収束する。2 から $\frac{E[K_n]-\theta\log n}{\sqrt{\theta\log n}}\to0$、$\frac{s_n}{\sqrt{\theta\log n}}\to1$ なので、正規化を取り替えても極限は変わらない。$\square$

$\theta=1$ では、一様な置換の巡回置換の個数の平均が調和数 $H_n=1+\frac12+\dots+\frac1n$ で、巡回置換の個数は $\log n$ のまわりに $\sqrt{\log n}$ の幅で揺らぐ(Pit02 §3.1, (151)–(152), p. 58、§3.3, (169), p. 68)。客の数を $10^6$ にしても、$\theta=1$ のテーブルはおよそ $14$ 卓しかない。

小さいテーブルの数の Poisson 極限

大きなテーブルの数は少なく、1 人や 2 人のテーブルの数は $n$ によらない程度に保たれる。

小さいテーブルの数の極限

$C_j^{(n)}$ を $\Pi_n$ の大きさ $j$ の組の個数とする。$b\ge1$ を固定すると、$n\to\infty$ のとき $(C_1^{(n)},\dots,C_b^{(n)})$ は、平均 $\theta,\frac\theta2,\dots,\frac\theta b$ の独立な Poisson分布 に従う確率変数の組 $(Y_1,\dots,Y_b)$ に分布収束する。

階乗モーメントを Ewens の抽出公式から計算する

要点:$(x)_r:=x(x-1)\cdots(x-r+1)$ とおくと、$s:=\sum_jjr_j\le n$ のとき $E\bigl[\prod_{j\le b}(C_j^{(n)})_{r_j}\bigr]=\prod_j(\theta/j)^{r_j}\cdot R_n(s)$、$R_n(s)\to1$ である。極限は Poisson の階乗モーメントで、階乗モーメントは $\mathbb N^b$ 上の分布を決める。

詳しい証明を開く

階乗モーメント。$r_1,\dots,r_b\ge0$、$s:=\sum_jjr_j\le n$ とする。cor-crp-esf で $a_j=r_j+c_j$($j\le b$)、$a_j=c_j$($j>b$)と置き換えると、$(a_j)_{r_j}/a_j!=1/c_j!$ なので

$$E\Bigl[\prod_{j\le b}(C_j^{(n)})_{r_j}\Bigr]=\prod_{j\le b}\Bigl(\frac\theta j\Bigr)^{r_j}\cdot\frac{n!}{\theta^{(n)}}\sum_{c}\prod_j\frac{(\theta/j)^{c_j}}{c_j!}$$

で、和は $\sum_jjc_j=n-s$ を満たす $c$ にわたる。$n-s$ 人についての cor-crp-esf の確率の和は $1$ なので、和は $\frac{\theta^{(n-s)}}{(n-s)!}$ に等しい。よって $R_n(s)=\frac{n!\,\theta^{(n-s)}}{(n-s)!\,\theta^{(n)}}=\prod_{i=n-s}^{n-1}\frac{i+1}{\theta+i}$ で、$s$ を固定して $n\to\infty$ とすると $R_n(s)\to1$ である。$s>n$ なら左辺は $0$ である。

収束。$X^{(n)}:=(C_1^{(n)},\dots,C_b^{(n)})$ とする。$E[C_j^{(n)}]=\frac\theta jR_n(j)$ は $n$ について有界なので、族 $\{X^{(n)}\}$ は緊密である。部分列 $X^{(n')}$ が $X$ に分布収束したとする。各 $r$ について $\prod_j(x_j)_{r_j}$ の 2 乗は、次数が $2r_j$ 以下の階乗の積の線形結合なので、上の公式から $\sup_nE[\prod_j(C_j^{(n)})_{r_j}^2]< \infty$ である。よって $\prod_j(C_j^{(n')})_{r_j}$ は 一様可積分性 をもち、$E[\prod_j(X_j)_{r_j}]=\prod_j(\theta/j)^{r_j}$ である。$u_j\ge0$ について、非負の項の和の順序を入れ替えて(Fubiniの定理)、

$$E\Bigl[\prod_j(1+u_j)^{X_j}\Bigr]=\sum_{r}\prod_j\frac{u_j^{r_j}}{r_j!}E\Bigl[\prod_j(X_j)_{r_j}\Bigr]=\exp\Bigl(\sum_j\frac{\theta}{j}u_j\Bigr)$$

である($(1+u)^x=\sum_r\binom xr u^r$)。左辺は非負の係数 $P(X=a)$ をもつ $z_j=1+u_j$ の冪級数で、$[1,\infty)^b$ のすべての点で収束するので、$\lvert z_j\rvert< R$ の多重円板で絶対収束する。右辺 $\exp(\sum_j\frac\theta j(z_j-1))$ と $[1,\infty)^b$ の内点の上で一致するので、一致の定理 を 1 変数ずつ使って冪級数の係数が一致し、$P(X=a)=\prod_je^{-\theta/j}\frac{(\theta/j)^{a_j}}{a_j!}$ である。部分列の極限がすべて同じなので、列全体が分布収束する。$\square$

一様な置換($\theta=1$)では、不動点の個数が平均 $1$ の Poisson 分布に近づく(モンモール数の確率 $1/e$)。この定理は Pit02 §3.3, (170), p. 69 に主張があり、cor-crp-esf を独立な $Y_j$ の言葉で書いた次の事実と同じ内容である。

条件付けによる表示

$Y_1,\dots,Y_n$ を平均 $\theta/j$ の独立な Poisson 変数、$T_n:=\sum_{j=1}^njY_j$ とする。$\sum_jja_j=n$ を満たす $a$ について
$$ P\bigl(C_j^{(n)}=a_j\ (j\le n)\bigr)=P\bigl(Y_j=a_j\ (j\le n)\bigm|T_n=n\bigr). $$

要点:$H_n:=\sum_{j\le n}\frac1j$ とおくと $P(T_n=n)=e^{-\theta H_n}\frac{\theta^{(n)}}{n!}$ である。

詳しい証明を開く

$P(Y=a)=e^{-\theta H_n}\prod_j\frac{(\theta/j)^{a_j}}{a_j!}=e^{-\theta H_n}\frac{\theta^{(n)}}{n!}P(C^{(n)}=a)$ である。$\sum_jja_j=n$ のすべての $a$ について足すと、cor-crp-esf の確率の和が $1$ なので $P(T_n=n)=e^{-\theta H_n}\frac{\theta^{(n)}}{n!}$ である。割り算すると主張を得る。$\square$

「独立な Poisson を、和の制約で条件付けたもの」という見方は、$n$ が大きいと制約 $T_n=n$ が小さい $j$ の成分にほとんど影響しないことを示唆する。thm-crp-poisson はそれを正確にしたものである。

最初のテーブルの割合

最初のテーブルの割合は Beta 分布に近づく

客 $1$ のテーブルの人数を $N_n$ とする。客 $n+1$ がそこに加わる確率は $\frac{N_n}{n+\theta}$、加わらない確率は $\frac{(n-N_n)+\theta}{n+\theta}$ である。これは、白玉 $1$ 個と「重さ」$\theta$ の黒玉から始め、取り出した色の玉を 1 個足す Pólyaの壺 で、白玉の割合が $\frac{N_n}{n+\theta}$ になるものと同じ遷移である。よって $N_n/n$ は確率 $1$ で収束し、極限は $\mathrm{Beta}(1,\theta)$ 分布に従う(Beta分布)。$\theta=1$ では極限は $[0,1]$ の一様分布で、$N_n$ は $\{1,\dots,n\}$ の一様分布に従う(Pit02 §3.1, p. 59)。一様な置換で $1$ を含む巡回置換の長さが一様分布に従うことの言い換えである。

客 $1$ のテーブルを除いた客だけを見ると、また $\mathrm{CRP}(\theta)$ の規則で座っている。したがって、テーブルを開いた順の極限の割合 $\tilde P_1,\tilde P_2,\dots$ は、独立な $W_i\sim\mathrm{Beta}(1,\theta)$ で $\tilde P_1=W_1$、$\tilde P_2=(1-W_1)W_2$、… と棒を折って作れる。これは Dirichlet過程 の棒折り構成の重みと同じ分布で、GEM 分布(Griffiths–Engen–McCloskey)という。$\tilde P_i$ を大きい順に並べ替えた列の分布を Poisson–Dirichlet 分布 $\mathrm{PD}(\theta)$ という(Pit02 Theorem 25, Definition 26, pp. 63–64。この記事では証明しない。分布の性質は Poisson–Dirichlet分布 で扱う)。

Dirichlet 過程との関係

Dirichlet過程 の系「予測分布(一般化した Pólya の壺)」は、全質量 $M$、基底分布 $G_0$ の Dirichlet 過程 $P$ から $P$ に従う独立な観測 $X_1,X_2,\dots$ を取ったとき、$X_{n+1}$ が確率 $\frac{M}{M+n}$ で $G_0$ から新しく選ばれ、確率 $\frac1{M+n}$ ずつ $X_1,\dots,X_n$ の値をとることを示している(Blackwell–MacQueen の壺)。

値の一致による分割

観測の空間は標準 Borel 空間で、$G_0$ は原子をもたない(すべての点 $x$ で $G_0(\{x\})=0$)とする。$i\sim j\Leftrightarrow X_i=X_j$ で定めた $[n]$ の分割を $\Pi_n$ とすると、$(\Pi_n)_{n\ge1}$ は $\mathrm{CRP}(M)$ である。

$X_1,\dots,X_n$ を固定すると、異なる値は $\Pi_n$ の組 $B_1,\dots,B_k$ に対応する。上の予測の規則により、$X_{n+1}$ が $B_i$ の値に等しくなる確率は、$G_0$ から新しく選んだ値が $B_i$ の値に一致する確率 $0$ を除いて $\frac{\lvert B_i\rvert}{M+n}$ である。$G_0$ から新しく選んだ値が既存の有限個の値のどれとも異なる確率は $1$ なので、$n+1$ が新しい組を作る確率は $\frac{M}{M+n}$ である。これは def-crp-main の規則で $\theta=M$ としたものである。$\square$

テーブルは観測の中の「異なる値」に、テーブルの人数は値の重複度にあたる。Dirichlet 過程を事前分布にした混合モデルで、観測をクラスタに分ける分布として中華料理店過程が使われるのはこのためである。thm-crp-tables の 2 は、Dirichlet過程 の記事の命題「異なる値の個数」と同じ式である。

2 パラメータの中華料理店過程

2 パラメータの中華料理店過程

$0\le\alpha<1$、$\theta>-\alpha$ とする。$\Pi_n=\{B_1,\dots,B_k\}$ のもとで、客 $n+1$ は確率 $\frac{\lvert B_i\rvert-\alpha}{n+\theta}$ で $B_i$ に加わり、確率 $\frac{\theta+k\alpha}{n+\theta}$ で新しいテーブルを開く。この列を $\mathrm{CRP}(\alpha,\theta)$ と書く。

和は $\frac{n-k\alpha+\theta+k\alpha}{n+\theta}=1$ で、$\lvert B_i\rvert\ge1>\alpha$、$\theta+k\alpha>0$ なので確率は正である。$\alpha=0$ が $\mathrm{CRP}(\theta)$ である(Pit02 §3.2, pp. 62–63)。

2 パラメータの分割の分布

組の大きさが $n_1,\dots,n_k$ の $[n]$ の分割 $\pi$ について
$$ P(\Pi_n=\pi)=\frac{\prod_{i=1}^{k-1}(\theta+i\alpha)}{(\theta+1)^{(n-1)}}\prod_{i=1}^k(1-\alpha)^{(n_i-1)} $$
である。特に $\Pi_n$ は交換可能である。

要点:prf-crp-ewens と同じく座り方の確率を掛ける。

詳しい証明を開く

客 $1$ は確率 $1$ で座り、客 $m+1$($m\ge1$)の分母は $m+\theta$ なので、分母の積は $(\theta+1)^{(n-1)}$ である。$i$ 番目($i\ge2$)のテーブルを開くときは $i-1$ 卓が開いているので分子は $\theta+(i-1)\alpha$ である。テーブル $B_i$ に人数 $1,2,\dots,n_i-1$ の状態から加わる客の分子は $1-\alpha,2-\alpha,\dots,n_i-1-\alpha$ で、積は $(1-\alpha)^{(n_i-1)}$ である。$\square$

$\alpha>0$ では新しいテーブルを開く確率がテーブルの数とともに増えるので、テーブルの数は対数ではなく冪の速さで増え、$K_n/n^\alpha$ が確率 $1$ で正の確率変数に収束する(Pit02 Theorem 31, (171), p. 69。この記事では証明しない)。極限の割合は独立な $W_i\sim\mathrm{Beta}(1-\alpha,\theta+i\alpha)$ による棒折りで、大きい順に並べた分布を $\mathrm{PD}(\alpha,\theta)$ と書く(Pit02 Theorem 25, (156), Definition 26, pp. 63–64)。

反例:仮定を外すと成り立たないこと

主張外す仮定反例成り立たなくなること
thm-crp-ewens の交換可能性加わる確率が人数に比例客 $n+1$ は確率 $\frac12$ で客 $n$ のテーブルに、確率 $\frac12$ で新しいテーブルに座る$P(\Pi_3=\{\{1,2\},\{3\}\})=\frac14$、$P(\Pi_3=\{\{1,3\},\{2\}\})=0$
thm-crp-tables の 3$\alpha=0$$\mathrm{CRP}(\alpha,\theta)$、$0< \alpha<1$$K_n/\log n\to\infty$($K_n$ は $n^\alpha$ の程度)
prop-crp-dp$G_0$ に原子がない$G_0=\delta_0$すべての $X_i$ が $0$ で、$\Pi_n$ はつねに 1 組
thm-crp-poisson見る大きさの範囲 $b$ を固定$\theta=1$、$b=n$(すべての大きさを同時に見る)$\sum_jjC_j^{(n)}=n$ はつねに成り立つが、$\sum_{j\le n}jY_j=n$ の確率は $e^{-H_n}\le\frac1{n+1}$ で、$(C_1^{(n)},\dots,C_n^{(n)})$ と $(Y_1,\dots,Y_n)$ の分布の全変動距離は $1$ に近づく
表の確かめ

1 行目:客 $2$ は確率 $\frac12$ で客 $1$ のテーブルに座り、客 $3$ が新しいテーブルを開く確率は $\frac12$ なので $\{\{1,2\},\{3\}\}$ の確率は $\frac14$ である。客 $3$ は客 $2$ のテーブルか新しいテーブルにしか座れないので、客 $2$ が新しいテーブルに座ったあと客 $3$ が客 $1$ のテーブルに座ることはない。組の大きさが同じ 2 つの分割の確率が違うので交換可能でない。2 行目:$\mathrm{CRP}(\alpha,\theta)$ では $K_n/n^\alpha$ が正の確率変数に収束するので、$K_n/\log n=(K_n/n^\alpha)(n^\alpha/\log n)\to\infty$ である。3 行目:予測の規則で $G_0$ から新しく選んだ値も $0$ なので、すべての $X_i$ が $0$ になる。4 行目:prf-crp-conditioning で求めた $P(T_n=n)=e^{-\theta H_n}\frac{\theta^{(n)}}{n!}$ は $\theta=1$ で $e^{-H_n}$ であり、$H_n\ge\int_1^{n+1}\frac{dt}{t}=\log(n+1)$ なので $\frac1{n+1}$ 以下である。事象 $\{\sum_jjx_j=n\}$ の確率が一方では $1$、他方では $\frac1{n+1}$ 以下なので、全変動距離は $1-\frac1{n+1}$ 以上である。$\square$

補足

名前と文献

「中華料理店」の名は、席に限りのない丸テーブルが並ぶ店の比喩で、Dubins と Pitman が 1980 年代初めに考えたと Pit02 §3.1 の注(p. 62)にある。この記事の命題の証明は、どれも座り方の確率の積と cor-crp-esf から直接組み立てた。

関連項目

参考文献

[1]
Jim Pitman, Combinatorial Stochastic Processes, Technical Report No. 621, Department of Statistics, University of California, Berkeley (2002), 2002, §2.2 Exercise 6・7, (123)–(125)(p. 41)、§3.1, (151)–(152)(pp. 58–59)と注(p. 62)、§3.2, Theorem 25, (155)–(156)(pp. 62–64)、Definition 26(p. 64)、§3.3, (169)–(170)(pp. 68–69)、Theorem 31(p. 69)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する