اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNew results for the Coupon Collectors problem with swapping and replacement
166
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.
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.
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 boxe
s 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.
Pole-swapping algorithms, which are generalizations of the QZ algorithm for the generalized eigenvalue problem, are studied. A new modular (and therefore more flexible) convergence theory that applies to all pole-swapping algorithms is developed. A k
ey component of all such algorithms is a procedure that swaps two adjacent eigenvalues in a triangular pencil. An improved swapping routine is developed, and its superiority over existing methods is demonstrated by a backward error analysis and numerical tests. The modularity of the new convergence theory and the generality of the pole-swapping approach shed new light on bi-directional chasing algorithms, optimally packed shifts, and bulge pencils, and allow the design of novel algorithms.
Consider an online facility assignment problem where a set of facilities $F = { f_1, f_2, f_3, cdots, f_{|F|} }$ of equal capacity $l$ is situated on a metric space and customers arrive one by one in an online manner on that space. We assign a custom
er $c_i$ to a facility $f_j$ before a new customer $c_{i+1}$ arrives. The cost of this assignment is the distance between $c_i$ and $f_j$. The objective of this problem is to minimize the sum of all assignment costs. Recently Ahmed et al. (TCS, 806, pp. 455-467, 2020) studied the problem where the facilities are situated on a line and computed competitive ratio of Algorithm Greedy which assigns the customer to the nearest available facility. They computed competitive ratio of algorithm named Algorithm Optimal-Fill which assigns the new customer considering optimal assignment of all previous customers. They also studied the problem where the facilities are situated on a connected unweighted graph. In this paper we first consider that $F$ is situated on the vertices of a connected unweighted grid graph $G$ of size $r times c$ and customers arrive one by one having positions on the vertices of $G$. We show that Algorithm Greedy has competitive ratio $r times c + r + c$ and Algorithm Optimal-Fill has competitive ratio $O(r times c)$. We later show that the competitive ratio of Algorithm Optimal-Fill is $2|F|$ for any arbitrary graph. Our bound is tight and better than the previous result. We also consider the facilities are distributed arbitrarily on a plane and provide an algorithm for the scenario. We also provide an algorithm that has competitive ratio $(2n-1)$. Finally, we consider a straight line metric space and show that no algorithm for the online facility assignment problem has competitive ratio less than $9.001$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
