התפלגות בינומית של פואסון

בתורת ההסתברות, **התפלגות בינומית של פואסון** היא התפלגות בדידה של סכום משתנים מקריים בעלי התפלגות ברנולי, כאשר המשתנים המקריים לא בהכרח מתפלגים בהתפלגות זהה. ההתפלגות נקראת על שמו של סימאון דני פואסון שהציג אותה לראשונה במאמר בשנת 1837.

ההתפלגות מתארת את מספר ההצלחות ב-n ניסויי ברנולי בלתי תלויים, עם תוצאה הצלחה או כישלון כאשר ההסתברות להצליח בניסוי ה-i היא p_i, ואינו תלוי בניסויים אחרים. ההתפלגות הבינומית היא מקרה פרטי של התפלגות בינומית של פואסון, בו כל הסתברויות ההצלחה זהות בין הניסויים, כלומר p_1 = p_2 = \cdots = p_n.

## תכונות
### פונקציית ההסתברות
ההסתברות לקבל מספר הצלחות k מתוך n ניסוי ברנולי מתוארת על ידי הסכום

:\Pr(K=k) = \sum\limits_{A\in F_k} \prod\limits_{i\in A} p_i \prod\limits_{j\in A^c} (1-p_j) 

כאשר F_k היא קבוצת כל תתי הקבוצות בגודל k שניתן לבחור מתוך \{1,2,3,...,n\}. כל קבוצה A כוללת בחירה של k ניסויים מתוך ה-n האפשריים. A^c היא הקבוצה המשלימה ל-A וכוללת את כל הניסויים מתוך ה-n האפשריים שלא נבחרו לקבוצה A. הגודל של קבוצה זו הוא בהתאמה n-k. p_i הוא ההסתברות להצלחה בניסוי ה-i.

#### חישוב באמצעות רקורסיה
במקרים בהם מספר הניסויים גדול, F_k היא קבוצה גדולה לחישוב ישיר של ההסתברות. דרך נוספת לחישובה, במקרה שאף אחת מההסתברויות להצלחה p_i לא שווה ל-1 היא באמצעות נוסחת רקורסיה

:\Pr (K=k)= \begin{cases}
\prod\limits_{i=1}^n (1-p_i) & k=0 \\ 
\frac{1}{k} \sum\limits_{i=1}^k (-1)^{i-1}\Pr (K=k-i)T(i) & k>0 \\ 
\end{cases}

כאשר 
:  T(i)=\sum\limits_{j=1}^n \left( \frac{p_j}{1-p_j} \right)^i

נוסחה זו אינה יציבה נומרית, ולא כדאי להשתמש בה עבור ערכי n גדולים (ככלל אצבע אפשר להשתמש עד n).

#### חישוב באמצעות אלגוריתם הפרד ומשול
שיטת חישוב נוספת היא באמצעות אלגוריתם הפרד ומשול. בהנחה ש-n=2^b עבור b\in \mathbb{N}. בעזרת קונבולוציה נוכל לכתוב 
: f(p_{1:2^b}) = f(p_{1:2^{b-1}})*f(p_{2^{b-1}+1:2^b})

כאשר f(p_{i:j})  היא ההתפלגות הבינומית של פואסון לניסויים i עד j עם הסתברויות להצלחה, p_i, \dots, p_j. השיטה כוללת חישוב קונבולוציה של וקטורים P_i,...,P_n עם הסתברות הצלחה וכישלון [p_i,1-p_i]. שיטה זאת ניתנת ליישום באלגוריתם הקונבולוציה הישירה (direct convolution (DC) algorithm). האלגוריתם מחזיר את ההסתברות לכל k\in {1,...,n} ובהתאמה עבור k ספציפי ההסתברות מתקבלת ב-PMF[k].


```python
# PMF and nextPMF begin at index 0
function DC(p₁, ..., pₙ) is
    declare new PMF array of size 1
    PMF[0] = [1]
    for i = 1 to n do
        declare new nextPMF array of size i + 1
        nextPMF[0] = (1 - pᵢ) * PMF[0]
        nextPMF[i] = pᵢ * PMF[i - 1]
        for k = 1 to i - 1 do
            nextPMF[k] = pᵢ * PMF[k - 1] + (1 - pᵢ) * PMF[k]
        repeat
        PMF = nextPMF
    repeat
    return PMF
end function
```


אלגוריתם זה הוא יעיל ומהיר גם ל-n גדול (עד בערך n=2000) והוא יכול להיות מהיר גם ל-n גדול יותר כתלות ב-p_i .

