中餐馆过程

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

Fred Hoppe于1984年比照波利亚罐模型（英语：Pólya's urn）描述了与中餐馆模型等价的集合划分过程。[1]将这一过程比作餐馆的表述最早见于David Aldous（英语：David Aldous）在1985年的文章[2] ，文中将这一表述归功于Jim Pitman（Jim Pitman又将其归功于Lester Dubins [3] ）。

定义

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

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

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

参考文献

1. Hoppe, Fred M. Pólya-like urns and the Ewens' sampling formula. Journal of Mathematical Biology. 1984, 20: 91–94. 
2. Aldous, D. J. Exchangeability and related topics. École d'Été de Probabilités de Saint-Flour XIII — 1983. Lecture Notes in Mathematics 1117. 1985: 1–198. ISBN 978-3-540-15203-3. doi:10.1007/BFb0099421.  中餐馆过程见于92页.
3. Pitman, Jim. Exchangeable and Partially Exchangeable Random Partitions. Probability Theory and Related Fields. 1995, 102 (2): 145–158. MR 1337249. S2CID 16849229. doi:10.1007/BF01213386 .