Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Useful Solution of the Coupon Collectors Problem
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The Coupon Collectors Problem is one of the few mathematical problems that make news headlines regularly. The reasons for this are on one hand the immense popularity of soccer albums (called Paninimania) and on the other hand that no solution is known that is able to take into account all effects such as replacement (limited purchasing of missing stickers) or swapping. In previous papers we have proven that the classical assumptions are not fulfilled in practice. Therefore we define new assumptions that match reality. Based on these assumptions we are able to derive formulae for the mean number of stickers needed (and the associated standard deviation) that are able to take into account all effects that occur in practical collecting. Thus collectors can estimate the average cost of completion of an album and its standard deviation just based on elementary calculations. From a practical point of view we consider the Coupon Collectors problem as solved. ----- Das Sammelbilderproblem ist eines der wenigen mathematischen Probleme, die regelma{ss}ig in den Schlagzeilen der Nachrichten vorkommen. Dies liegt einerseits an der gro{ss}en Popularitat von Fu{ss}ball-Sammelbildern (Paninimania genannt) und andererseits daran, dass es bisher keine Losung gibt, die alle relevanten Effekte wie Nachkaufen oder Tauschen berucksichtigt. Wir haben bereits nachgewiesen, dass die klassischen Annahmen nicht der Realitat entsprechen. Deshalb stellen wir neue Annahmen auf, die die Praxis besser abbilden. Darauf aufbauend konnen wir Formeln fur die mittlere Anzahl benotigter Bilder (sowie deren Standardabweichung) ableiten, die alle in der Praxis relevanten Effekte berucksichtigen. Damit konnen Sammler die mittleren Kosten eines Albums sowie deren Standardabweichung nur mit Hilfe von elementaren Rechnungen bestimmen. Fur praktische Zwecke ist das Sammelbilderproblem damit gelost.
rate research
Read More
The solution of the classical Coupon Collectors Problem is based on the assumptions that all stickers are independently and uniformly distributed. We can prove statistically as well as analytically that in particular the assumption of independence is not fulfilled in the field. To achieve this result we have systematically modeled and analyzed the production process of the stickers by combinatorial methods. We have also derived measures for the deviation from independence. Thus the results for the classical Coupon Collectors Problem are not valid for practical applications anymore, but we can show that they constitute an a upper bound. This means in particular that in practice the deviation is advantageous for the collectors, not a fraud of the vendors. ------ Im klassischen Sammelbilderproblem wird angenommen, dass die Sammelbilder gleichverteilt und unabhangig sind, d. h. alle Bilder kommen gleich haufig vor und werden zufallig auf die Packchen verteilt. Wir konnen sowohl statistisch als auch analytisch nachweisen, dass insbesondere die Annahme der Zufalligkeit bzw. Unabhangigkeit in der Praxis nicht erfullt ist. Dazu haben wir den Herstellungsprozess der Sammelbilder systematisch mit kombinatorischen Methoden untersucht. Wir konnen auch Ma{ss}e dafur angeben, wie gro{ss} die Abweichung vom Zufall ist. Damit sind die Ergebnisse des klassischen Sammelbildermodells in der Praxis nicht mehr gultig, aber wir konnen zeigen, dass sie eine Abschatzung nach oben darstellen. Dies bedeutet insbesondere, dass kein Betrug durch den Hersteller vorliegt, sondern vielmehr eine Bevorteilung der Sammler.
This paper focuses on the Coupon Collectors Problem with replacement (limited purchasing of missing stickers) and swapping. We have simulated combined strategies and found new results, which we were able to prove for a particular case. The ratio of the average number of stickers needed to fill the album by the album size (number of different stickers needed) and the number of collectors as well as the ratio of the variance and the album size depend approximately only on the percentage of replacement stickers (the limited number of stickers that can be bought directly from the vendor) and the number of collectors, but not on the total album size. Thus collectors can estimate the average cost of completion of an album and its standard deviation just based on basic calculations and a table lookup. Additionally we could show that asymptotocally the effect of replacement is stronger than swapping. ----- In diesem Artikel wird das Sammelbilderproblem mit Nachkaufen und Tauschen untersucht. Wir haben mit Hilfe von Simulationen neue Ergebnisse gefunden und sie auch in einem Spezialfall bewiesen. Das Verhaltnis der mittleren Anzahl zu kaufender Karten pro Sammler als auch das Verhaltnis der Varianz zur Albumgro{ss}e hangt in sehr guter Naherung nur vom Anteil der nachkaufbaren Karten ab, aber nicht von der Albumgro{ss}e. Damit konnen Sammler anhand des Prozentsatzes der Nachkaufkarten die mittleren Kosten eines Albums sowie deren Standardabweichung nur mit einer Tabelle und Grundrechenarten bestimmen. Ausserdem konnten wir belegen, dass asymptotisch der Effekt des Nachkaufens starker ist als der des Tauschens.
Consider the coupon collector problem where each box of a brand of cereal contains a coupon and there are n different types of coupons. Suppose that the probability of a box containing a coupon of a specific type is $1/n$ and that we keep buying boxes until we collect at least $m$ coupons of each type. For $kgeq m$ call a certain coupon a $k$-ton if we see it $k$ times by the time we have seen $m$ copies of all of the coupons. Here we determine the asymptotic distribution of the number of $k$-tons after we have collected $m$ copies of each coupon for any $k$ in a restricted range, given any fixed $m$. We also determine the asymptotic joint probability distribution over such values of $k$ and the total number of coupons collected.
The Secret Santa ritual, where in a group of people every member presents a gift to a randomly assigned partner, poses a combinatorial problem when considering the probabilities involved in the formation of pairs, where two persons exchange gifts mutually. We give different possible derivations for such probabilities by counting fixed-point-free permutations with certain numbers of 2-cycles.
The mathematical achievements of Harry Kesten since the mid-1950s have revolutionized probability theory as a subject in its own right and in its associations with aspects of algebra, analysis, geometry, and statistical physics. Through his personality and scientific ability, he has framed the modern subject to a degree exceeded by no other. The impact of his work and personality is summarised in this memoir.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
