اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe number of k-tons in the coupon collector problem
101
0
0.0
(
0
)
تأليف
J.C. Saunders
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle$ of its elements. One can think of $|Srangle=sum_{iin S}|irangle/sqrt{|S|}$ as the quantum version of a uniformly random sample over $S$,
as in the classical analysis of the ``coupon collector problem. We show that if $k$ is close to $n$, then we can learn $S$ using asymptotically fewer quantum samples than random samples. In particular, if there are $n-k=O(1)$ missing elements then $O(k)$ copies of $|Srangle$ suffice, in contrast to the $Theta(klog k)$ random samples needed by a classical coupon collector. On the other hand, if $n-k=Omega(k)$, then $Omega(klog k)$ quantum samples are~necessary. More generally, we give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through $|Srangle$. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.
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 t
he 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.
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 know
n 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.
This paper investigates sufficient conditions for a Feynman-Kac functional up to an exit time to be the generalized viscosity solution of a Dirichlet problem. The key ingredient is to find out the continuity of exit operator under Skorokhod topology,
which reveals the intrinsic connection between overfitting Dirichlet boundary and fine topology. As an application, we establish the sub and supersolutions for a class of non-stationary HJB (Hamilton-Jacobi-Bellman) equations with fractional Laplacian operator via Feynman-Kac functionals associated to $alpha$-stable processes, which help verify the solvability of the original HJB equation.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
