[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Coupon Subset Collection Problem with Quotas

  • Published:
Methodology and Computing in Applied Probability Aims and scope Submit manuscript

Abstract

This paper studies the coupon subset collection problem with quotas, which is a variant of the classical coupon-collection problem. Specifically, the set of coupons is divided into distinct subsets, each of which is referred to as a class and each element of a class is referred to as a type. Coupons can be collected one by one by purchasing a coupon package. A coupon class is said to be acquired if the number of acquired types belonging to the class reaches a given threshold. This paper derives an explicit representation of the survival function of the number of purchases required to acquire a given number of different coupon classes. Several upper and lower bounds of the survival function that can be calculated with less computation time are also derived. Finally, this paper shows that coupon subset collection problems are closely related to some practical problems and the results derived in this paper are useful for solving these problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adler I, Ross S (2001) The coupon subset collection problem. J. Appl. Prob. 38:737–746

    Article  MathSciNet  Google Scholar 

  • Adler M (2005) Trade-offs in probabilistic packet marking. J ACM 52(2):217–244

    Article  MathSciNet  Google Scholar 

  • Anderson K, Sobel M, Uppuluri VRR (1982) Quota fulfillment times. Canadian Journal of Statistics 10(2):73–88

    Article  MathSciNet  Google Scholar 

  • Arcuri A, Iqbal MZ, Briand L (2010) Formal analysis of the effectiveness and predictability of random testing. In: Proceedings of the 19th international symposium on Software testing and analysis, pp 219–230. ACM

  • Arcuri A, Iqbal MZ, Briand L (2012) Random testing: Theoretical results and practical implications. IEEE Trans Softw Eng 38(2):258–277

    Article  Google Scholar 

  • Boneh S, Papanicolaou VG (1996) General asymptotics estimates for the coupon collector problem. J. Comput. Appl. Math. 67:277–289

    Article  MathSciNet  Google Scholar 

  • Dean D, Franklin M (2002) An algebraic approach to IP traceback. ACM Trans Inf Syst Secur 5:119–137

    Article  Google Scholar 

  • Di Natale G, Doulcier M, Flottes M-L, Rouzeyre B (2008) Low-cost self-test of crypto devices. In: 2nd Workshop on Dependable and Secure Nanocomputing

  • Feller W (1967) An introduction to probability theory and its applications, 3rd ed., vol. 1 John Wiley & Sons

  • Furia CA, Meyer B, Oriol M, Tikhomirov A, Wei Y (2013) The search for the laws of automatic random testing. In: Proceedings of the 28th Annual ACM Symposium on Applied Computing, pp 1211–1216. ACM

  • Galambos J, Simonelli I (1996) Bonferroni-type inequalities with applications. Springer-Verlag

  • Goodrich MT (2002) Efficient packet marking for large-scale IP traceback. In: Proceedings of the 9th ACM Conference on Computer and Communication Security, pp 117–126

  • Holst L (2001) Extrem value distributions for random coupon collector and birthday problems. Extremes 4(2):129–145

    Article  MathSciNet  Google Scholar 

  • Holst L (1986) On birthday, collectors’, occupancy and other classical urn problems. International Statistical Review/Revue Internationale de Statistique 54 (1):15–27

    MathSciNet  MATH  Google Scholar 

  • Kobza JE, Jacobson SH, Vaughan DE (2007) A survey of the coupon collector’s problem with random sample sizes. Methodol. Comput. Appl. Probab. 9:573–584

    Article  MathSciNet  Google Scholar 

  • Martinez S (2004) Some bounds on the coupon collector problem. Random Structure and Algorithms 25:208–226

    Article  MathSciNet  Google Scholar 

  • May R (2008) Coupon collecting with quotas. The electronic journal of combinatorics 15(1):31

    Article  MathSciNet  Google Scholar 

  • Myers AN, Wilf HS (2003) Some new aspects of the coupon collector’s problem. SIAM J. Discrete Math. 17(1):1–17

    Article  MathSciNet  Google Scholar 

  • Papanicolaou VG, Kokolakis GE, Boneh S (1998) Asymptotics for the random coupon collector problem. J. Comput. Appl. Math. 93:95–105

    Article  MathSciNet  Google Scholar 

  • Savage A, Wetherall D, Karlin A, Anderson T (2001) Network support for IP traceback. IEEE/ACM Trans. Networking 9(3):226–237

    Article  Google Scholar 

  • Shank NB, Yang H (2013) Coupon collector problem for non-uniform coupons and random quotas. the electronic journal of combinatorics 20(2):33

    Article  MathSciNet  Google Scholar 

  • Shioda S (2006) Some upper and lower bounds on the coupon collector problem. J Comput Appl Math 200(1):154–167

    Article  MathSciNet  Google Scholar 

  • Shioda S (2009) A theoretical approach to parameter value selection of probabilistic packet marking for ip traceback. In: Proceeding of the Asian Internet Engineering Conference (AINTEC)

  • Smythe RT (2011) Generalized coupon collection: the superlinear case. J Appl Probab 48:189–199

    Article  MathSciNet  Google Scholar 

  • Song D, Perrig A (2001) Advanced and authenticated techniques for IP traceback. In: IEEE INFOCOM

  • Stadje W (1990) The collector’s problem with group drawing. Adv. Appl. Prob. 22:866–874

    Article  MathSciNet  Google Scholar 

  • Yaar A, Perrig A, Song D (2005) FIT: Fast Internet traceback. In: IEEE INFOCOM

Download references

Acknowledgments

The author gratefully acknowledges comments received from the anonymous reviewers that led to material improvements in the paper.

Author information

Authors and Affiliations

  1. Chiba University, 1-33 Yayoi, Inage, Chiba, 263-8522, Japan

    Shigeo Shioda

Authors
  1. Shigeo Shioda
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shigeo Shioda.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix A: Proof of (5)

Define

$$ f(i)\overset{\text{def}}{=}\sum\limits_{l =0}^{i-m} (-1)^{l} {i \choose l+m}{l+m-1 \choose l}. $$

It is obvious that f(m) = 1. Suppose that f(i) = 1 for some integer i ≥ m. Observe that

$$ \begin{array}{ll} f(i+1)&=\sum\limits_{l =0}^{i+1-m} (-1)^{l} {l+m-1 \choose l}{i+1 \choose l+m}\\ &=\sum\limits_{l =0}^{i+1-m} (-1)^{l} {l+m-1 \choose l}\left( {i \choose l+m-1}+{i \choose l+m}\right)\\ &=f(i) +\sum\limits_{l=0}^{i+1-m}(-1)^{l}{l+m-1 \choose l}{i \choose l+m-1}\\ &= f(i) +{i \choose m-1}\sum\limits_{l =0}^{i+1-m}(-1)^{l}{i+1-m \choose l}\\ &=f(i). \end{array} $$

Hence, by induction, f(i) = 1 for any integer i ≥ m.

Appendix B: Proof of (7)

It is straightforward to verify that f(n)(i,n) = 1 for all nonnegative integers i and n. Assume that (7) holds for some integer j ≥ n and for all nonnegative integers i. Observe that

$$ \begin{array}{@{}rcl@{}} f^{(n)}(i,j+1)&=&\sum\limits_{l=0}^{\min\{i,j+1-n\}} (-1)^{l} {j+1 \choose l+n}{l+n-1 \choose l}\\ &=&\sum\limits_{l=0}^{\min\{i,j+1-n\}} (-1)^{l} \left( {j \choose l+n-1}+{j \choose l+n}\right){l+n-1 \choose l}\\ &=&f^{(n)}(i,j)+ \sum\limits_{l=0}^{\min\{i,j+1-n\}} (-1)^{l} {j \choose l+n}{l+n-1 \choose l}\\ &=&f^{(n)}(i,j)+{j \choose n-1}\sum\limits_{l=0}^{\min\{i,j+1-n\}} (-1)^{l} {j-n+1 \choose l}, \end{array} $$

where

$$ \sum\limits_{l=0}^{\min\{i,j+1-n\}} (-1)^{l} {j-n+1 \choose l}=\begin{cases} (-1)^{i} {j-n \choose i}, & i<j-n+1\\ 0. & i\geq j-n+1 \end{cases} $$

Therefore, if i is even, then

$$ f^{(n)}(i,j+1)=f^{(n)}(i,j)+{j-n \choose i}\text{\boldmath $1$}(i<j-n+1)\geq f^{(n)}(i,j)\geq 0. $$

where 1(A) is equal to 1 (0) if A is true (false). We also see that f(n)(i,j + 1) ≤ f(n)(i,j) if i is odd. Thus, the proof is completed by induction.

Appendix C: Proof of (19)

It follows from (7) that

$$ \begin{array}{@{}rcl@{}} g(i;m_{1})&=&\sum\limits_{l_{1}; 0\leq l_{1}\leq m_{1}-k_{1},l_{1} \leq i} \left\{(-1)^{l_{1}}{m_{1} \choose l_{1}+k_{1}}{l_{1}+k_{1}-1 \choose l_{1}}\right\}\\ &=&f^{(k_{1})}(i,m_{1}) \begin{cases} \geq 1, &\text{if \textit{i} is even,}\\ \leq 1, &\text{if \textit{i} is odd.} \end{cases} \end{array} $$

Now assume that for some positive integer n

$$ \begin{array}{@{}rcl@{}} g(i;m_{1},\dots,m_{n}) \begin{cases} \geq 1, &\text{if \textit{i} is even,}\\ \leq 1, &\text{if \textit{i} is odd.} \end{cases} \end{array} $$
(1)

Observe that

$$ g(i;m_{1},\dots,m_{n},m_{n+1})=\sum\limits_{s=0}^{i} h(s;m_{1},\dots,m_{n})g(i-s;m_{n+1}), $$

where

$$ \begin{array}{@{}rcl@{}} h(i;m_{1},\dots,m_{n})&\overset{\text{def}}{=}&\sum\limits_{(l_{1},\dots,l_{n}); 0\leq l_{j}\leq m_{j}-k_{j},{\sum}_{j} l_{j} = i} \prod\limits_{j=1}^{n}\left\{(-1)^{l_{j}}{m_{j} \choose l_{j}+k_{j}}{l_{j}+k_{j}-1 \choose l_{j}}\right\}\\ &=& g(i;m_{1},\dots,m_{n})- g(i-1;m_{1},\dots,m_{n}). \end{array} $$

It follows from the definition and (1) that

$$ h(i;m_{1},\dots,m_{n}) \begin{cases} \geq 0, &\text{if \textit{i} is even,}\\ \leq 0, &\text{if \textit{i} is odd.} \end{cases} $$

Suppose that i is even. If s is even, i − s is also even; thus, \(h(s;m_{1},\dots ,m_{n})g(i-s;m_{n+1})\geq h(s;m_{1},\dots ,m_{n})\) because \(h(s;m_{1},\dots ,m_{n})\geq 0\) and g(i − s; mn+ 1) ≥ 1. If s is odd, i − s is also odd; thus, \(h(s;m_{1},\dots ,m_{n})g(i-s;m_{n+1})\geq h(s;m_{1},\dots ,m_{n})\) because \(h(s;m_{1},\dots ,m_{n})\leq 0\) and 0 ≤ g(i − s; mn+ 1) ≤ 1. From the above consideration, it follows that

$$ \begin{array}{@{}rcl@{}} g(i;m_{1},\dots,m_{n},m_{n+1})&=& \sum\limits_{s=0}^{i} h(s;m_{1},\dots,m_{n})g(i-s;m_{n+1})\\ &\geq& \sum\limits_{s=0}^{i} h(s;m_{1},\dots,m_{n}) \\ &=&g(i;m_{1},\dots,m_{n})\geq 1. \end{array} $$

Next, suppose that i is odd. If s is even, i − s is odd; thus, \(h(s;m_{1},\dots ,m_{n})g(i-s;m_{n+1})\leq h(s;m_{1},\dots ,m_{n})\) because \(h(s;m_{1},\dots ,m_{n})\geq 0\) and 0 ≤ g(i − s; mn+ 1) ≤ 1. If s is odd, i − s is even; thus, \(h(s;m_{1},\dots ,m_{n})g(i-s;m_{n+1})\leq h(s;m_{1},\dots ,m_{n})\) because \(h(s;m_{1},\dots ,m_{n})\leq 0\) and g(i − s; mn+ 1) ≥ 1. Thus, it follows that

$$ \begin{array}{@{}rcl@{}} g(i;m_{1},\dots,m_{n},m_{n+1})&=& \sum\limits_{s=0}^{i} h(s;m_{1},\dots,m_{n})g(i-s;m_{n+1})\\ &\leq& \sum\limits_{s=0}^{i} h(s;m_{1},\dots,m_{n}) \\ &=&g(i;m_{1},\dots,m_{n})\leq 1. \end{array} $$

Thus, we have

$$ \begin{array}{@{}rcl@{}} g(i;m_{1},\dots,m_{n+1}) \begin{cases} \geq 1, &\text{if \textit{i} is even,}\\ \leq 1, &\text{if \textit{i} is odd.} \end{cases} \end{array} $$

This completes the proof by induction.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shioda, S. Coupon Subset Collection Problem with Quotas. Methodol Comput Appl Probab 23, 1203–1235 (2021). https://doi.org/10.1007/s11009-020-09811-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11009-020-09811-z

Keywords

Mathematics Subject Classification (2010)

Search

Navigation