#### חישוב באמצעות התמרת פורייה בדידה
דרך נוספת לחישוב ההסתברות היא באמצעות התמרת פורייה בדידה
:\Pr (K=k)=\frac{1}{n+1} \sum_{\ell=0}^n C^{-lk} \prod_{m=1}^n \left( 1+(C^\ell-1) p_m \right) 

כאשר C=\exp \left( \frac{2i\pi }{n+1} \right) ו- i=\sqrt{-1}.

### פונקציית ההסתברות המצטברת
פונקציית ההסתברות המצטברת מחושבת על ידי
: \Pr(K \leq k) = \sum^{k}_{\ell=0} \sum_{A\in F_\ell} \prod_{i\in A} p_i \prod_{j\in A^c} (1-p_j), 
כאשר F_\ell היא קבוצת כל תתי הקבוצות בגודל \ell של ניסויים שניתן לבחור מתוך סך n הניסויים. מכיוון שפונקציית ההסתברות המצטברת ל-k היא סכום ההסתברויות לקבל ערכים שקטנים מ-k, ניתן להיעזר בשיטת החישוב עם אלגוריתם DC ולסכום את כל התוצאות מהאינדקס הראשון 0 ועד ל-k (כולל).

### תוחלת ושונות
התוחלת של משתנה בינומי של פואסון הוא סכום התוחלות של כל משתני הברנולי המייצגים את n הניסויים. מכיוון שהניסויים בלתי תלויים והתוחלת ליניארית התוחלת של המשתנה תהיה סכום התוחלות של כל משתנה ברנולי עם הסתברות להצלחה p_i.
: \mu = \sum\limits_{i=1}^n p_i

באותו אופן גם השונות תהיה סכום השונויות של כל משתני הברנולי
: \sigma^2 =\sum\limits_{i=1}^n (1-p_i) p_i

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

האנטרופיה של התפלגות בינומית של פואסון חסומה התפלגות בינומית עם אותו מספר הפרמטרים (אותו מספר הניסויים) עם אותה התוחלת.

השערת הקעירות של שפ-אולקין (Shepp–Olkin concavity conjecture), שהוצגה על ידי לורנס שפ ואינגרם אולקין בשנת 1981, והוכחה על ידי ארוואן היליון ואוליבר ג'ונסון בשנת 2015, מראה כי האנטרופיה היא פונקציה קעורה של הסתברויות ההצלחה של כל אחד מהניסויים p_1,...,p_n.

השערה נוספת מאותו המאמר המכונה השערת המונוטוניות של שפ–אולקין (Shepp–Olkin monotonicity conjecture) מראה כי כאשר כל p_i\geq\frac{1}{2} האנטרופיה היא פונקציה מונוטונית עולה ב-p_i, גם השערה זאת הוכחה על ידי היליון וג׳ונסון בשנת 2019.

## דוגמה
נניח ניסוי שבו נערך מבחן בכיתה בה 30 תלמידים, כל תלמיד יכול לעבור את המבחן או להיכשל בו. במקרה שבו הכיתה זהה לגמרי כך שההסתברות להצלחה של כל תלמיד להצליח זהה ובלתי תלויה באחרים, נוכל לתאר את הניסוי על ידי התפלגות בינומית. במקרה בו ההסתברות של כל תלמיד להצליח במבחן שונה וגם אינה תלויה בתלמיד אחר, כלומר לכל תלמיד הסתברות הצלחה שונה, נתאר את הניסוי בעזרת התפלגות בינומית של פואסון. 
נניח שלתלמיד ה-i יש הסתברות הצלחה של p_i = \frac{i}{i+1}.

נחשב את התוחלת של ההתפלגות: 
 \mu = \sum\limits_{i=1}^{30} \frac{i}{i+1}\approx 26.97.
כלומר מספר התלמידים הצפוי לעבור את המבחן במקרה שנבצע את הניסוי מספר רב של פעמים הוא 27. 

נשווה למקרה בו הכיתה הייתה מתפלגת בינומית, וההסתברות של כל תלמיד להצליח הוא ממוצע ההסתברויות מההתפלגות המקורית, כלומר 
p = \frac{1}{30}\sum\limits_{i=1}^{30} \frac{i}{i+1}\approx \frac{26.97}{30}\approx0.89. במקרה זה התוחלת של הניסוי הייתה \mu=n\cdot p = 30 \cdot 0.89 \approx 26.97. נשים לב כי קיבלנו תוחלת זהה להתפלגות הבינומית של פואסון, כלומר מספר העוברים (במקרה של ביצוע הניסוי מספר רב של פעמים) זהה בין ההתפלגויות ושווה לבערך 27. זה לא מקרי שכן אופן החישוב של תוחלת ההתפלגות הבינומית הוא מכפלת כמות התלמידים בהסתברות להצלחה. אך הסתברות זאת היא בדיוק סכום הסתברויות ההצלחה של ההתפלגות הבינומית של פואסון (שהוא התוחלת של התפלגות זאת) לחלק למספר הניסויים.

