תהליך "המסעדה סינית" – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־09:02, 10 במרץ 2024

הפניה ל:

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

בתורת ההסתברות, תהליך "המסעדה הסינית" הוא תהליך סטוכסטי זמן בדיד, המודגם באמצעות מודל של התיישבות לקוחות ליד שולחנות במסעדה. נתונה מסעדה עם אינסוף שולחנות הממוספרים $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 של דיוויד אלדוס^[1], שם היא יוחסה לג'ים פיטמן (אשר ייחס אותה ללסטר דובין)^[2].

הערות שוליים

^ Aldous, D. J. (1985). "Exchangeability and related topics". École d'Été de Probabilités de Saint-Flour XIII — 1983. Lecture Notes in Mathematics. Vol. 1117. pp. 1–198. doi:10.1007/BFb0099421. ISBN 978-3-540-15203-3. The restaurant process is described on page 92.
^ Pitman, Jim (1995). "Exchangeable and Partially Exchangeable Random Partitions". Probability Theory and Related Fields. 102 (2): 145–158. doi:10.1007/BF01213386. MR 1337249.

[1] Aldous, D. J. (1985). "Exchangeability and related topics". École d'Été de Probabilités de Saint-Flour XIII — 1983. Lecture Notes in Mathematics. Vol. 1117. pp. 1–198. doi:10.1007/BFb0099421. ISBN 978-3-540-15203-3. The restaurant process is described on page 92.

[Pitman1995-2] Pitman, Jim (1995). "Exchangeable and Partially Exchangeable Random Partitions". Probability Theory and Related Fields. 102 (2): 145–158. doi:10.1007/BF01213386. MR 1337249.

[1]

[2]

@@ שורה 1: / שורה 1: @@
 #הפניה [[תהליך "המסעדה הסינית"]]
+בתורת [[תורת ההסתברות|ההסתברות]], '''תהליך "המסעדה הסינית"''' הוא [[תהליך סטוכסטי]] [[זמן בדיד וזמן רציף|זמן בדיד]], המודגם באמצעות מודל של התיישבות לקוחות ליד שולחנות במסעדה. נתונה מסעדה עם אינסוף שולחנות הממוספרים <math>1,2,\ldots</math>, ולכל שולחן אינסוף מקומות ישיבה. לקוח <math>1</math> בוחר לשבת על יד שולחן <math>1</math>. לקוח <math>2</math> בהסתברות חצי בוחר לשבת על יד שולחן <math>1</math> עם לקוח <math>1</math>, אחרת, הוא בוחר לשבת לבד על יד שולחן <math>2</math>. בהמשך, כאשר מגיע לקוח <math>n</math>, בהסתברות  <math>\frac{n-1}{n}</math> הוא בוחר באקראי את אחד הלקוחות שכבר יושבים ויושב לידו באותו השולחן (באחד מ-<math>m</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>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>.) תכונה זו של מודל "המסעדה הסינית" מיושמת להבנת תהליכים [[גנטיקה של אוכלוסיות|בגנטיקה של אוכלוסיות]], בניתוח לשוני ובעיבוד תמונות.
+מודל "המסעדה הסינית" הופיעה לראשונה במאמר משנת 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>, שם היא יוחסה [[Jim Pitman|לג'ים פיטמן]] (אשר ייחס אותה ללסטר דובין)<ref name="Pitman1995">{{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&ndash;158|doi=10.1007/BF01213386|mr=1337249|doi-access=free}}</ref>.
+== הערות שוליים ==
+[[קטגוריה:תהליכים סטוכסטיים]]