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

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

דוגמה

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

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

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

דוגמה לצמצום

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

$\Pr(\Pi _{2}=\{\{1\},\{2\}\})=\Pr(\Pi _{3}=\{\{1\},\{2\},\{3\}\})+\Pr(\Pi _{3}=\{\{1,3\},\{2\}\})+\Pr(\Pi _{3}=\{\{1\},\{2,3\}\})={\frac {1}{2}}$

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

$\Pr(\Pi _{2}=\{\{1,2\}\})=\Pr(\Pi _{3}=\{\{1,2\},\{3\}\})+\Pr(\Pi _{3}=\{\{1,2,3\}\})={\frac {1}{2}}$

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

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

דוגמה

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

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

אם סדרה אינסופית של חלוקות מקריות $\Pi _{1},\Pi _{2},...$ כך ש-$\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}$.