Search on the blog

2016年1月17日日曜日

中国料理店過程

中国料理店過程とは?
  • 離散時刻で確率的に変化する過程
  • 中国料理店に客がやってきたときに、どの円卓に座るかを考える
  • 店には無数の円卓があり、円卓には無数の人が座れるものとする
  • 最初の客は空の円卓に座る
  • 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

0 件のコメント:

コメントを投稿