Birthday paradox, coupon collectors, caching algorithms and self- organizing search (Q1201808)

The authors present a unified treatment for a class of random allocation processes including the birthday paradox, the coupon collector problem, least-recently-used caching in memory management systems under the independent reference model and the move-to-front heuristic of self- organizing search. These four problems have a common flavor, namely a sequence of elements from a finite universe is drawn at random, according to some probability distribution. When an element arrives, a certain action is taken depending on the different elements present in the system, and a corresponding cost function has to be analysed. Exact solutions to these four problems under a general probability distribution for items (birth dates, coupons, memory references, keys) are provided, only assuming independence. We remark that systematic translation mechanisms are used to derive integral representations for expectations and probability distributions.