בעיית אוסף הקופונים

מתוך ויקיפדיה, האנציקלופדיה החופשית
מספר הקופונים (בציר האנכי) כנגד מספר הדגימות הנדרש בתוחלת (בציר האופקי)

בתורת ההסתברות, בעיית אוסף הקופונים היא בעיה קלאסית הדנה במשחק שבו נאספים קופונים מתוך תיבה עם קופונים שונים, בהסתברות שווה עם החזרה, והמטרה היא לאסוף את כל הקופונים. מהי ההסתברות שנדרשות לפחות דגימות כדי לצפות בכל הקופונים לפחות פעם אחת? ניתוח מתמטי מראה שתוחלת מספר הדגימות הנדרש כדי לצפות בכל קופון לפחות פעם אחת גדלה כתלות ב- לפי (לדוגמה כאשר מספר הקופונים הוא n = 50, נדרשות בממוצע כ-225[1] דגימות).

עיקרון חשוב להבנת הבעיה הוא שנדרש מספר דגימות מועט מאוד כדי לאסוף את הקופונים הראשונים, ואילו כדי לצפות בקופונים האחרונים (אלו שלא נצפו קודם לאחר שכמעט כל הקופונים נצפו) נדרש מספר גדול של דגימות. למשל כאשר יש 50 קופונים ו-49 מהם כבר נצפו, ידרשו בממוצע כ-50 דגימות כדי לצפות בקופון האחרון.

פתרון הבעיה[עריכת קוד מקור | עריכה]

נסמן כזמן הנדרש (או מספר הדגימות) לאיסוף קופונים, נסמן ב את הזמן הנדרש לאיסוף הקופון ה- לאחר שנאספו קופונים. נתייחס אל ו- כאל משתנים מקריים. נשים לב שההסתברות לאיסוף קופון חדש (לא אחד מתוך ה- שכבר נצפו) היא . הזמן הנדרש לאיסוף הקופון ה- () מתפלג לפי התפלגות גאומטרית עם תוחלת של . באמצעות ליניאריות התוחלת ניתן למצוא את תוחלת הזמן הנדרש לאיסוף כל הקופונים, :

כאשר הוא המספר ההרמוני ה-. בניתוח אסימפטוטי מקבלים שכאשר :

כאשר הוא קבוע אוילר-מסקרוני. באמצעות אי-שוויון מרקוב ניתן לחסום את ההסתברות שהזמן הנדרש לאיסוף כל הקלפים יעלה על :

חישוב השונות[עריכת קוד מקור | עריכה]

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

כאשר הוא ערך של פונקציית זטא של רימן. (ראו בעיית בזל). באמצעות אי-שוויון צ'בישב מתקבל החסם:

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ E(50)=50(1 + 1/2 + 1/3 + ... + 1/50) = 224.9603, מספר הניסויים הצפוי לאיסוף כל 50 הקופונים. בקירוב: כאשר במקרה זה מתקבלת התוצאה המקורבת: .