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