Large deviation asymptotics for occupancy problems

Details Large deviation asymptotics for occupancy problems Large deviation asymptotics for occupancy problems

2004-10-06

arxiv.org/abs/math/0410174v1

Annals of Probability 2004, Vol. 32, No. 3B, 2765-2818

Mathematics

Probability

Published by the Institute of Mathematical Statistics (http://www.imstat.org) in the Annals of Probability (http://www.imsta

Scientific paper

10.1214/009117904000000135

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.

Affiliated with

Also associated with

No associations

Rating

Large deviation asymptotics for occupancy problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large deviation asymptotics for occupancy problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large deviation asymptotics for occupancy problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-171348