Limiting Distributions in Sequential Occupancy Problem

Abstract

In a general sequential allocation scheme the limiting distribution of the instant at which a treatment receives the given number of subjects is derived. Classical occupancy problems, in particular, the Banach match-box problem and the birthday problem are shown to be closely related and are discussed.

Key Words:

• Banach match-box problem
• Birthday problem
• Combinatorial extreme-value theory
• Load balancing
• Multinomial trials
• Poisson approximation
• Probability generating function
• Skew-normal distribution

MSC 2000 Subject Classification:

• Primary 60E05
• Secondary 60C05
• 62E20
• 62G30

Acknowledgment

This research was supported by NSA grant #MDA904-00-1-0033.

Notes

Recommended by P. Chen