-2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I do not know what you mean. Why doesn’t the uniform distribution on [0,0.4] satisfy your condition in the second paragraph? $\endgroup$ – Tsuyoshi Ito Jul 18 '11 at 19:13
  • $\begingroup$ 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? $\endgroup$ – Nick Jul 18 '11 at 19:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Jul 18 '11 at 20:49
  • $\begingroup$ “I need it to generate 1 with some non-zero probability too.” Where did you state that requirement? $\endgroup$ – Tsuyoshi Ito Jul 18 '11 at 21:17
  • $\begingroup$ 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. $\endgroup$ – Nick Jul 18 '11 at 21:34
1
$\begingroup$

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.

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.