נחשב את השונות של ההתפלגות:
\sigma^2 =\sum\limits_{i=1}^{30} (1-\frac{i}{i+1}) \frac{i}{i+1} \approx 2.41.
בנוסף נחשב במקרה של ההתפלגות הבינומית המתאימה 
\sigma^2 = n \cdot (1-p) p \approx 2.72. נשים לב כי השונות גבוהה יותר במקרה של ההתפלגות הבינומית הסטנדרטית. במקרה שתיארנו ככל שנבצע יותר ניסויים נתקרב למספר תלמידים שהצליחו כמו התוחלת שיצאה זהה בשני המקרים. אך בהתפלגות הבינומית של פואסון, שבמקרה זה נותנת להרבה תלמידים הסתברות גבוהה יותר להצליח לעומת ההסתברות להצליח במקרה הבינומי, נקבל שונות נמוכה יותר שמצביעה על פיזור נמוך יותר ביחס לתוחלת.

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

כמו כן, השונות של ההתפלגות הבינומית של פואסון ניתנת לחישוב על ידי השונות של ההתפלגות הבינומית הרגילה על ידי המרחק של כל הסתברות להצלחה p_i מהתוחלת ובפרט

:  \operatorname{Var}(PB)=\operatorname{Var}(B)- \sum_{i=1}^n (p_i-\mu)^2

המקסימום של השונות מתקבל כאשר p_i = \mu לכל i, ובפרט כאשר ההתפלגות זהה להתפלגות הבינומית. 

הקשר בין השונויות מאפשר לשים חסם על מרחק השונות הכוללת של ההתפלגות הבינומית וההתפלגות הבינומית של פואסון מה שבעצם מאפשר לחסום את השגיאה בהערכת ההתפלגות הבינומית של פואסון בעזרת ההתפלגות הבינומית הסטנדרטית. נגדיר את \nu = 1 - \mu כאשר \mu היא התוחלת של כל ה-p_i ואת d(PB,B) להיות המרחק השונות הכוללת בין ההתפלגויות ואז 

: d(PB,B)\le(1-\mu^{n+1}-\nu^{n+1}) \frac{\sum_{i=1}^n (p_i-\mu)^2}{((n+1)\mu\nu)}

: d(PB,B)\ge C\min\left\{\,1,\frac{1}{n\mu\nu}\,\right\} \sum_{i=1}^n (p_i-\mu)^2

כאשר C\ge\frac{1}{124}. 
מכאן שהמרחק שואף ל-0 אם ורק אם \operatorname{Var}(PB)/\operatorname{Var}(B) שואף ל-1.

### הקשר להתפלגות פואסון
ההתפלגות הבינומית של פואסון (נסמן ב-P_o) ניתנת לשערוך באמצעות התפלגות פואסון עם תוחלת \lambda=\sum_{i=1}^n p_i
. ברבור והול הראו שניתן לחסום את המרחק שונות הכוללת d(PB,Po) בין התפלגויות אלו על ידי

: \frac{1}{32}\min\left\{\,\frac{1}{\lambda},1\,\right\} \sum_{i=1}^n p_i^2\le d(PB, Po)\le\frac{1-\varepsilon^{-\lambda}} \lambda \sum_{i=1}^n p_i^2

במקרה זה ניתן לראות שככל ש-P_i קטנים יותר כך גם מרחק השונות הכוללת בין ההתפלגויות ובפרט השערוך של התפלגות פואוסן את ההתפלגות הבינומית של פואסון. 

בנוסף, ניתן לחסום את השונות של ההתפלגות הבינומית של פואסון על ידי השונות של התפלגות פואסון. השונות של התפלגות פואסון היא \operatorname{Var}(Po)=\lambda=\sum_{i=1}^n p_i והשונות של התפלגות בינומית של פואסון היא

:  \sigma^2 =\sum\limits_{i=1}^n (1 - p_i)p_i =\sum\limits_{i=1}^n p_i-\sum\limits_{i=1}^n p_i^2 

ונשים לב כי אכן מתקיים \operatorname{Var}(\mathrm{Po})>\operatorname{Var}(PB).

## ראו גם
* התפלגות בינומית
* התפלגות פואסון

## לקריאה נוספת

* Wang, Y. William (2020). A Survey of Poisson Binomial Distribution. Columbia University — מאמר סקירה עדכני על התפלגות פואסון בינומית, כולל תכונות, אלגוריתמים ושימושים


## הערות שוליים

בינומית של פואסון