Problemi i grumbulluesit të kuponave

Në teorinë e probabilitetit, problemi i grumbulluesit të kuponëve përshkruan konkurset "mblidhni të gjithë kuponët dhe fitoni". Ai shtron pyetjen e mëposhtme: Nëse çdo kuti e një marke drithërash përmban një kupon dhe ka  lloje të ndryshme kuponësh, sa është probabiliteti që duhet të blihen më shumë se  kuti për të mbledhur të gjithë  kuponët? Një deklaratë alternative është: Duke pasur parasysh  kuponët, sa kuponë prisni që ju duhet të tërhiqni (me zëvendësim) përpara se të keni tërhequr çdo kupon të paktën një herë? Analiza matematikore e problemit zbulon se numri i pritshëm i provave të nevojshme rritet si  .  Për shembull, kur  duhen mesatarisht rreth 225 prova E(50) = 50(1 + 1/2 + 1/3 + ... + 1/50) = 224.9603, the expected number of trials to collect all 50 coupons. The approximation  for this expected number gives in this case . për të mbledhur të gjithë 50 kuponët.

 Zgjidhje 

 Llogaritja e pritjes matematike 
Le të jetë koha  numri i tërheqjeve të nevojshme për të mbledhur të gjithë  kuponët dhe le jetë  koha për të mbledhur kuponin i -të pas janë mbledhur  kupona. Pastaj  . Mendoni për  dhe  si ndryshore të rastësishme . Vini re se probabiliteti për të mbledhur një kupon të ri është  . Prandaj,  ka shpërndarje gjeometrike me pritje matematike  . Nga lineariteti i pritjeve kemi:



Këtu  është numri harmonik n -të. Duke përdorur asimptotikën e numrave harmonikë, marrim:



ku  është konstantja Euler-Mascheroni .

Përdorimi i mosbarazimit të Markovit për të kufizuar probabilitetin e dëshiruar:



Sa më sipër mund të modifikohet pak për të trajtuar rastin kur ne kemi mbledhur tashmë disa nga kuponët. Le të jetë k numri i kuponëve të mbledhur tashmë, atëherë:



 Llogaritja e variancës 
Duke përdorur pavarësinë e ndryshoreve të rastit , marrim:



nga relacioni  (shih problemin e Bazelit ).

Kufizoni probabilitetin e dëshiruar duke përdorur mosbarazimin e Çebishevit :



 Vlerësimet e bishtit 
Një vlerësim më i fortë i bishtit për bishtin e sipërm merret si më poshtë. Le të jenë  që tregojnë ngjarjen që kupini -të nuk është zgjedhur në  provat e para. Atëherë



Kështu, për , ne kemi  . Ne marrim