(tilly) (still imperfect): Randomize an array

[tilly]

I was trying to figure out how to explain why this was going to give a perfect sort, and I realized that in fact this trick simply cannot give a perfect sort for an array of size larger than 2 when fed an algorithm with bounded performance!

This is cute.

As the above makes clear, you are basically making random coin flips until it spits out an answer. If the array has n entries, there is some maximum number of flips, say k, that you could be asked for.

Turning it around on its head I could just ask you up front to make k coin flips, then feed that into the algorithm, and get an answer. Now there are 2^k possible sequences that you could give me, and they are all equally likely. So if you write in base 2, the probability of any particular permutation is 2^(-k) times the number of sequences that gave that permutation.

What that is I don't care. What I do care about is that when written out in base 2 that probability is a decimal that terminates after at most k places. But for each permutation the probability we really want is 1/n!, and if n is bigger than 2 then n! is divisible by 3 which is *not* a power of two so 1/n! has to be (base 2) an infinite repeating decimal!

In other words I may not, without calculating it, have any idea how your anwer will be biased, but in fact it is!

ObTrivia: A somewhat similar counting argument manages to show that the 400 year Gregorian calendar repeats days of the week, but cannot divide a particular day of the month between them. However it takes explicit calculation to show that the 13'th falls on Friday more than 1 day in 7.