Contributions to the Generalized Coupon Collector and LRU Problems

2017/06/16 by Berthet, Christian
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1706.05250

Abstract

Based upon inequalities on Subset Probabilities, proofs of several conjectures on the Generalized Coupon Collector Problem (i.e. CCP with unequal popularity) are presented. Then we derive a very simple asymptotic relation between the expectation of the waiting time for a partial collection in the CCP, and the Miss rate of a LRU cache.

Related

• On the coupon-collector's problem with several parallel collections
• On Von Schelling Formula for the Generalized Coupon Collector Problem
• New results on a generalized coupon collector problem using Markov chains
• Approximation Theorems Related to the Coupon Collector's Problem
• A note on the coupon - collector's problem with multiple arrivals and the random sampling