תהליך "המסעדה סינית"

בתורת ההסתברות, תהליך "המסעדה הסינית" הוא תהליך סטוכסטי זמן בדיד, המודגם באמצעות מודל של התיישבות לקוחות ליד שולחנות במסעדה. נתונה מסעדה עם אינסוף שולחנות הממוספרים $1,2,\ldots$, ולכל שולחן אינסוף מקומות ישיבה. לקוח $1$ בוחר לשבת על יד שולחן $1$. לקוח $2$ בהסתברות חצי בוחר לשבת על יד שולחן $1$ עם לקוח $1$, אחרת, הוא בוחר לשבת לבד על יד שולחן $2$. בהמשך, כאשר מגיע לקוח $n$, בהסתברות ${\frac {n-1}{n}}$ הוא בוחר באקראי את אחד הלקוחות שכבר יושבים ויושב לידו באותו השולחן (באחד מ-$m$ שולחנות). אחרת, הוא בוחר לשבת ליד השולחן הפנוי הממוספר כשולחן ה-$m+1$. התהליך עצמו הוא סדרה של משתנים מקריים $X_{1},X_{2},\ldots$ כאשר $X_{n}$ הוא מספר השולחן לידו התיישב הלקוח ה-$n$.

פונקציית הסתברות

נניח שהגיעו למסעדה $n$ לקוחות והתיישבו ב-$k$ שולחנות לפי סדר מסוים (מימוש) $X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n}$, ולכל $1\leq i\leq k$, נתון ש-$a_{i}$ התיישבו ליד השולחן ה-$i$. ההסתברות שסדר כזה יתקבל, הוא ${\textstyle \Pr \left(X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n}\right)={\frac {\prod _{i=1}^{k}(a_{i}-1)!}{n!}}}$.

דוגמה

למשל, אם ידוע לנו שהגיען $10$ לקוחות אז ההסתברות שהם התיישבו לפי הסדר הבא: ${\textstyle 1,2,1,3,1,2,3,2,3,3}$. במקרה כזה $a_{1}=3$, $a_{2}=3$ ו-$a_{3}=4$. ההסתברות לקבלת הסדר הספציפי הזה היא:

$$\Pr(X_{1}=1,X_{2}=2,X_{3}=1,X_{4}=3,X_{5}=1,X_{6}=2,X_{7}=3,X_{=}8=2,X_{9}=3,X_{1}0=3)={\frac {(3-1)!(3-1)!(4-1)}{10!}}$$

תכונה: רק החלוקה קובעת את הסתברות המימוש.

שימו לב שההסתברות ש-$10$ לקוחות יגיעו בסדר ${\textstyle 1,2,2,3,1,1,3,2,3,1}$ זהה לזו של הסדר ${\textstyle 1,2,1,3,1,2,3,2,3,3}$ ושווה ל-${\textstyle {\frac {(4-1)!(3-1)!(3-1)!}{10!}}}$ זה נובע כי בשני המימושים אותה יש את אותה החלוקה של $10$ והיא: $10=4+3+3$ (לא חשוב מבחינת חישוב ההסתברות, שסדרי ההגעה שונים ולמשל, שבסדר ההגעה הראשון הגיעו ארבעה לשולחן $3$ ובסדר ההגעה השני הגיעו ארבעה לשולחן $1$.)

תכונה זו של מודל "המסעדה הסינית" היא אחת הסיבות שבגללן המודל אטרקטיבי למידול תהליכים בגנטיקה של אוכלוסיות, בניתוח לשוני ובעיבוד תמונות.

מודל "המסעדה הסינית" הופיעה לראשונה במאמר משנת 1985 של דייוויד אלדוס, שם היא יוחסה לג'ים פיטמן (אשר ייחס אותה ללסטר דובין).