中国料理店過程

中国料理店過程とは？

• 離散時刻で確率的に変化する過程
• 中国料理店に客がやってきたときに、どの円卓に座るかを考える
• 店には無数の円卓があり、円卓には無数の人が座れるものとする
• 最初の客は空の円卓に座る
• 2番目以降の客はランダムに円卓を選ぶが、座っている人の数が多い円卓を好む
• 数学的には[1,2,3,...,n]のpartitionがランダムに作成されることになり、数学者はこのpartitionの確率分布に興味を持つらしい
• ノンパラメトリックなベイズメソッドに応用される

モデリング

より一般化されたモデルもあるみたいだが、一番簡単なモデルを考える。

最初の客は空の円卓に座る。

n番目（n > 1）の客は、|b_i|/nの確率で円卓b_iに座る。もしくは、1/nの確率で空の円卓に座る。ただし、|b_i|は円卓b_iに座っている客の人数を表す。

サンプルプログラム

これだけだと何が嬉しいかわからない。ベイズにどうやって応用するか勉強したい。

from random import random
from bisect import bisect_left
import numpy as np

n = 100       # number of customers
block = []    # partition

for i in range(n):
    if not block:
        block.append([i])
    else:
        x = random()
        p = np.cumsum([1.0*len(b)/(i+1) for b in block])
        pos = bisect_left(p, x)
        if pos >= len(block):
            block.append([i])
        else:
            block[pos].append(i)
    print block