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

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

בתורת ההסתברות, בעיית אוסף הקופונים היא בעיה קלאסית הדנה במשחק שבו נאספים קופונים מתוך תיבה עם n קופונים שונים, בהסתברות שווה עם החזרה, והמטרה היא לאסוף את כל הקופונים. מהי ההסתברות שנדרשים לפחות t דגימות כדי לצפות בכל n הקופונים לפחות פעם אחת? ניתוח מתמטי מראה שתוחלת מספר הדגימות הנדרש כדי לצפות בכל קופון לפחות פעם אחת גדלה כתלות ב-n לפי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(n\log(n))} (לדוגמה כאשר מספר הקופונים הוא n = 50, נדרשות כ-225 דגימות).

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

פתרון הבעיה

נסמן T כזמן הנדרש (או מספר הדגימות) לאיסוף n קופונים, נסמן בהפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_i} את הזמן הנדרש לאיסוף הקופון ה-i לאחר שנאספו i-1 קופונים. נתייחס אל T ו-$t_{i}$ כאל משתנים מקריים. נשים לב שההסתברות לאיסוף קופון חדש (לא אחד מתוך ה-i-1 שכבר נצפו) היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i = \frac{n-(i-1)}{n}} . הזמן הנדרש לאיסוף הקופון ה-i (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_i} ) מתפלג לפי התפלגות גאומטרית עם תוחלת של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{p_i}} . באמצעות לינאריות התוחלת ניתן לשערך את התוחלת לאיסוף כל הקופונים:

$${\begin{aligned}\operatorname {E} (T)&=\operatorname {E} (\sum _{i=1}^{n}t_{i})=\operatorname {E} (t_{1})+\operatorname {E} (t_{2})+\cdots +\operatorname {E} (t_{n})={\frac {1}{p_{1}}}+{\frac {1}{p_{2}}}+\cdots +{\frac {1}{p_{n}}}\\&={\frac {n}{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{1}}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\,=\,n\cdot H_{n}.\end{aligned}}$$

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_n} הוא המספר ההרמוני ה-n. בניתוח אסימפטוטי מקבלים שכאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \to \infty} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{E}(T) = n \cdot H_n = n \log n + \gamma n + \frac1{2} + o(1) }

כאשר הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \gamma \approx 0.5772156649} הוא קבוע אוילר-מסקרוני. באמצעות אי-שוויון מרקוב ניתן לחסום את ההסתברות שהזמן הנדרש לאיסוף כל הקלפים יעלה על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c \, n H_n} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{P}(T \geq c \, n H_n) \le \frac1c.}

חישוב השונות

ניתן לקבל חסם למספר התצפיות הנדרש לפי השונות. תוך שימוש בכך שהמשתנים המקרים $t_{i}$ בלתי תלויים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \operatorname{Var}(T)& = \operatorname{Var}(t_1) + \operatorname{Var}(t_2) + \cdots + \operatorname{Var}(t_n) \\ & = \frac{1-p_1}{p_1^2} + \frac{1-p_2}{p_2^2} + \cdots + \frac{1-p_n}{p_n^2} \\ & = \left(\frac{n^2}{n^2} + \frac{n^2}{(n-1)^2} + \cdots + \frac{n^2}{1^2}\right) - \left(\frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1}\right)\\ & = n^2 \cdot \left(\frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} \right) - n \cdot H_n\\ & = n^2 \cdot \left(\frac{\pi^2}{6} - \frac{1}{n} + \frac{1}{2n^2}\right) - \left(n \log n + \gamma n + \frac{1}{2}\right) + o(1)\\ & < \frac{\pi^2}{6} n^2. \end{align} }

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi^2/6} הוא ערך של פונקציית זטא של רימן. (ראו בעיית בזל). באמצעות אי-שוויון צ'בישב מתקבל החסם:

הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \operatorname {P} \left(|T-nH_{n}|\geq c\,n\right)\leq {\frac {\pi ^{2}}{6c^{2}}}.}