Kupon yig'uvchilar muammosi - Coupon collectors problem - Wikipedia

Kuponlar sonining grafigi, n va barchasini to'plash uchun kutilgan sinovlar soni (ya'ni vaqt), E (T )

Yilda ehtimollik nazariyasi, kupon yig'uvchisi muammosi "barcha kuponlarni to'plang va yutib oling" tanlovlarini tasvirlaydi. U quyidagi savolni beradi: Agar donli donlarning har bir qutisida kupon bo'lsa va u erda bo'lsa n kuponlarning har xil turlari, ehtimolligi qancha t barchasini yig'ish uchun qutilarni sotib olish kerak n kuponlar? Muqobil bayonot quyidagicha: berilgan n kuponlar, har bir kuponni kamida bir marta olishdan oldin almashtirish bilan qancha kupon tortishingiz kerak deb o'ylaysiz? Muammoning matematik tahlili shuni ko'rsatadiki kutilgan raqam zarur bo'lgan sinovlar o'sib boradi .[a] Masalan, qachon n = 50 uchun taxminan 225 kerak bo'ladi[b] barcha 50 kuponlarni yig'ish uchun o'rtacha sinovlar.

Qaror

Kutishni hisoblash

Ruxsat bering T barchasini yig'ish vaqti bo'lsin n kuponlar va ruxsat bering tmen yig'ish vaqti bo'lsin men- keyin kupon men - 1 ta kupon to'plandi. Keyin . Haqida o'ylash T va tmen kabi tasodifiy o'zgaruvchilar. Yig'ish ehtimoliga e'tibor bering a yangi kupon . Shuning uchun, bor geometrik taqsimot kutish bilan . Tomonidan kutishlarning lineerligi bizda ... bor:

Bu yerda Hn bo'ladi n-chi harmonik raqam. Dan foydalanish asimptotiklar harmonik raqamlardan quyidagilarni olamiz:

qayerda bo'ladi Eyler-Maskeroni doimiysi.

Endi birini ishlatishi mumkin Markov tengsizligi kerakli ehtimollikni cheklash uchun:

Dispersiyani hisoblash

Tasodifiy o'zgaruvchilar mustaqilligidan foydalanish tmen, biz quyidagilarni olamiz:

beri (qarang Bazel muammosi ).

Endi birini ishlatishi mumkin Chebyshev tengsizligi kerakli ehtimollikni cheklash uchun:

Quyruq taxminlari

Quyidagi kuzatuvdan boshqacha yuqori chegara olinishi mumkin. Ruxsat bering hodisani belgilaydi - birinchi kupon birinchisida olinmagan sinovlar. Keyin:

Shunday qilib, uchun , bizda ... bor .

Kengaytmalar va umumlashmalar

  • Per-Simon Laplas, Biroq shu bilan birga Pol Erdos va Alfred Reniy, ning taqsimlanishining chegara teoremasini isbotladi T. Bu natija oldingi chegaralarni yanada kengayishiga olib keladi.
  • Donald J. Nyuman va Lourens Shepp qachon kupon yig'uvchisi muammosini umumlashtirdi m har bir kuponning nusxalarini to'plash kerak. Ruxsat bering Tm birinchi marta bo'ling m har bir kuponning nusxalari to'planadi. Ular bu holatda kutish quyidagilarni qondirishini ko'rsatdi.
Bu yerda m belgilangan. Qachon m = 1 kutishning oldingi formulasini olamiz.
  • Umumiy umumlashma, shuningdek Erdos va Renii tufayli:

Shuningdek qarang

Izohlar

  1. ^ Bu erda va ushbu maqola davomida "log" ga tegishli tabiiy logaritma boshqa bazaga logaritma o'rniga. Bu erdan foydalanishni talab qiladi katta O yozuvlari.
  2. ^ E (50) = 50 (1 + 1/2 + 1/3 + ... + 1/50) = 224.9603, barcha 50 kuponlarni yig'ish uchun kutilayotgan sinovlar soni. Yaqinlashish chunki bu kutilgan raqam bu holda beradi .

Adabiyotlar

  1. ^ Flajolet, Filipp; Gardi, Daniele; Thimonier, Loÿs (1992), "Tug'ilgan kungi paradoks, kupon kollektorlari, keshlash algoritmlari va o'z-o'zini qidirish", Diskret amaliy matematika, 39 (3): 207–229, CiteSeerX  10.1.1.217.5965, doi:10.1016 / 0166-218x (92) 90177-v

Tashqi havolalar