why does this simple shuffle algorithm produce biased results? what is a simple reason?
See this:
The Danger of Naïveté (Coding Horror)
Let's look at your three card deck as an example. Using a 3 card deck, there are only 6 possible orders for the deck after a shuffle: 123, 132, 213, 231, 312, 321.
With your 1st algorithm there are 27 possible paths (outcomes) for the code, depending on the results of the rand() function at different points. Each of these outcomes are equally likely (unbiased). Each of these outcomes will map to the same single result from the list of 6 possible "real" shuffle results above. We now have 27 items and 6 buckets to put them in. Since 27 is not evenly divisible by 6, some of those 6 combinations must be over-represented.
With the 2nd algorithm there are 6 possible outcomes that map exactly to the 6 possible "real" shuffle results, and they should all be represented equally over time.
This is important because the buckets that are over-represented in the first algorithm are not random. The buckets selected for the bias are repeatable and predictable. So if you're building an online poker game and use the 1st algorithm a hacker could figure out you used the naive sort and from that work out that certain deck arrangements are much more likely to occur than others. Then they can place bets accordingly. They'll lose some, but they'll win much more than they lose and quickly put you out of business.
Here's the complete probability tree for these replacements.
Let's assume that you start with the sequence 123, and then we'll enumerate all the various ways to produce random results with the code in question.
123
+- 123 - swap 1 and 1 (these are positions,
| +- 213 - swap 2 and 1 not numbers)
| | +- 312 - swap 3 and 1
| | +- 231 - swap 3 and 2
| | +- 213 - swap 3 and 3
| +- 123 - swap 2 and 2
| | +- 321 - swap 3 and 1
| | +- 132 - swap 3 and 2
| | +- 123 - swap 3 and 3
| +- 132 - swap 2 and 3
| +- 231 - swap 3 and 1
| +- 123 - swap 3 and 2
| +- 132 - swap 3 and 3
+- 213 - swap 1 and 2
| +- 123 - swap 2 and 1
| | +- 321 - swap 3 and 1
| | +- 132 - swap 3 and 2
| | +- 123 - swap 3 and 3
| +- 213 - swap 2 and 2
| | +- 312 - swap 3 and 1
| | +- 231 - swap 3 and 2
| | +- 213 - swap 3 and 3
| +- 231 - swap 2 and 3
| +- 132 - swap 3 and 1
| +- 213 - swap 3 and 2
| +- 231 - swap 3 and 3
+- 321 - swap 1 and 3
+- 231 - swap 2 and 1
| +- 132 - swap 3 and 1
| +- 213 - swap 3 and 2
| +- 231 - swap 3 and 3
+- 321 - swap 2 and 2
| +- 123 - swap 3 and 1
| +- 312 - swap 3 and 2
| +- 321 - swap 3 and 3
+- 312 - swap 2 and 3
+- 213 - swap 3 and 1
+- 321 - swap 3 and 2
+- 312 - swap 3 and 3
Now, the fourth column of numbers, the one before the swap information, contains the final outcome, with 27 possible outcomes.
Let's count how many times each pattern occurs:
123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
27 times total
If you run the code that swaps at random for an infinite number of times, the patterns 132, 213 and 231 will occur more often than the patterns 123, 312, and 321, simply because the way the code swaps makes that more likely to occur.
Now, of course, you can say that if you run the code 30 times (27 + 3), you could end up with all the patterns occuring 5 times, but when dealing with statistics you have to look at the long term trend.
Here's C# code that explores the randomness for one of each possible pattern:
class Program
{
static void Main(string[] args)
{
Dictionary<String, Int32> occurances = new Dictionary<String, Int32>
{
{ "123", 0 },
{ "132", 0 },
{ "213", 0 },
{ "231", 0 },
{ "312", 0 },
{ "321", 0 }
};
Char[] digits = new[] { '1', '2', '3' };
Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2)
{
Char[] result = new Char[] { input[0], input[1], input[2] };
Char temp = result[pos1];
result[pos1] = result[pos2];
result[pos2] = temp;
return result;
};
for (Int32 index1 = 0; index1 < 3; index1++)
{
Char[] level1 = swap(digits, 0, index1);
for (Int32 index2 = 0; index2 < 3; index2++)
{
Char[] level2 = swap(level1, 1, index2);
for (Int32 index3 = 0; index3 < 3; index3++)
{
Char[] level3 = swap(level2, 2, index3);
String output = new String(level3);
occurances[output]++;
}
}
}
foreach (var kvp in occurances)
{
Console.Out.WriteLine(kvp.Key + ": " + kvp.Value);
}
}
}
This outputs:
123: 4
132: 5
213: 5
231: 5
312: 4
321: 4
So while this answer does in fact count, it's not a purely mathematical answer, you just have to evaluate all possible ways the random function can go, and look at the final outputs.
From your comments on the other answers, it seems that you are looking not just for an explanation of why the distribution is not the uniform distribution (for which the divisibility answer is a simple one) but also an "intuitive" explanation of why it is actually far from uniform.
Here's one way of looking at it. Suppose you start with the initial array [1, 2, ..., n] (where n might be 3, or 52, or whatever) and apply one of the two algorithms. If all permutations are uniformly likely, then the probability that 1 remains in the first position should be 1/n. And indeed, in the second (correct) algorithm, it is 1/n, as 1 stays in its place if and only if it is not swapped the first time, i.e. iff the initial call to rand(0,n-1) returns 0.
However, in the first (wrong) algorithm, 1 remains untouched only if it is neither swapped the first time nor any other time — i.e., only if the first rand returns 0 and none of the other rands returns 0, the probability of which is (1/n) * (1-1/n)^(n-1) ≈ 1/(ne) ≈ 0.37/n, not 1/n.
And that's the "intuitive" explanation: in your first algorithm, earlier items are much more likely to be swapped out of place than later items, so the permutations you get are skewed towards patterns in which the early items are not in their original places.
(It's a bit more subtle than that, e.g. 1 can get swapped into a later position and still end up getting swapped back into place through a complicated series of swaps, but those probabilities are relatively less significant.)