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

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

מאפיינים
פרמטרים	<math>\mathbf{p}\in [0,1]^n</math> – ההסתברות להצלחה לכל ניסוי i, n – מספר ניסויי ברנולי
תומך	k ∈ { 0, …, n }
פונקציית הסתברות (pmf)	<math>\sum\limits_{A\in F_k} \prod\limits_{i\in A} p_i \prod\limits_{j\in A^c} (1-p_j)</math>
פונקציית ההסתברות המצטברת (cdf)	<math>\sum\limits_{l=0}^k \sum\limits_{A\in F_l} \prod\limits_{i\in A} p_i \prod\limits_{j\in A^c} (1-p_j)</math>
תוחלת	<math>\sum\limits_{i=1}^n p_i</math>
שונות	<math> \sigma^2 =\sum\limits_{i=1}^n (1 - p_i)p_i</math>
פונקציה יוצרת מומנטים (mgf)	<math>\prod\limits_{j=1}^n (1-p_j+p_j e^t)</math>
פונקציה אופיינית	<math>\prod\limits_{j=1}^n (1-p_j+p_j e^{it})</math>
צידוד	<math>\frac{1}{\sigma^3}\sum\limits_{i=1}^n ( 1-2p_i ) ( 1-p_i ) p_i</math>
גבנוניות	<math>\frac{1}{\sigma^4}\sum\limits_{i=1}^n ( 1 - 6(1 - p_i)p_i )( 1 - p_i )p_i</math>

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

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

תכונות

פונקציית ההסתברות

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

<math>\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) </math>

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

קובץ:PBD PMF.png	קובץ:PBD CDF.png
פונקציית ההסתברות ופונקציית ההסתברות הצוברת עבור 30 ניסויים. השוואה בין התפלגות בינומית של פואסון כך שההסתברות להצלחה בכל ניסוי מוגרלת בהתפלגות אחידה לבין התפלגות בינומית עם הסתברות הצלחה שהיא ממוצע הסתברויות ההצלחה שהוגרלו לבין התפלגות פואסון עם קבוע <math>\lambda</math> שהוא סכום הסתברויות ההצלחה שהוגרלו.

חישוב באמצעות רקורסיה

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

<math>\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}</math>

כאשר

<math> T(i)=\sum\limits_{j=1}^n \left( \frac{p_j}{1-p_j} \right)^i</math>

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

חישוב באמצעות אלגוריתם הפרד ומשול

שיטת חישוב נוספת היא באמצעות אלגוריתם הפרד ומשול. בהנחה ש-<math>n=2^b</math> עבור <math>b\in \mathbb{N}</math>. בעזרת קונבולוציה נוכל לכתוב

<math>f(p_{1:2^b}) = f(p_{1:2^{b-1}})*f(p_{2^{b-1}+1:2^b})</math>

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

# 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 גדול (עד בערך <math>n=2000</math>) והוא יכול להיות מהיר גם ל-n גדול יותר כתלות ב-<math>p_i </math>.

חישוב באמצעות התמרת פורייה בדידה

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

<math>\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) </math>

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

פונקציית ההסתברות המצטברת

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

<math>\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), </math>

כאשר <math>F_\ell</math> היא קבוצת כל תתי הקבוצות בגודל <math>\ell</math> של ניסויים שניתן לבחור מתוך סך n הניסויים. מכיוון שפונקציית ההסתברות המצטברת ל-k היא סכום ההסתברויות לקבל ערכים שקטנים מ-k, ניתן להיעזר בשיטת החישוב עם אלגוריתם DC ולסכום את כל התוצאות מהאינדקס הראשון 0 ועד ל-k (כולל).

תוחלת ושונות

התוחלת של משתנה בינומי של פואסון הוא סכום התוחלות של כל משתני הברנולי המייצגים את n הניסויים. מכיוון שהניסויים בלתי תלויים והתוחלת ליניארית התוחלת של המשתנה תהיה סכום התוחלות של כל משתנה ברנולי עם הסתברות להצלחה <math>p_i</math>.

<math>\mu = \sum\limits_{i=1}^n p_i</math>

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

<math>\sigma^2 =\sum\limits_{i=1}^n (1-p_i) p_i</math>

אנטרופיה

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

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

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

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

דוגמה

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

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

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

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

התפלגויות קשורות

הקשר להתפלגות בינומית

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

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

<math> \operatorname{Var}(PB)=\operatorname{Var}(B)- \sum_{i=1}^n (p_i-\mu)^2</math>

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

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

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

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

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

הקשר להתפלגות פואסון

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

<math>\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</math>

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

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

<math> \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 </math>

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

ראו גם

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

לקריאה נוספת

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