Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23
Anonymous (nobody@replay.com)
Fri, 30 Oct 1998 20:15:26 +0100
It's a common beginner's mistake to use the wrong algorithm to randomize
an array. Here is an attempt to explain why it is wrong.
Consider an array with three slots, 1, 2, and 3, which initially hold the
values 1, 2 and 3 respectivelly. Call a slot "randomized" if it has an
equal chance of holding any of 1, 2, or 3. Call a slot "biased" if the
chance of holding some value is greater than the chance of holding some
other value. Initially, all the slots are (very) biased, of course.
The naive algorithm has three steps:
1. Swap slot 1 with the contents of a random choice of slots 1, 2, or 3.
2. Swap slot 2 with the contents of a random choice of slots 1, 2, or 3.
3. Swap slot 3 with the contents of a random choice of slots 1, 2, or 3.
After step 1, slot 1 is randomized. No matter what the distribution of
the values was before that step, the fact that a random slot was chosen
and put into slot 1 means that the contents of slot 1 will become random.
Similarly, after step 2, slot 2 is randomized, and after step 3, slot 3
is randomized.
The problem is that when we randomize a slot we can disturb the randomness
of other slots.
Pay attention to slot 2. After step 2, that slot is randomized. Now, when
we do step 3, there is a 2/3 chance that we won't touch slot 2 (because
slots 1 or 3 are chosen to swap). In that case, slot 2 remains randomized.
However, there is a 1/3 chance that we will swap slot 3 into slot 2.
The problem is, slot 3 is biased. If you work out the probabilities in
detail, you find that after step 2, slot 3 holds a 3 with probability 4/9,
a 1 with probability 2/9, and a 2 with probability 3/9.
When you swap slot 3 into slot 2, and slot 3 is biased, you leave slot
2 biased. Since there is a nonzero probability of this happening,
the result is that after step 3, slot 2 is no longer randomized but is
biased.
You can generalize this to n elements. After step n-1, slot n-1 is
randomized but slot n is biased. Then after step n, slot n becomes
randomized, but there is a chance we will swap with slot n-1 and so we
transfer our bias to that slot.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23