中餐馆过程

在概率论中，中餐馆过程（Chinese restaurant process）是一种离散时间随机过程，得名于想象中的中餐馆圆桌。设想一间有可数无穷多张桌子的中餐馆，第一个客人在桌子 $1$ 就座，其后的每个客人可以选择随机坐在一张有人的桌子上或另找一张没人的新桌子，且坐在有人桌子上的概率正比于该桌子上的人数。 在时刻 $n$ ，所有顾客的集合 $\{1,2,...,n\}$ 按所在的桌子划分为 $m$ 个子集，其中 $m$ 是当前有人的桌子总数。

Fred Hoppe于1984年比照波利亚罐模型描述了与中餐馆模型等价的集合划分过程。将这一过程比作餐馆的表述最早见于David Aldous在1985年的文章 ，文中将这一表述归功于Jim Pitman（Jim Pitman又将其归功于Lester Dubins ）。

定义

对正整数 $n$ ，中餐馆过程在时刻 $n$ 的取值是集合 $\{1,2,...,n\}$ 的一个划分 $B_{n}$ 。在下一时刻， $n+1$ 所属的划分块有如下两种可能：

1. 放入 $B_{n}$ 的一个块 $b$ 中，其概率正比于块 $b$ 的元素个数，即 $|b|/(n+1)$ ,
2. 将 $\{n+1\}$ 作为只包含一个元素的新块加入 $B_{n}$ ，概率为 $1/(n+1)$ 。

当 $n=1$ 时，$B_{n}$ 以概率 $1$ 取为平凡划分 $\{\{1\}\}$ 。