Large deviation asymptotics for occupancy problems
Large deviation asymptotics for occupancy problems
复制标题
占用问题的大偏差渐近
DOI：
10.1214/009117904000000135
复制
发表时间：
2004
影响因子：
2.3
通讯作者：
P. Whiting
中科院分区：
文献类型：
--
作者：
P. Dupuis;C. Nuzman;P. Whiting
在占用问题的标准公式中，考虑r个球在n个细胞中的分布，每个球以1/n的概率独立分配给给定的细胞。尽管可以给出各种有趣数量的分布的封闭形式表达式（例如包含给定数量的球的细胞的比例），但这些表达式的实际用途通常有限。近似提供了一种有吸引力的替代方法，在本文中，我们考虑当r和n趋于无穷时的大偏差近似。为了分析这个问题，我们首先考虑一个动态模型，其中球按顺序放置在单元格中，“时间”对应于已经抛出的球的数量。对该“过程级”问题进行了完整的大偏差分析，并通过收缩原理得到原问题的速率函数。分析了表征该速率函数的变分问题，得到了较为完整和显式的解。将最小轨迹和最小代价识别为两个常数，并将该常数表征为初等不动点问题的唯一解。然后使用这些结果来解决许多有趣的问题，包括溢出问题和部分优惠券收集器问题。
In the standard formulation of the occupancy problem one considers the distribution of r balls in n cells, with each ball assigned independently to a given cell with probability 1/n. Although closed form expressions can be given for the distribution of various interesting quantities (such as the fraction of cells that contain a given number of balls), these expressions are often of limited practical use. Approximations provide an attractive alternative, and in the present paper we consider a large deviation approximation as r and n tend to infinity. In order to analyze the problem we first consider a dynamical model, where the balls are placed in the cells sequentially and “time” corresponds to the number of balls that have already been thrown. A complete large deviation analysis of this “process level” problem is carried out, and the rate function for the original problem is then obtained via the contraction principle. The variational problem that characterizes this rate function is analyzed, and a fairly complete and explicit solution is obtained. The minimizing trajectories and minimal cost are identified up to two constants, and the constants are characterized as the unique solution to an elementary fixed point problem. These results are then used to solve a number of interesting problems, including an overflow problem and the partial coupon collector’s problem.