# Distributing items randomly into groups of equal size

Given n items (20% type A, 80% type B), I'm looking for a way to distribute them randomly into g groups of equal size. It must be possible for one group to end up with As in the majority but it must not be inevitable. I.e. If I was using binomial distribution, it would be extremely unlikely (with large values of n) to get a group in which the proportion of As was far from 20%. With uniform distribution between 0 and n/g, the first group to which As were allocated would almost always get many more As than the other groups (because the mean of the distribution function would be 50% rather than 20%).

I don't know much about stats and probability so this may be a stupid question but I suppose what I am asking for is a distribution function whose mean is 0.2 but which is likely to generate numbers between 0 and 0.2 and numbers between 0.2 and 1 with equal probability as well.

• I do not know what you mean. Why doesn’t the uniform distribution on [0,0.4] satisfy your condition in the second paragraph? – Tsuyoshi Ito Jul 18 '11 at 19:13
• I need it to generate 1 with some non-zero probability too. Uniform over [0,0.4] will never give you anything more than 0.4 right? – Nick Jul 18 '11 at 19:58
• By your own constraints, you're requiring 0.2 to be the mean and the median of the distribution. One way to achieve this is to place a uniform distribution on [0,0.2] and construct a (probably exponential) distribution on [0.2,1] whose mean is at 0.3. Taking the average of these distributions will yield what you want. – Suresh Venkat Jul 18 '11 at 20:49
• “I need it to generate 1 with some non-zero probability too.” Where did you state that requirement? – Tsuyoshi Ito Jul 18 '11 at 21:17
• I feel that "it must be possible for one group to end up with As in the majority" and "numbers between 0.2 and 1" suggest it. Maybe not :D. – Nick Jul 18 '11 at 21:34

To a statistician there is an unambiguous meaning to this statement. Which is to take n items, mark 20% of them as being of type A, shuffle them, then pull off groups of size n/g. For large n the resulting distribution will be very close to the binomial one. But it won't exactly be the binomial distribution. In fact there is a persistent bias towards being even more even than the binomial distribution, because when one thing of type A goes into a group it fills the group up a bit and makes it less likely that the next thing will go into that group.
It is straightforward to write code to create a list of things, perform a shuffle, and then pull out the groups. This will run in time O(n).