הכלה והפרדה, בעיית הכובעים, שובך יונים, מסלולי סריג, ספירה לחישוב הסתברות, קצב גדילה וסטירלינג, וקומבינטוריקה ב-ML. זמן משוער: כ-3 שעות כולל התרגול. אין דרישות קדם: כל הכלים שבהם משתמשים כאן מופיעים בתזכורת בתחילת הדף (ובנספח א1 יש עליהם הסבר מלא).
בנספח הזה נעבור לבעיות שבהן הכלים הבסיסיים של הספירה לא מספיקים בצורתם הפשוטה: חפיפה בין מקרים, טענות "בהכרח", מסלולים, וגם הקישור הישיר בין ספירה להסתברות.
אם כבר קראת את נספח א1, אפשר לדלג. אחרת, זה כל מה שצריך:
הכל נשען על הכלים של א1. בסעיף 6 נשתמש בלוגריתם ובקירוב סטירלינג, אבל רק כעובדה שנבדוק מספרית. את ההוכחה שלו נשאיר ללימוד טורי טיילור.
❓ כמה מספרים בין 1 ל-60 מתחלקים ב-2, או ב-3, או ב-5?
נלך בשלבים: (1) שני מאורעות, ריענון, (2) שלושה: למה הנוסחה כזו, (3) הנוסחה הכללית ולמה היא נכונה, (4) מעבדה, (5) "אף אחד" והקשר ל-$\varphi$, (6) גרסת ההסתברות, (7) פונקציות על.
מספרים עד 60 שמתחלקים ב-2 או ב-3: $|A|=30$ (מתחלקים ב-2), $|B|=20$ (ב-3). אם נחבר $30+20=50$ נספור פעמיים את אלה שמתחלקים בשניהם (כלומר ב-6): $\lfloor60/6\rfloor=10$. לכן $|A\cup B|=30+20-10=40$.
עכשיו נוסיף $C$ = "מתחלקים ב-5": $|C|=12$. ננסה: $|A|+|B|+|C|=62$. כמובן ספרנו יותר מדי. נחסיר את הזוגות: $|A\cap B|=10$ (ב-6), $|A\cap C|=6$ (ב-10), $|B\cap C|=4$ (ב-15): $62-20=42$. אבל עכשיו פספסנו! המספרים שמתחלקים בשלושתם (ב-30: אלה 30 ו-60, כלומר $|A\cap B\cap C|=2$) נספרו 3 פעמים בסכום הראשון, ואז הוחסרו 3 פעמים בזוגות, לכן "נעלמו". צריך להוסיף אותם בחזרה: $42+2=44$.
כדי לבדוק שהנוסחה נכונה, נבדוק כמה פעמים נספר כל אזור בציור ונוודא שהתשובה תמיד 1:
| איבר שנמצא ב... | בסכום היחידים $\sum|A_i|$ | בסכום הזוגות $\sum|A_i\cap A_j|$ | בשלשה $|A\cap B\cap C|$ | נטו |
|---|---|---|---|---|
| קבוצה אחת בלבד | +1 | 0 | 0 | 1 |
| שתי קבוצות בדיוק | +2 | −1 | 0 | 1 |
| שלוש הקבוצות | +3 | −3 | +1 | 1 |
כל איבר מהאיחוד נספר בדיוק פעם אחת. זה כל ההסבר.
(הסימון $\sum_{i<j}$ פירושו "סכום על כל הזוגות $i<j$", והסימן מתחלף בכל שלב.)
נבדוק איבר שנמצא ב-$m\ge1$ קבוצות. בסכום היחידים הוא נספר $\binom m1$ פעמים, בסכום הזוגות $\binom m2$ פעמים (כל זוג מתוך הקבוצות ש"שלו"), בשלשות $\binom m3$, וכן הלאה. הנטו:
$$\binom m1-\binom m2+\binom m3-\cdots\pm\binom mm=1.$$ולמה זה 1? ממשפט הבינום (בתזכורת למעלה) עם $a=-1$ ו-$b=1$: $(-1+1)^m=0$, כלומר $\sum_{j=0}^m(-1)^j\binom mj=0$, כלומר $\binom m0-\binom m1+\binom m2-\cdots=0$, ולכן $\binom m1-\binom m2+\cdots=\binom m0=1$. ∎
לרוב השאלה היא "כמה לא מתחלקים באף אחד?". זה פשוט $N-|\bigcup A_i|$. בדוגמה: $60-44=16$. זה בדיוק מספר המספרים עד 60 שזרים ל-60: פונקציית אוילר $\varphi(60)=16$. הצורה הזו נותנת גם נוסחה ידועה: $\varphi(60)=60\left(1-\tfrac12\right)\left(1-\tfrac13\right)\left(1-\tfrac15\right)=16$, כי הכפל פותח את אותה הכלה והפרדה.
אותה נוסחה, עם $P$ במקום $|\cdot|$: $P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)$.
אם כל $k$ המאורעות "שווים" (כל חיתוך של $k$ מהם בעל אותה הסתברות $p_k$), הנוסחה מתכנסת ל-$\sum_{k=1}^n(-1)^{k+1}\binom nkp_k$. כי יש $\binom nk$ חיתוכים של $k$ מאורעות. זה בדיוק מה שנעשה בבעיית הכובעים (סעיף 2).
כמה דרכים יש לשייך 5 נקודות מובחנות ל-3 אשכולות (clusters), כך שכל אשכול מקבל לפחות נקודה אחת? הכל: $3^5=243$. נחסר את אלה שבהם אשכול מסוים ריק. תהי $A_i$ = "אשכול $i$ ריק": $|A_i|=2^5$ (הנקודות בוחרות מבין שני האחרים), $|A_i\cap A_j|=1^5$, $|A_1\cap A_2\cap A_3|=0$. לפי הכלה והפרדה:
$$3^5-\left[3\cdot2^5-3\cdot1^5+0\right]=243-93=150.$$בכלליות: $\sum_{j=0}^k(-1)^j\binom kj(k-j)^n$. ב-ML: זה מספר השיוכים האפשריים של $n$ דגימות ל-$k$ אשכולות ללא אשכול ריק, שחשוב להבין כשמאתחלים k-means. והסיכוי ששיוך אקראי לא משאיר אשכול ריק: $150/243\approx0.617$.
תרגיל 1.1 הכלה והפרדה לשלוש קבוצות ⭐
ב-100 סטודנטים: 60 לומדים מדעי המחשב, 50 מתמטיקה, 40 פיזיקה. 30 לומדים מ"ח ומתמטיקה, 20 מ"ח ופיזיקה, 15 מתמטיקה ופיזיקה, ו-10 לומדים את שלושתם. כמה לא לומדים אף אחד מהשלושה?
איחוד: $60+50+40-(30+20+15)+10=95$. לכן $100-95=5$ לא לומדים אף אחד.
תרגיל 1.2 גרסת ההסתברות ⭐⭐
$P(A)=0.5$, $P(B)=0.4$, $P(C)=0.3$; $P(A\cap B)=0.2$, $P(A\cap C)=0.15$, $P(B\cap C)=0.1$; $P(A\cap B\cap C)=0.05$. מה $P(A\cup B\cup C)$, ומה הסיכוי שאף אחד לא קרה?
$1.2-0.45+0.05=0.8$. אף אחד: $0.2$.
תרגיל 1.3 מציאת טעות בנוסחה ⭐⭐
תלמיד כותב: $P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)$ (שכח את השלשה). הראה בדוגמה קטנה שהנוסחה שגויה.
נקח $A=B=C$ עם $P=0.5$. האיחוד הוא $A$ עצמו: $0.5$. הנוסחה של התלמיד נותנת $1.5-1.5=0$, שגוי. עם השלשה: $1.5-1.5+0.5=0.5$ ✔.
תרגיל 1.4 הכלה והפרדה + משלים ⭐⭐
כמה מספרים בין 1 ל-100 אינם מתחלקים ב-2, ב-3 ולא ב-7?
$|A|=50,\ |B|=33,\ |C|=14$; זוגות (6, 14, 21): $16,\ 7,\ 4$; שלשה (42): $2$. איחוד: $97-27+2=72$. אף אחד: $100-72=28$.
תרגיל 1.5 פונקציות על + הסתברות ⭐⭐⭐
4 דגימות משויכות באקראי ובאחידות ל-3 אשכולות. מה הסיכוי שכל האשכולות לא ריקים?
כל השיוכים: $3^4=81$. על: $3^4-3\cdot2^4+3\cdot1^4=81-48+3=36$. הסיכוי: $\frac{36}{81}=\frac49\approx0.444$.
הכלה והפרדה מתחילה לשרת אותנו בבעיה מפורסמת: מה הסיכוי שאף אחד לא מקבל את מה ששייך לו?
❓ $n$ אנשים זורקים את הכובעים שלהם לערימה, וכל אחד מוציא כובע אקראי. מה הסיכוי שאף אחד לא קיבל את הכובע שלו?
נלך בשלבים: (1) מקרים קטנים, (2) הנוסחה בעזרת הכלה והפרדה, (3) התוצאה המפתיעה, (4) הרחבות.
סידור ללא נקודת קבע נקרא derangement, ומספרם מסומן $D_n$. מצאנו $D_1=0$, $D_2=1$, $D_3=2$.
נגדיר $A_i$ = "אדם $i$ קיבל את הכובע שלו". אנחנו רוצים את מספר הסידורים שאינם באף $A_i$, כלומר $n!-|\bigcup A_i|$.
לפי הטריק הסימטרי (שלב 6 בסעיף 1):
$$\Big|\bigcup A_i\Big|=\sum_{k=1}^n(-1)^{k+1}\binom nk(n-k)!=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!},$$כי $\binom nk(n-k)!=\frac{n!}{k!\,(n-k)!}(n-k)!=\frac{n!}{k!}$. לכן:
$$D_n=n!-\Big|\bigcup A_i\Big|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\ ,\qquad P(\text{אף אחד})=\frac{D_n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}=1-1+\frac1{2!}-\frac1{3!}+\cdots$$הסיכוי כמעט לא תלוי ב-$n$! כבר מ-$n=5$ הוא בערך 0.3667, ועם עוד אנשים הוא מתכנס ל-$0.36788\ldots$. מספר זה הוא $1/e$ (כאשר $e\approx2.718$ הוא הקבוע המתמטי הידוע), כי הסכום הוא תחילת הטור של $e^{-1}$. (ההוכחה דורשת את פיתוח טיילור של $e^x$, שלא נעסוק בו כאן; את הערך אפשר לבדוק מספרית בטבלה.) המסקנה: בין 5 אנשים או חמישה מיליון, ההסתברות שאף אחד לא יקבל את הכובע שלו היא כ-37%. כל אחד בנפרד מקבל את שלו בסיכוי קטן ($1/n$), אבל יש הרבה אנשים, ושני האפקטים מתקזזים כמעט בדיוק.
אדם 1 מקבל כובע של אדם $j\ne1$ ($n-1$ בחירות). שני מקרים: (א) אדם $j$ מקבל את הכובע של 1 (החלפה), ושאר $n-2$ בלי נקודת קבע: $D_{n-2}$. (ב) אדם $j$ לא מקבל את הכובע של 1: אפשר לחשוב על הכובע של 1 כ"כובע של $j$", ואז יש $n-1$ אנשים ללא נקודת קבע: $D_{n-1}$. לכן $D_n=(n-1)(D_{n-2}+D_{n-1})$. (זה מה שהמעבדה משתמשת בו.)
לכל אדם הסיכוי לקבל את שלו הוא $1/n$, ויש $n$ אנשים. בתורת ההסתברות מוכיחים (בעזרת מושג ה"תוחלת", כלומר הממוצע לטווח ארוך) שהמספר הממוצע של "נקודות קבע" הוא $n\cdot\frac1n=1$, לכל $n$, למרות שלעיתים קרובות (37%) מספרן 0 (ולעיתים 2 או יותר). זה דוגמה ליעילות של "שיטת האינדיקטורים".
ערבוב אקראי של דוגמאות או תוויות הוא תמורה אקראית. כשמשווים מודל ל"baseline אקראי" (נניח, שיוך תוויות באקראי), כדאי לדעת שתמורה אקראית משאירה בממוצע בדיוק פריט אחד במקומו, ושב-37% מהמקרים אף אחד לא נשאר במקומו. גם "Secret Santa" ו"מבחני פרמוטציה" בנויים על אותה מתמטיקה.
תרגיל 2.1 ספירה ישירה ⭐
רשום את כל ה-derangements של $\{1,2,3,4\}$ שמתחילים ב-2 ("אדם 1 מקבל את הכובע של 2"), וספור. מה $D_4$?
שלושה: $(2,1,4,3)$, $(2,3,4,1)$, $(2,4,1,3)$. מכיוון שהסימטריה מתאימה לכל אחד מ-3 הכובעים האפשריים של אדם 1: $D_4=3\cdot3=9$ ✔ (נוסחת הנסיגה: $3\cdot(D_3+D_2)=3\cdot3=9$).
תרגיל 2.2 הפעלת הנוסחה ⭐
חשב את $P(\text{אף אחד})$ עבור $n=5$ בעזרת $\sum_{k=0}^5\frac{(-1)^k}{k!}$.
$1-1+\frac12-\frac16+\frac1{24}-\frac1{120}=\frac{44}{120}\approx0.3667$ ($D_5=44$).
תרגיל 2.3 בחר ואז שבץ ⭐⭐
5 אנשים מקבלים כובעים באקראי. מה הסיכוי שבדיוק שניים קיבלו את שלהם?
בוחרים את השניים: $\binom52=10$. השלושה האחרים בלי נקודת קבע: $D_3=2$. סה"כ $20$ מתוך $120$: $\frac16$.
תרגיל 2.4 קוד ⭐⭐
דמה "Secret Santa" ל-10 אנשים: ערבב אקראית את range(10) ובדוק באיזה חלק מהמקרים אין נקודת קבע. השווה ל-$\sum_{k=0}^{10}\frac{(-1)^k}{k!}\approx0.36788$.
import numpy as np
from math import factorial
rng = np.random.default_rng(0)
n, T = 10, 200_000
hits = sum(not np.any(rng.permutation(n) == np.arange(n)) for _ in range(T))
exact = sum((-1)**k / factorial(k) for k in range(n + 1))
print(hits / T, exact) # both ~ 0.3679עד עכשיו חישבנו כמה דברים קורים. לפעמים אפשר להוכיח שמשהו חייב לקרות, בלי לחשב כמה, ובלי לדעת איך.
❓ בקבוצה של 13 אנשים, האם בהכרח יש שניים שנולדו באותו חודש?
אם מכניסים $m$ יונים ל-$n$ שובכים ו-$m>n$, בשובך אחד לפחות יש שתי יונים או יותר. בגרסה המדויקת: יש שובך עם לפחות $\lceil m/n\rceil$ יונים.
העיקרון לא אומר איזה שובך, ולא אילו יונים, רק שבהכרח קיים אחד כזה. 13 אנשים ו-12 חודשים: בלי לדעת כלום על האנשים, אי אפשר שכולם יהיו בחודשים שונים. הטיעון הוא בבסיסו "אין מספיק מקום".
העיקרון עצמו טריוויאלי. האמנות היא להגדיר את היונים והשובכים נכון. דוגמה:
בחר 6 מספרים כלשהם מ-$\{1,\dots,10\}$. הראה ששניים מהם סכומם 11. השובכים: הזוגות $\{1,10\},\{2,9\},\{3,8\},\{4,7\},\{5,6\}$ (חמישה שובכים, כל אחד סכומו 11). היונים: 6 המספרים שנבחרו, כל אחד נכנס לשובך שלו. 6 יונים ב-5 שובכים: שני מספרים באותו שובך, ובדיוק בזוג כזה סכומם 11. ∎
לכל $n$ מספרים שלמים יש רצף עוקב שסכומו מתחלק ב-$n$. הוכחה: יהיו $a_1,\dots,a_n$. נגדיר סכומים חלקיים $S_0=0$, $S_1=a_1$, $S_2=a_1+a_2$, ..., $S_n$. אלה $n+1$ מספרים (יונים). נסתכל על השארית של כל אחד בחלוקה ב-$n$: יש רק $n$ שאריות אפשריות (שובכים). לכן שניים, $S_i$ ו-$S_j$ ($i<j$), בעלי אותה שארית, ולכן $S_j-S_i=a_{i+1}+\cdots+a_j$ מתחלק ב-$n$. ∎
שובך יונים עוסק ב"בהכרח" (הסתברות 1), בעוד שההסתברות עוסקת במה שביניהם. דוגמה, יום ההולדת: כמה אנשים צריך כדי שלשניים מהם יהיה יום הולדת באותו יום (365 ימים בשנה, כל יום שווה-סיכוי)? שובך יונים מבטיח התאמה רק ב-366 אנשים. אבל החישוב ההסתברותי (בעזרת משלים וכלל הכפל: $1-\frac{365\cdot364\cdots(365-n+1)}{365^n}$) מראה שכבר ב-23 אנשים הסיכוי להתאמה הוא 50.7%. ההסתברות מספרת מה קורה לפני שהוודאות מגיעה.
תרגיל 3.1 שובך יונים ישיר ⭐
כמה אנשים צריך כדי להבטיח ששלושה מהם נולדו באותו חודש?
נשתמש בגרסה המדויקת: $\lceil m/12\rceil\ge3$ כאשר $m\ge25$. כלומר 25 אנשים (ב-24 אפשר שכל חודש בדיוק פעמיים).
תרגיל 3.2 בחירת שובכים ⭐⭐
5 נקודות נבחרות בריבוע $2\times2$. הוכח ששתיים מהן במרחק של לכל היותר $\sqrt2$.
נחלק את הריבוע לארבעה ריבועי יחידה (שובכים). 5 נקודות: שתיים באותו ריבוע יחידה. אלכסון של ריבוע יחידה הוא $\sqrt2$, ולכן המרחק בין שתי נקודות בתוכו לכל היותר $\sqrt2$. ∎
תרגיל 3.3 סכומים חלקיים (אתגר) ⭐⭐⭐
הראה שבין כל 7 מספרים שלמים יש רצף עוקב לא ריק שסכומו מתחלק ב-7. השתמש בשיטה של שלב 3, והדגם על 4, 8, 11, 3, 5, 9, 10.
סכומים חלקיים: $0,4,12,23,26,31,40,50$. שאריות מודולו 7: $0,4,5,2,5,3,5,1$. שארית 5 מופיעה שלוש פעמים ($S_2=12$, $S_4=26$, $S_6=40$). ניקח את הראשונים: $S_4-S_2=26-12=14=a_3+a_4=11+3$, וזה מתחלק ב-7 ✔.
תרגיל 3.4 ML: דחיסה ⭐⭐
למה אין אלגוריתם דחיסה ללא אובדן שמקצר כל קובץ בן 1,000 ביטים?
קבצים באורך בדיוק 1,000: $2^{1000}$. קבצים קצרים יותר (אורך 0 עד 999): $2^{1000}-1$. אם כל קובץ היה מקוצר, היינו ממפים $2^{1000}$ "יונים" ל-$2^{1000}-1$ "שובכים", ושניים היו מתנגשים ולא היה אפשר לשחזר אותם בדיוק. ∎
עד עכשיו ספרנו בחירות וסידורים. הכלי הבא סופר מסלולים, ויש לו קשר ישיר למשולש פסקל ולהליכה אקראית.
❓ אני בפינה השמאלית-תחתונה של רשת $4\times4$ ורוצה להגיע לפינה הימנית-עליונה, כשמותר לזוז רק ימינה או למעלה. כמה מסלולים?
כל מסלול הוא רצף של 8 צעדים: 4 צעדים ימינה (R) ו-4 צעדים למעלה (U). מסלול נקבע לחלוטין על ידי באילו 4 מקומות מתוך 8 עומדים ה-R (השאר הם U). זה הטריק "בחר מקומות" (מופיע בתזכורת למעלה):
$$\binom84=70.$$מספר המסלולים מהפינה $(0,0)$ ל-$(a,b)$, כשכל צעד הוא ימינה או למעלה, הוא:
$$\binom{a+b}{a}=\binom{a+b}{b}=\frac{(a+b)!}{a!\,b!}.$$הנימוק: יש $a+b$ צעדים בסך הכל, מהם $a$ ימינה. בוחרים באילו $a$ מקומות (מתוך $a+b$) עומדים צעדי ה-"ימינה".
כדי להגיע לנקודה $(i,j)$, האחרון בצעד בא משמאל (מ-$(i-1,j)$) או מלמטה (מ-$(i,j-1)$). לפי כלל החיבור:
$$\text{paths}(i,j)=\text{paths}(i-1,j)+\text{paths}(i,j-1).$$זה בדיוק כלל פסקל! ברשת, המספרים ליד כל נקודה יוצרים את משולש פסקל ה"מסובב". וגם בכיוון ההפוך: "שני הסיפורים" (ספירה ישירה ונסיגה) מסכימים.
רצף של $n$ הטלות מטבע הוא מסלול: עץ = צעד ימינה, פלי = צעד למעלה. מספר הרצפים עם $k$ עצים הוא $\binom nk$, ולכן מספר המסלולים שמגיעים לנקודה מסוימת בסוף הוא $\binom nk$. זה מקבל משמעות מלאה בהליכה אקראית ובשרשראות מרקוב (תהליכים שבהם כל צעד תלוי רק במצב הנוכחי).
בכלל פסקל יש רעיון מרכזי של תכנות דינמי: במקום לספור (או לרשום) מיליוני מסלולים, מחשבים לכל נקודה את מספר המסלולים אליה מתוך אלה של שכניה. אותו עיקרון מניע אלגוריתמים ב-ML שסוכמים על "המון מסלולים אפשריים": אלגוריתם Forward של HMM וכן Viterbi מחשבים סכום או מקסימום מעל $k^T$ רצפי מצבים מוסתרים בזמן $O(Tk^2)$, בדיוק כמו כלל פסקל.
תרגיל 4.1 בחר מקומות ⭐
כמה מסלולים בין $(0,0)$ ל-$(5,3)$ בצעדי ימינה/למעלה?
8 צעדים, מהם 5 ימינה: $\binom85=\binom83=56$.
תרגיל 4.2 מסלולים דרך נקודה ⭐⭐
ברשת $5\times5$, כמה מסלולים מ-$(0,0)$ ל-$(5,5)$ עוברים דרך $(2,3)$?
$(0,0)\to(2,3)$: $\binom52=10$. $(2,3)\to(5,5)$: 3 ימינה ו-2 למעלה: $\binom53=10$. סה"כ $10\cdot10=100$.
תרגיל 4.3 מסלולים שנמנעים ⭐⭐
ברשת $3\times3$, כמה מסלולים מ-$(0,0)$ ל-$(3,3)$ לא עוברים דרך $(1,1)$?
הכל: $\binom63=20$. דרך $(1,1)$: $\binom21\cdot\binom42=2\cdot6=12$. נמנעים: $20-12=8$.
תרגיל 4.4 הליכה אקראית ⭐⭐
מטילים מטבע הוגן 10 פעמים (עץ = +1, פלי = −1). מה הסיכוי שאחרי 10 צעדים הסכום הוא בדיוק +4?
סכום +4 אומר $h-t=4$ ו-$h+t=10$. כמה עצים?
$h=7$, $t=3$. מספר הרצפים: $\binom{10}7=120$ מתוך $2^{10}=1024$. הסיכוי: $\frac{120}{1024}\approx0.117$.
ראינו הרבה כלי ספירה. עכשיו נחבר אותם ישירות להסתברות: איך הופכים בעיית הסתברות לבעיית ספירה, ואיפה זה מסוכן.
❓ בכל בעיית הסתברות עם תוצאות שוות-סיכוי, הדרך היא $P=\frac{|A|}{|\Omega|}$. מה צריך להיזהר ממנו, ואיך נראית התפלגות מבחירה בלי החזרה?
נלך בשלבים: (0) כללי ברזל, (1) בחירה בלי החזרה (היפרגאומטרית), (2) "בונים אובייקט בשדות" (ידי פוקר), (3) כדורים בתאים, (4) בינומי מספירה.
בחפיסה של $N$ פריטים, $K$ מהם "מיוחדים" (למשל 13 לבבות מתוך 52). שולפים $n$ בלי החזרה. מה הסיכוי לבדיוק $k$ מיוחדים?
דוגמה: 5 קלפים, בדיוק 2 לבבות: $\frac{\binom{13}2\binom{39}3}{\binom{52}5}=\frac{78\cdot9139}{2598960}=\frac{712842}{2598960}\approx0.274$. הנרמול ($\sum_kP(k)=1$) נובע מזהות ונדרמונד: ספירת כל הבחירות לפי מספר האדומים $j$ שנבחרו נותנת $\sum_j\binom Kj\binom{N-K}{n-j}=\binom Nn$, כלומר מונים שמסתכמים בדיוק למכנה.
כדי לספור ידיים מסוג מסוים, נבנה יד "כמו טופס": כל שדה הוא בחירה, ומכפילים. דוגמה, זוג אחד (שני קלפים באותו ערך ושלושה קלפים אחרים בערכים שונים זה מזה ומהזוג):
סה"כ $13\cdot6\cdot220\cdot64=1{,}098{,}240$, ולכן $P=\frac{1098240}{2598960}\approx0.4226$.
| יד | ספירה | מספר ידיים | הסתברות |
|---|---|---|---|
| זוג אחד | $13\cdot\binom42\cdot\binom{12}3\cdot4^3$ | 1,098,240 | 0.4226 |
| שני זוגות | $\binom{13}2\binom42^2\cdot44$ | 123,552 | 0.0475 |
| שלישייה | $13\cdot\binom43\cdot\binom{12}2\cdot4^2$ | 54,912 | 0.0211 |
| פול האוס | $13\cdot\binom43\cdot12\cdot\binom42$ | 3,744 | 0.00144 |
| רביעייה | $13\cdot48$ | 624 | 0.00024 |
"בחר זוג ($13\cdot6=78$), ואז כל שלושה קלפים מתוך 50 הנותרים": $78\cdot\binom{50}3=1{,}528{,}800$. יותר מהנכון ($1{,}098{,}240$)! כי "שלושה מתוך 50" כוללים ידיים עם זוג נוסף (נספרות פעמיים, בכל "איזה זוג בחרתי"), שלישיות ופול האוס. הכלל: בנה כל אובייקט בצורה שבה הוא נקבע בדרך אחת בלבד (קודם הזוג, אחר כך שלושה ערכים שונים).
זורקים $n$ כדורים לתוך $k$ תאים באקראי (כל כדור בוחר תא באחידות ובלתי-תלוי). זה מודל לטבלאות hash. ה"רצפים" (איזה כדור בכל תא) שוות-סיכוי, ויש $k^n$ מהם:
2 כדורים ב-2 תאים: מספר "הספירות" (כוכבים וקווים) הוא 3: $(2,0),(1,1),(0,2)$. אבל הן לא שוות-סיכוי: ברצפים, $(1,1)$ יכול לקרות בשתי דרכים (הכדור הראשון בתא 1 והשני בתא 2, או להפך), לעומת $(2,0)$ בדרך אחת. ההסתברויות האמיתיות: $\frac14,\frac12,\frac14$, ולא $\frac13$ לכל אחת. כוכבים וקווים סופר ספירות, והסתברות דורשת לספור רצפים.
$n$ ניסויים בלתי-תלויים, בכל אחד הצלחה בסיכוי $p$ (וכישלון $q=1-p$). מה הסיכוי לבדיוק $k$ הצלחות?
כש-$p\ne\frac12$, רצפים שונים אינם שווי-סיכוי (SSFSF שונה מ-FFFFF). אבל כל הרצפים עם אותו $k$ שווים, ולכן "מספר רצפים × הסתברות כל אחד" עובד. זו הסיבה שהסתברות אינה רק ספירה: היא ספירה משוקללת.
דוגמה: 5 הטלות של מטבע מוטה עם $p=0.3$ לעץ, בדיוק 2 עצים: $\binom52\cdot0.3^2\cdot0.7^3=10\cdot0.09\cdot0.343\approx0.3087$. משפט הבינום מבטיח שהסכום על כל $k$ הוא $(p+q)^n=1$ (כי $p+q=1$).
תרגיל 5.1 היפרגאומטרית ⭐
מחלקים 5 קלפים מחפיסה. מה הסיכוי שיהיו בדיוק 2 לבבות? (בדוק במעבדה.)
$\frac{\binom{13}2\binom{39}3}{\binom{52}5}=\frac{712842}{2598960}\approx0.2743$.
תרגיל 5.2 בניית יד בשדות ⭐⭐
מה הסיכוי לפול האוס (שלושה מאותו ערך וזוג מערך אחר) ב-5 קלפים?
ערך השלישייה: 13; סוגיה: $\binom43=4$; ערך הזוג: 12; סוגיו: $\binom42=6$. סה"כ $13\cdot4\cdot12\cdot6=3744$, ו-$\frac{3744}{2598960}\approx0.00144$.
תרגיל 5.3 מציאת טעות (ספירה כפולה) ⭐⭐
סטודנט סופר ידיים עם "לפחות אס אחד" כך: "בוחרים אס (4), ואז 4 קלפים מ-51: $4\binom{51}4$". מה הבעיה, ואיך מחשבים נכון?
יד עם 2 אסים נספרת פעמיים (איזה אס "בחרתי"), עם 3 אסים שלוש פעמים וכו'. נכון: משלים. ללא אסים: $\binom{48}5$. $P(\text{לפחות אס})=1-\frac{\binom{48}5}{\binom{52}5}=1-\frac{1712304}{2598960}\approx0.341$.
תרגיל 5.4 כדורים בתאים ⭐⭐
3 כדורים נזרקים באקראי ל-5 תאים. מה הסיכוי שכולם בתאים שונים? ומה הסיכוי שתא 1 ריק?
שונים: $\frac{5\cdot4\cdot3}{5^3}=\frac{60}{125}=0.48$. תא 1 ריק: $\left(\frac45\right)^3=0.512$.
תרגיל 5.5 בינומי ⭐⭐
מטבע מוטה עם $p=0.3$ לעץ מוטל 5 פעמים. חשב את $P(k)$ לכל $k=0,\dots,5$, ובדוק שהסכום 1.
$k=0$: $0.7^5=0.1681$. $k=1$: $5\cdot0.3\cdot0.7^4=0.3602$. $k=2$: $0.3087$. $k=3$: $10\cdot0.3^3\cdot0.7^2=0.1323$. $k=4$: $5\cdot0.3^4\cdot0.7=0.02835$. $k=5$: $0.3^5=0.00243$. סכום: $1$ ✔.
תרגיל 5.6 הכלה והפרדה + היפרגאומטרית (אתגר) ⭐⭐⭐
מה הסיכוי שב-5 קלפים מופיעים כל ארבעת הסוגים?
$A_i$ = "אין קלף מסוג $i$". חפש את $P(\bigcup A_i)$ בהכלה והפרדה, ואז משלים.
$|A_i|=\binom{39}5$, $|A_i\cap A_j|=\binom{26}5$, $|A_i\cap A_j\cap A_k|=\binom{13}5$, ארבעת הסוגים ביחד: 0. $|\bigcup|=4\binom{39}5-6\binom{26}5+4\binom{13}5=2303028-394680+5148=1913496$. לכן $P(\text{כולם})=1-\frac{1913496}{2598960}\approx0.2637$. בדיקה ישירה: סוג אחד מופיע פעמיים ($4\binom{13}2\cdot13^3=685464$), כלומר $0.2637$ ✔.
המספרים שמופיעים בספירה גדלים מהר מאוד. בסעיף הבא נראה כמה, ואיך מטפלים בהם בלי לחשב עצרות ענקיות.
❓ כמה גדול $n!$? והאם יש דרך לדעת בערך כמה גדול $\binom{n}{k}$ בלי לחשב?
נלך בשלבים: (1) הדירוג של הגדילה, (2) נוסחת סטירלינג, (3) $\binom nk$ ואנטרופיה, (4) טיפים לחישוב בקוד.
| $n$ | $n^2$ | $2^n$ | $n!$ | $n^n$ |
|---|---|---|---|---|
| 10 | 100 | 1,024 | 3,628,800 | $10^{10}$ |
| 20 | 400 | $\approx10^6$ | $2.4\cdot10^{18}$ | $10^{26}$ |
סדר הגדילה: פולינום $\ll$ מעריכית $\ll$ עצרת $\ll$ $n^n$. כבר ב-$n=20$ העצרת גדולה פי $10^{12}$ מ-$2^n$.
הקירוב הופך מדויק יחסית ככל ש-$n$ גדל (השגיאה היחסית בערך $\frac1{12n}$). את ההוכחה נשאיר ללימוד מתקדם יותר, ופה נבדוק מספרית. שים לב שבשימוש הנפוץ ב-ML מספיק הפשוט: $\ln n!\approx n\ln n-n$.
ננסה להעריך כמה מחרוזות בינאריות באורך $n$ יש עם בדיוק $qn$ אחדות. נסמן ב-$H(q)$ את האנטרופיה הבינארית:
$$H(q)=-q\log_2q-(1-q)\log_2(1-q)\qquad(\text{ביטים}).$$אז:
$$\binom n{qn}\approx\frac{2^{\,n\,H(q)}}{\sqrt{2\pi\,n\,q(1-q)}}\ ,\qquad\text{ובקירוב גס: }\binom n{qn}\approx2^{\,n\,H(q)}.$$הקירוב אומר שיש בערך $2^{nH(q)}$ מחרוזות כאלה, ולכן כדי "לתת שם" לאחת מהן צריך $\log_2$ של זה $\approx nH(q)$ ביטים, כלומר $H(q)$ ביטים לכל סימן. כש-$q=\frac12$ זה 1 ביט לסימן (אין רמז). ככל ש-$q$ רחוק מ-$\frac12$ (נניח 0.1), יש פחות מחרוזות טיפוסיות וצריך פחות ביטים ($H(0.1)\approx0.47$). זו האנטרופיה (מושג מרכזי בתורת האינפורמציה, ושימושי ב-ML), והיא בעצם ספירה. בהתחלה הייתה קומבינטוריקה.
math.lgamma(n+1) נותן $\ln n!$.math.comb(n, k) בפייתון מחזיר מספר שלם מדויק (אין גלישה). לשימוש בהסתברות: חשב $\ln\binom nk+k\ln p+(n-k)\ln(1-p)$ ואז exp.from math import lgamma, log, exp
def log_binom(n, k):
return lgamma(n + 1) - lgamma(k + 1) - lgamma(n - k + 1)
def binom_pmf(n, k, p):
return exp(log_binom(n, k) + k * log(p) + (n - k) * log(1 - p))
print(binom_pmf(1000, 500, 0.5)) # ~0.02523 (no overflow!)
תרגיל 6.1 השוואת קצבים ⭐
מי גדול יותר: $20!$ או $2^{60}$?
$20!\approx2.43\cdot10^{18}$ ו-$2^{60}\approx1.15\cdot10^{18}$. העצרת גדולה בפי 2 בערך.
תרגיל 6.2 הערכה עם סטירלינג ⭐⭐
כמה ספרות יש ל-$52!$ (מספר הסידורים של חפיסת קלפים)? השתמש ב-$\ln n!\approx n\ln n-n+\frac12\ln(2\pi n)$.
$\ln52!\approx52\ln52-52+\tfrac12\ln(2\pi\cdot52)\approx205.46-52+2.89=156.35$. לכן $\log_{10}52!\approx\frac{156.35}{2.3026}=67.9$, כלומר $52!\approx8\cdot10^{67}$ ו-68 ספרות. (הערך האמיתי: $8.07\cdot10^{67}$.) כל חפיסה מעורבת היטב היא כנראה סידור שמעולם לא התרחש.
תרגיל 6.3 $\binom{n}{n/2}$ ⭐⭐
הראה בעזרת הנוסחה של שלב 3 ש-$\binom{n}{n/2}\approx\frac{2^n}{\sqrt{\pi n/2}}$, והעריך את $\binom{1000}{500}/2^{1000}$.
$q=\frac12$: $H(\tfrac12)=1$ ו-$2\pi nq(1-q)=\frac{\pi n}2$. לכן $\binom n{n/2}\approx\frac{2^n}{\sqrt{\pi n/2}}$. ל-$n=1000$: $\frac1{\sqrt{500\pi}}\approx0.0252$. כלומר מבין כל $2^{1000}$ מחרוזות, רק כ-2.5% הן עם בדיוק 500 אחדות. (זה הסיכוי ש-1000 הטלות מטבע ייתנו בדיוק 500 עצים.)
תרגיל 6.4 קוד: יציבות נומרית ⭐⭐
למה factorial(1000)/(factorial(500)**2) בפלואט נכשל, ואיך מחשבים את אותו דבר בלוגים?
ב-float64 factorial(1000) חורג (גדול ממש מ-$10^{308}$), ולכן התוצאה inf או שגיאה. בלוגים: exp(lgamma(1001) - 2*lgamma(501) - 1000*log(2)) נותן $\binom{1000}{500}/2^{1000}\approx0.02523$ בלי גלישה.
עכשיו אפשר לראות איפה כל המספרים האלה מופיעים ב-ML: "גן החיות" של ספירה.
❓ באילו מקומות ב-ML נתקלים בספירה, ומה אנחנו לומדים מגודל המספר?
| מה סופרים | הנוסחה | גודל טיפוסי | המשמעות |
|---|---|---|---|
| תתי-קבוצות של $d$ פיצ'רים | $2^d$ | $d=50$: $\approx10^{15}$ | בחירת פיצ'רים בכוח גס בלתי-אפשרית |
| פונקציות בוליאניות על $d$ ביטים | $2^{2^d}$ | $d=4$: 65,536; $d=6$: $1.8\cdot10^{19}$ | למה חייבים להניח הנחות על המבנה (inductive bias) |
| תיוגים בינאריים של $n$ נקודות | $2^n$ | $n=20$: מיליון | מושג "ניפוץ" (shattering) ו-VC dimension: מחלקה "מנפצת" $n$ נקודות אם היא מייצרת את כל $2^n$ התיוגים |
| זוגות דוגמאות | $\binom n2$ | $n=10^6$: $5\cdot10^{11}$ | למה מטריצות מרחקים לא מתאימות לדאטה גדול |
| mini-batches בגודל $B$ מתוך $N$ | $\binom NB$ | $N=10^4$, $B=32$: $\approx4\cdot10^{92}$ | למה אין שתי ריצות אימון זהות בלי seed |
| סדרי ערבוב של $N$ דוגמאות | $N!$ | $N=52$: $8\cdot10^{67}$ | עוצמת המילה "אקראי" |
| וקטורי bag-of-words | $\binom{n+V-1}{V-1}$ | $V=10^4$, $n=100$: עצום | ההבדל בין רצף לספירה |
| שיוכים של $n$ נקודות ל-$k$ אשכולות | $k^n$; בלי אשכול ריק: surjections (סעיף 1) | $n=100$, $k=3$: $5\cdot10^{47}$ | למה k-means מוצא רק מינימום מקומי |
| התנגשויות hash | שובך יונים / יום ההולדת | $\sqrt{k}$ מפתחות מספיקים | "בטוח" לעומת "סביר" |
| סימטריות ברשת עם $h$ יחידות חבויות | $h!$ | $h=64$: $10^{89}$ | אותו מודל נראה "שונה" אחרי ערבוב יחידות: בעיית זהות בלמידה |
בשימוש ב-ML כמעט תמיד המספרים האלה עצומים. זו הסיבה שעוזרים לנו שלושה כלים: הסתברות (במקום לספור הכל, מתארים "כמה סביר"), לוגים (במקום להתמודד עם מספרים ענקיים), והנחות מבנה (שמצמצמות את המרחב).
בלי כותרת טכניקה. כל התרגילים משלבים כמה כלים מנספחי א1 ו-א2 (הטכניקה רשומה בפתרון).
תרגיל מ.1 ⭐⭐⭐
5 גברים ו-4 נשים מסתדרים בשורה כך שאין שתי נשים צמודות. כמה סידורים?
קודם סדר את הגברים. כמה "רווחים" נוצרים ביניהם ובקצוות?
טכניקת הרווחים (gaps). סידור 5 הגברים: $5!=120$. נוצרים 6 רווחים (4 בין גברים ו-2 בקצוות). הנשים נכנסות לרווחים שונים (אחרת שתיים יהיו צמודות): בוחרים 4 מתוך 6 רווחים ומסדרים אותן בהם: $\binom64\cdot4!=15\cdot24=360$. סה"כ $120\cdot360=43{,}200$.
תרגיל מ.2 ⭐⭐⭐
מטילים מטבע הוגן 7 פעמים. מה הסיכוי שלא יופיעו שני עצים רצופים?
אותה טכניקה: קודם הפלים, אחר כך ה"רווחים" שבהם עצים יכולים לשבת. לכל $k$ מספר עצים, כמה פלים יש?
רווחים + בחר מקומות. עם $k$ עצים יש $7-k$ פלים, ו-$8-k$ רווחים (בין הפלים ובקצוות). העצים נכנסים לרווחים שונים: $\binom{8-k}k$. סה"כ $\sum_{k=0}^4\binom{8-k}k=1+7+15+10+1=34$ מתוך $2^7=128$: $\frac{34}{128}\approx0.266$.
תרגיל מ.3 ⭐⭐
בכמה דרכים אפשר לבחור 3 מושבים לא סמוכים מתוך 10 מושבים בשורה?
בחר 3 מושבים, אחר כך "כווץ" את הרווח: אם אסור שיהיו צמודים, הורד 0, 1, 2 מהמספרים המוזמנים.
התאמה חח"ע + צירופים. אם המושבים $a<b<c$ לא סמוכים, אז $a<b-1<c-2$ הם שלושה מספרים שונים מתוך $\{1,\dots,8\}$, וההתאמה הפיכה. לכן $\binom83=56$.
תרגיל מ.4 ⭐⭐
בקבוצה של 7 אנשים, כל אחד מקבל באקראי מספר מ-1 עד 10 (חזרות מותרות). מה הסיכוי שכולם שונים? מה הסיכוי שיש חזרה?
כדורים בתאים + משלים. שונים: $\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4}{10^7}=\frac{604800}{10^7}=0.06048$. חזרה: $1-0.06048\approx0.94$.
| הכלי | מתי | הרעיון |
|---|---|---|
| הכלה והפרדה | איחוד של מקרים חופפים | סכום, מינוס זוגות, פלוס שלשות... כך שכל איבר נספר פעם אחת |
| derangements | "אף אחד לא במקום" | $D_n=n!\sum\frac{(-1)^k}{k!}$, וההסתברות $\approx\frac1e$ ללא תלות ב-$n$ |
| שובך יונים | "בהכרח" / "קיים" | הקושי הוא להגדיר שובכים (דוגמה: זוגות סכום 11) |
| מסלולי סריג | רצפים של שני סוגי צעדים | $\binom{a+b}a$ ("בחר מקומות"), ונסיגה שהיא כלל פסקל |
| ספירה לשם הסתברות | $P=|A|/|\Omega|$ | אותו $\Omega$ במונה ובמכנה; בונים אובייקט בשדות; הרצפים (לא הספירות) שוות-סיכוי |
| היפרגאומטרית | בחירה בלי החזרה | $\frac{\binom Kk\binom{N-K}{n-k}}{\binom Nn}$ |
| בינומי מספירה | ניסויים בלתי-תלויים | $\binom nkp^kq^{n-k}$: ספירה משוקללת |
| סטירלינג ואנטרופיה | הערכת גודל | $\ln n!\approx n\ln n-n$; $\binom n{qn}\approx2^{nH(q)}$ |
lgamma), לא ישירות.