בעיית אוסף הקופונים - יישומים וסימולציות

נקודת המוצא שלנו היא בעיית אוסף הקופונים (THE COUPON COLLECTOR‘S PROBLEM, CCP). הבעיה הוזכרה כבר לפני למעלה מ-300 שנה ע״י DE MOIVRE. ניסוח הבעיה הוא כדלקמן: כמה שליפות של קופונים נדרשות בממוצע על מנת להשלים אוסף של $n$ סוגי קופונים, אם בכל שלב נשלף קופון בודד באופן אקראי ובהתפלגות אחידה, כאשר כל השליפות בלתי תלויות.

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

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

• טבעי להריץ כמה סימולציות של תהליך ה-CCP כדי לנחש ו/או לאמת את ההתנהגות של משתנים מסויימים. לדוגמה: נסמן ב-$T_{n,m}$ את הזמן עד שהאספן יצליח לאסוף $m$ עותקים מכל אחד מ-$n$ הקופונים ונתבונן בהתפלגות והתוחלת האסימפטוטית שלו כאשר $n$ שואף לאינסוף, ו-$m$ שואף לאינסוף כפונקציה מסויימת של $n$. (בעיה זו נפתרה על ידי ארדש ורניי (1961) עבור $m$ קבוע ונשארה פתוחה עבור $m$ שואף לאינסוף.)

  במהלך המחקר, נתקלנו בקשיים בביצוע סימולציות עבור $T_{n,m}$ ככל ש־n גדל. הבעיה בסימולציה המבוצעת על ידי האלגוריתם הנאיבי והפשוט: כיוון שבכל שלב אנו שולפים קופון בודד, כל ריצה לוקחת זמן של $\Omega(n \log n)$ בהסתברות גבוהה. יתרה מכך, כדי לשמור את הנתונים לגבי מספר הפעמים שראינו כל קופון, אנו זקוקים לשמור $\Theta(n)$ מקום בזיכרון. נוסף על כך, כיוון שידוע כי התכנסות המשתנים ב-CCP היא איטית מאוד, נדרש מספר רב של איטרציות כדי לקבל אומדנים אמינים. לפיכך, עבור $n$-ים גדולים, האלגוריתם הנאיבי הופך לבלתי ישים.

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

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