Stopping rules in balanced allocation problem: normal order statistics and geometric sums
by
Andrew Rukhin
UMBC

This talk discusses the properties of two most commonly used balanced allocation schemes with several treatments when there is a quota for each treatment. Such sequential schemes are common in clinical trials, load balancing in computer files storage, etc. To force balance in an assignment of sequentially arriving subjects between a number of treatments, one has to choose a randomization design. One of the two following randomization swhich starts with the given, say, uniform probability assignment of subjects to treatments until one of the treatments receives its quota of subjects. Then this distribution switches to the remaining treatments, and the allocation process continues in this way until there is just one treatment with less than its quota is left. This treatment gets then all remaining subjects.

The limiting joint distribution of the instants at which a treatment receives the given number of subjects is found. The behavior of the random allocation scheme is shown to be quite different from that of the truncated multinomial design. For the latter design it is governed by sum of independent geometric random variables, for the former it is shown to be that of spacings for normal order statistics possibly with different variances. In the uniform case, formulas for the accidental bias and for the selection bias of both procedures are derived. The relationship to classical probability theory is discussed. The arising probability distributions involve the largest cell frequency in multinomial trials, the number of remaining matches in the Banach match-box problem, and the number of vacant cells in the occupancy problem.

Date received: February 13, 2007