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
Jim Gillogly (jim@acm.org)
Fri, 30 Oct 1998 14:14:10 -0800
I wrote [analyzing the bad shuffling algorithm for 3 elements]:
>So the six possible permutations of abc have this probability:
>abc: 5/27
>acb: 5/27
>bac: 4/27
>bca: 4/27
>cab: 4/27
>cba: 5/27
>
>This is a subtle effect and wouldn't be noticeable for 256 elements,
Greg Rose wrote:
> Actually, there is a paper somewhere which I saw once, and have been
> totally unable to find ever since, which proves that as the number of
> elements increases, the discrepancy in probabilities for this incorrect
> algorithm *increases*. By that, I mean that the ratio of probabilities of
> the most probable outcomes and the least probable, increases. This is a
> counterintuitive result, which I can't prove myself, although it looked
> like a correct proof at the time.
My gosh, you're right! I just did a quicky Perl hack to test the
effect. It agreed with the distribution of my hand-job on the three
elements above. For 4 elements, the lowest permutation gets 8 (out of
256) and the highest is 15. For 5 elements the lowest is 16 and the
highest is 47. For 6 elements they range from 32 to 159.
The straightforward shuffling algorithm is not subtly bad for large N,
it's <stunningly> bad.
Bottom line -- using Knuth's Algorithm P. (I'm starting to sound
like a well-known character in sci.crypt pushing his personal favorite.)
-- Jim Gillogly Trewesday, 9 Blotmath S.R. 1998, 22:06 12.19.5.11.12, 10 Eb 5 Zac, Seventh Lord of Night
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23