跳至內容

中餐館過程

維基百科,自由的百科全書

概率論中,中餐館過程(Chinese restaurant process)是一種離散時間英語Discrete-time stochastic process隨機過程,得名於想象中的中餐館圓桌。設想一間有可數無窮多張桌子的中餐館,第一個客人在桌子 就座,其後的每個客人可以選擇隨機坐在一張有人的桌子上或另找一張沒人的新桌子,且坐在有人桌子上的概率正比於該桌子上的人數。 在時刻 ,所有顧客的集合 按所在的桌子劃分為 個子集,其中 是當前有人的桌子總數。

Fred Hoppe於1984年比照波利亞罐模型英語Pólya's urn描述了與中餐館模型等價的集合劃分過程。[1]將這一過程比作餐館的表述最早見於David Aldous英語David Aldous在1985年的文章[2] ,文中將這一表述歸功於Jim Pitman(Jim Pitman又將其歸功於Lester Dubins [3] )。

定義

[編輯]

對正整數 ,中餐館過程在時刻 的取值是集合 的一個劃分 。在下一時刻, 所屬的劃分塊有如下兩種可能:

  1. 放入 的一個塊 中,其概率正比於塊 的元素個數,即 ,
  2. 作為只包含一個元素的新塊加入 ,概率為

時, 以概率 取為平凡劃分

參考文獻

[編輯]
  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可免費查閱.