Contributions to the Generalized Coupon Collector and LRU Problems

Christian Berthet

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment