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

בתורת ההסתברות, תהליך המסעדה הסינית הוא תהליך סטוכסטי זמן בדיד, המודגם באמצעות מודל של התיישבות לקוחות ליד שולחנות במסעדה, עם אינסוף שולחנות עגולים, הממוספרים $1,2,\ldots$, שלכל אחד מהם קיבולת ישיבה אינסופית. לקוח $1$ מתיישב על יד שולחן $1$. הלקוח הבא בוחר או לשבת באותו שולחן כמו לקוח 1, או בשולחן הבא. כך התהליך ממשיך, כאשר נכנס הלקוח ה-$n$, הוא בוחר לשבת ליד באחד מה-$m$ השולחנות התפוסים בהסתברות שפרופורציונלית למספר הלקוחות שכבר שם (כלומר, יש סיכוי גבוה יותר שיתיישב בשולחן עם לקוחות רבים מאשר מעטים), או בהסתברות ${\frac {1}{n}}$ בשולחן שמספרו $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_{10}=3)={\frac {(3-1)!(3-1)!(4-1)!}{10!}}$$תכונה: רק החלוקה של $n$ קובעת את הסתברות המימוש.

בדוגמה לעיל, ההסתברות ש-$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$.

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

הכללה

תהליך המסעדה הסינית ניתן להכללה למודל עם שני פרמטרים, $\theta$ ו - $\alpha$. כאשר הלקוח ה-$n$ מגיע הוא מוצא $m$ שולחנות תפוסים ומחליט לשבת ליד שולחן ריק בהסתברות

${\frac {\theta +m\alpha }{n+\theta }}$,

או ליד שולחן תפוס שמספרו $1\leq i\leq m$ עם $a_{i}$ לקוחות שכבר יושבים לידו, בהסתברות

${\frac {a_{i}-\alpha }{n+\theta }}$.

כדי להבטיח התפלגות תקפה (הסתברויות חיוביות), יש צורך להניח ש - $0\leq \alpha <1$ ו - $\theta >-\alpha$, או ש - $\alpha <0$ ואז $\theta =-L\alpha$ עבור מספר טבעי $L$ (במקרה כזה מספר השולחנות התפוסים לא יכול לעלות על $L$).

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

$\Pr \left(X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n}\right)={\frac {(\theta +\alpha )_{k-1,\alpha }}{(\theta +1)_{n-1,1}}}\prod _{i=1}^{k}(1-\alpha )_{a_{i}-1,1}$,

כאשר $(b)_{c,d}$ הוא הסימן-k של פושהמר, שלפי המוסכמה מקיים, $(b)_{0,d}=1$, ועבור $c>0$

$(b)_{c,d}=\prod _{i=0}^{c-1}(b+id)={\begin{cases}b^{c}&:d=0&{\text{םא }}\\\\{\dfrac {d^{c}\,\Gamma (b/d+c)}{\Gamma (b/d)}}&:{\text{תרחא}}\end{cases}}$.

היסטוריה

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