3 ms·

How about the following process? Each person gets randomly assigned to one of the two groups, when one group is full, move the rest to the other group. Does thi

by chaoxu 6y ago

How about the following process? Each person gets randomly assigned to one of the two groups, when one group is full, move the rest to the other group. Does this make sure every equal partition have the same probability of showing up?

thaumasiotes 6y ago
> Does this make sure every equal partition have the same probability of showing up? I'm not sure, but I wouldn't bet against it. But what is the value of having an exactly equal partition? On second thought, the algorithm you describe processes people in a particular order, and it is much more likely to put two people who both occur near the end of the list into the same bucket than to put them in different buckets. So if that processing order is constant, the algorithm cannot produce every equal partition with equal probability.
- asheldon 6y ago
  I agree. It would be simpler to shuffle the list of people, then split the list in half. Here's a proof this algorithm doesn't work by counter-example (N=6) Consider a list of 6 elements. Elements 5 and 6 must be in the same bucket 50% of the time and different buckets 50% of the time. For this to be true, after we place the first 4 elements into their buckets according to this algorithm, there must be space left in both buckets 50% of the time and in only one bucket 50% of the time. Sequences of the first 4 coin flips where neither bucket is filled, followed by possible ending sequences, and the odds of the prefix. AABB(AB, BA) = 1/16th ABAB(AB, BA) = 1/16th ABBA(AB, BA) = 1/16th BBAA(AB, BA) = 1/16th BABA(AB, BA) = 1/16th BAAB(AB, BA) = 1/16th Total: 3/8ths Sequences of the first 3-4 coin flips where one bucket is filled, followed by possible ending sequences, and the odds of the prefix: AAA(BBB) = 1/8th BBB(AAA) = 1/8th AABA(BB) = 1/16th ABAA(AA) = 1/16th ABBB(AA) = 1/16th BBAB(AA) = 1/16th BABB(AA) = 1/16th BAAA(BB) = 1/16th Total: 5/8ths Since one bucket is filled 5/8ths of the time after 4 elements are processed according to this algorithm, the final two elements will be in the same bucket 5/8ths of the time, not the expected 4/8ths of the time.

by chaoxu 6y ago

thaumasiotes 6y ago

> Does this make sure every equal partition have the same probability of showing up? I'm not sure, but I wouldn't bet against it. But what is the value of having an exactly equal partition? On second thought, the algorithm you describe processes people in a particular order, and it is much more likely to put two people who both occur near the end of the list into the same bucket than to put them in different buckets. So if that processing order is constant, the algorithm cannot produce every equal partition with equal probability.

asheldon 6y ago
I agree. It would be simpler to shuffle the list of people, then split the list in half. Here's a proof this algorithm doesn't work by counter-example (N=6) Consider a list of 6 elements. Elements 5 and 6 must be in the same bucket 50% of the time and different buckets 50% of the time. For this to be true, after we place the first 4 elements into their buckets according to this algorithm, there must be space left in both buckets 50% of the time and in only one bucket 50% of the time. Sequences of the first 4 coin flips where neither bucket is filled, followed by possible ending sequences, and the odds of the prefix. AABB(AB, BA) = 1/16th ABAB(AB, BA) = 1/16th ABBA(AB, BA) = 1/16th BBAA(AB, BA) = 1/16th BABA(AB, BA) = 1/16th BAAB(AB, BA) = 1/16th Total: 3/8ths Sequences of the first 3-4 coin flips where one bucket is filled, followed by possible ending sequences, and the odds of the prefix: AAA(BBB) = 1/8th BBB(AAA) = 1/8th AABA(BB) = 1/16th ABAA(AA) = 1/16th ABBB(AA) = 1/16th BBAB(AA) = 1/16th BABB(AA) = 1/16th BAAA(BB) = 1/16th Total: 5/8ths Since one bucket is filled 5/8ths of the time after 4 elements are processed according to this algorithm, the final two elements will be in the same bucket 5/8ths of the time, not the expected 4/8ths of the time.