BIRTHDAY PARADOX, COUPON COLLECTORS, CACHING ALGORITHMS AND SELF-ORGANIZING SEARCH
BIRTHDAY PARADOX, COUPON COLLECTORS, CACHING ALGORITHMS AND SELF-ORGANIZING SEARCH
复制标题
DOI：
10.1016/0166-218x(92)90177-c
复制
发表时间：
1992-11-11
影响因子：
1.1
通讯作者：
THIMONIER, L
中科院分区：
文献类型：
--
作者：
FLAJOLET, P;GARDY, D;THIMONIER, L
本文介绍了一个统一的框架来分析一类随机分配过程，包括：（i）生日悖论;（ii）优惠券收集器问题;（iii）独立参考模型下的内存管理系统中的最近最少使用（LRU）缓存;（iv）移动到前启发式的自组织搜索。所有的分析都是针对一般的非均匀概率分布的。首先，概率感兴趣的现象描述的正则语言扩展除了洗牌产品。接下来，系统的翻译机制被用来获得期望和概率分布的积分表示。
This paper introduces a unified framework for the analysis of a class of random allocation processes that include: (i) the birthday paradox; (ii) the coupon collector problem; (iii) least-recently-used (LRU) caching in memory management systems under the independent reference model; (iv) the move-to-front heuristic of self-organizing search. All analyses are relative to general nonuniform probability distributions.Our approach to these problems comprises two stages. First, the probabilistic phenomena of interest are described by means of regular languages extended by addition of the shuffle product. Next, systematic translation mechanisms are used to derive integral representations for expectations and probability distributions.