חלוקה מקרית של קבוצה

בתורת ההסתברות חלוקה מקרית של קבוצה היא משתנה מקרי המקבל את ערכיו בקבוצת החלוקות של קבוצה. חלוקות מקריות משמשות ביישומים בגנטיקה.

דוגמה

לדוגמה, נגדיר חלוקה מקרית ${\mathrm{\Pi }}_3$ של $N_3=\{1,2,3\}$ באמצעות מתן ההסתברות של כל אחת מחמש ההחלוקות של $N_3$ להתקבל: $\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1\},\{2\},\{3\}\})=\frac{1}{2}$, $\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,2\},\{3\}\})=\frac{1}{6}$, $\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,2,3\}\})=\frac{1}{3}$, $\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,3\},\{2\}\})=\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1\},\{2,3\}\})=0$.

חלוקה מקרית של המספרים הטבעיים

סדרה אינסופית של חלוקות מקריות ${\mathrm{\Pi }}_1,{\mathrm{\Pi }}_2,...$ כך ש-${\mathrm{\Pi }}_i$ חלוקה מקרית של $N_i$ לכל $i=1,2,...$, תקרא חלוקה מקרית של $\mathbb{N}$ (קבוצת כל המספרים הטבעיים) אם לכל שני מספרים טבעיים $m<n$ מתקיים שהצמצום של ${\mathrm{\Pi }}_n$ ל-$N_m$ נותן את ${\mathrm{\Pi }}_m$.

דוגמה לצמצום

נניח ש-${\mathrm{\Pi }}_2$ מתקבלת מהצמצום של ${\mathrm{\Pi }}_3$ מהדוגמה למעלה ל-$N_2=\{1,2\}$. נחשב את ${\mathrm{\Pi }}_2$: ממחיקת המספר 3 מכל אחת מהחלוקות $\{\{1\},\{2\},\{3\}\},\{\{1,3\},\{2\}\},\{\{1\},\{2,3\}\}$ מקבלים את החלוקה $\{\{1\},\{2\}\}$ ולכן

$\mathrm{Pr}({\mathrm{\Pi }}_2=\{\{1\},\{2\}\})=\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1\},\{2\},\{3\}\})+\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,3\},\{2\}\})+\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1\},\{2,3\}\})=\frac{1}{2}$

באופן דומה מקבלים ש-

$\mathrm{Pr}({\mathrm{\Pi }}_2=\{\{1,2\}\})=\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,2\},\{3\}\})+\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,2,3\}\})=\frac{1}{2}$

חלוקה מקרית חילופית של $\{1,...,n\}$

חלוקה מקרית חילופית ${\mathrm{\Pi }}_n$ של $N_n=\{1,...,n\}$ היא חלוקה מקרית של $N_n$ כך שלכל חלוקה $A$ של $N_n$ ולכל תמורה $\theta$ על $N_n$ מתקיים $\mathrm{Pr}({\mathrm{\Pi }}_n=A)=\mathrm{Pr}({\mathrm{\Pi }}_n=\theta (A))$. כלומר, ההסתברות לקבלת חלוקה נשמרת תחת תמורות.

דוגמה

החלוקה המקרית בדוגמה למעלה איננה חילופית. כדי לראות זאת נבחר את התמורה $\theta (1)=3,\theta (2)=2,\theta (3)=1$ ואת החלוקה $A=\{\{1,2\},\{3\}\}$. מצד אחד $\mathrm{Pr}({\mathrm{\Pi }}_n=A)=\frac{1}{6}$ ומהצד השני $\theta (A)=\{\{\theta (1),\theta (2)\},\{\theta (3)\}\}=\{\{3,2\},\{1\}\}=\{\{1\},\{2,3\}\}$ ו- $\mathrm{Pr}({\mathrm{\Pi }}_n=\theta (A))=0$. ראינו ש- $\mathrm{Pr}({\mathrm{\Pi }}_n=A)\ne \mathrm{Pr}({\mathrm{\Pi }}_n=\theta (A))$ ולכן החלוקה המקרית אינה חילופית. אם לעומת זאת נגדיר את ${\mathrm{\Pi }}_3$ באופן הבא: $\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1\},\{2\},\{3\}\})=\frac{1}{2}$, $\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,2\},\{3\}\})=\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,3\},\{2\}\})=\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1\},\{2,3\}\})=\frac{1}{18}$, $\mathrm{Pr}({\mathrm{\Pi }}_3=\{\{1,2,3\}\})=\frac{1}{3}$, נקבל חלוקה מקרית חילופית.

חלוקה מקרית חילופית של המספרים הטבעיים

אם סדרה אינסופית של חלוקות מקריות ${\mathrm{\Pi }}_1,{\mathrm{\Pi }}_2,...$ כך ש-${\mathrm{\Pi }}_i$ חלוקה מקרית חילופית של $N_i$ לכל $i=1,2,...$, היא גם חלוקה מקרית של $\mathbb{N}$ אז היא חלוקה מקרית חילופית של $\mathbb{N}$.

בניית חלוקה מקרית חילופית של המספרים הטבעיים באמצעות תהליך "המסעדה הסינית"

בתהליך המסעדה הסינית הלקוחות הממוספרים $i=1,2,...$ נכנסים למסעדה בזה אחר זה. הלקוח ה-$n$ שנכנס בוחר אם להתיישב ליד שולחן שכבר יושבים לידו בהסתברות שהיא בגודל יחסי למספר האנשים היושבים ליד השולחן או יושב ליד שולחן ריק מאנשים בהסתברות $\frac{1}{n}$. בתהליך זה ניתן להראות שהחלוקה של $n$ הלקוחות הראשונים לשולחנות היא חלוקה מקרית חילופית של $N_n$, והסדרה האינסופית של החלוקות המקריות החילופיות עבור $n=1,2,...$ היא חלוקה מקרית חילופית של $\mathbb{N}$.