הצגת המקור של הדף "תהליך המסעדה הסינית"

ב[[תורת ההסתברות]], '''תהליך המסעדה הסינית''' הוא [[תהליך סטוכסטי]] [[זמן בדיד וזמן רציף|זמן בדיד]], המודגם באמצעות מודל של התיישבות לקוחות ליד שולחנות במסעדה, עם אינסוף שולחנות עגולים, הממוספרים <math>1,2,\ldots</math>, שלכל אחד מהם קיבולת ישיבה אינסופית. לקוח <math>1</math> מתיישב על יד שולחן <math>1</math>. הלקוח הבא בוחר או לשבת באותו שולחן כמו לקוח 1, או בשולחן הבא. כך התהליך ממשיך, כאשר נכנס הלקוח ה-<math>n</math>, הוא בוחר לשבת ליד באחד מה-<math>m</math> השולחנות התפוסים בהסתברות שפרופורציונלית למספר הלקוחות שכבר שם (כלומר, יש סיכוי גבוה יותר שיתיישב בשולחן עם לקוחות רבים מאשר מעטים), או בהסתברות <math>\frac{1}{n}</math> בשולחן שמספרו <math>m+1</math> ועדיין פנוי. התהליך עצמו הוא סדרה של [[משתנה מקרי|משתנים מקריים]] <math>X_1,X_2,\ldots</math> כאשר <math>X_n</math> הוא מספר השולחן לידו התיישב הלקוח ה-<math>n</math>. התהליך הזה הוא אמצעי חשוב ליצירה של סדרה של [[חלוקה מקרית של קבוצה|חלוקות מקריות חליפיות]] (החלוקות של הלקוחות לפי שולחנות) שהיא גם [[חלוקה מקרית של קבוצה|חלוקה מקרית חילופית של המספרים הטבעיים]]. תכונה זו מפשטת מאוד מספר בעיות ב[[גנטיקה של אוכלוסיות]], ניתוח לשוני ו[[ראייה ממוחשבת|זיהוי תמונות]].

== פונקציית הסתברות ==
נניח שהגיעו למסעדה <math>n</math> לקוחות והתיישבו ב-<math>k</math> שולחנות לפי סדר מסוים (מימוש) <math>X_1=x_1, X_2=x_2,\ldots,X_n=x_n</math>, ולכל <math>1\leq i\leq k</math>, נתון ש-<math>a_i</math> התיישבו ליד השולחן ה-<math>i</math>. ההסתברות שסדר כזה יתקבל, הוא <math display="inline">
 \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! }
</math>.

'''דוגמה'''

למשל, אם ידוע לנו שהגיעו <math>10</math> לקוחות והתיישבו לפי הסדר הבא: <math display="inline">1,2,1,3,1,2,3,2,3,3</math>. במקרה כזה <math>a_1=3</math>, <math>a_2=3</math> ו-<math>a_3=4</math>. ההסתברות לקבלת המימוש הספציפי הזה היא:<math display="block">\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!}</math>'''תכונה: רק ה[[חלוקה (תורת המספרים)|חלוקה]] של <math>n</math> קובעת את הסתברות המימוש.'''

בדוגמה לעיל, ההסתברות ש-<math>10</math> לקוחות יגיעו בסדר - <math display="inline">1,2,2,3,1,1,3,2,3,1</math> זהה לזו של הסדר בדוגמה - <math display="inline">1,2,1,3,1,2,3,2,3,3</math> ושווה גם היא ל-<math display="inline">\frac{(4-1)!(3-1)!(3-1)!}{10! }</math>. הסיבה לכך היא שבשני המימושים יש את אותה החלוקה של <math>10</math> והיא: <math>10=4+3+3</math>. מבחינת חישוב ההסתברות, אין חשיבות לכך שסדרי ההגעה שונים. למשל, בסדר ההגעה הראשון הגיעו ארבעה לשולחן <math>3</math> ובסדר ההגעה השני הגיעו ארבעה לשולחן <math>1</math>.

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

== הכללה ==
תהליך המסעדה הסינית ניתן להכללה למודל עם שני פרמטרים, <math>\theta</math> ו - <math>\alpha</math>.<ref name="Pitman19952">{{Cite journal|last=Pitman|first=Jim|year=1995|title=Exchangeable and Partially Exchangeable Random Partitions|journal=Probability Theory and Related Fields|volume=102|issue=2|pages=145-158|doi=10.1007/BF01213386|mr=1337249|doi-access=free}}</ref><ref name="Pitman2006">{{Cite book|last=Pitman|first=Jim|url=http://works.bepress.com/jim_pitman/1/|title=Combinatorial Stochastic Processes|publisher=Springer-Verlag|year=2006|isbn=9783540309901|volume=1875|location=Berlin|access-date=2011-05-11|archive-url=https://web.archive.org/web/20120925082105/http://works.bepress.com/jim_pitman/1/|archive-date=2012-09-25|url-status=dead}}</ref> כאשר הלקוח ה-<math>n</math> מגיע הוא מוצא <math>m</math> שולחנות תפוסים ומחליט לשבת ליד שולחן ריק בהסתברות

<math>
\frac{\theta + m \alpha}{n + \theta}
</math>,

או ליד שולחן תפוס שמספרו <math>
1\leq i\leq m
</math> עם <math>
a_i
</math> לקוחות שכבר יושבים לידו, בהסתברות

<math>
\frac{a_i - \alpha}{n + \theta}
</math>.

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

נניח שהגיעו למסעדה <math>n</math> לקוחות והתיישבו ב-<math>k</math> שולחנות לפי סדר מסוים (מימוש) <math>X_1=x_1, X_2=x_2,\ldots,X_n=x_n</math>, ולכל <math>1\leq i\leq k</math>, נתון ש-<math>a_i</math> התיישבו ליד השולחן ה-<math>i</math>. ההסתברות לפי המודל המוכלל שסדר כזה יתקבל, הוא

<math>
\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}
</math>,

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

<math>
(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}
</math>.

== היסטוריה ==
אנלוגיית המסעדה הסינית הופיעה לראשונה במאמר משנת 1985 של דייוויד אלדוס<ref>{{Cite book|last=Aldous|first=D. J.|title=École d'Été de Probabilités de Saint-Flour XIII — 1983|year=1985|isbn=978-3-540-15203-3|series=Lecture Notes in Mathematics|volume=1117|pages=1–198|chapter=Exchangeability and related topics|doi=10.1007/BFb0099421}} The restaurant process is described on page 92.</ref>, שם היא יוחסה לג'ים פיטמן (שנתן קרדיט גם ללסטר דובין){{הערה|שם=Pitman19952}}.

== הערות שוליים ==
[[קטגוריה:תהליכים סטוכסטיים]]
{{הערות שוליים}}
__ללא_עריכה__