
[Norvig] And the answer is that every permutation has a nonzero probability,

but they don't all have the same probability.

And let's see how I discovered that.

I wrote some test code that generated this output,

and what I did is I gave it some example inputs, some example decks, that were very simple.

First I gave it the deck consisting of 3 itemsa, b, and c

and then I gave it the deck consisting of 2 itemsa and b

and I had it test for both shuffle algorithmsthe correct algorithm and the teacher's algorithm.

I had it generate a few thousand decks, shuffle them,

and then figure out how many times each of the possible outcomes come out.

For 3 cards there's 6 possible permutations.

Both shuffle algorithms generated all 6.

For the correct shuffle algorithm you can see that they're all about 1/6 of the time.

1/6 of the time would be 16.6667%, and they're all pretty close to that.

For the teacher's shuffle algorithm, not so much.

Notice that the combination abc only shows up 5% of the time,

whereas some of the other combinations show up 27% of the time.

Not very good distribution of probability at all,

so there's something wrong with that algorithm.

And it's even more obvious when we just give it the trivial case of a 2card deck.

With the correct algorithm it turns out to be exactly 5050.

It might have been 49.1, 50.1.

This is just luck that it was exactly 5050 in my simulation.

But with the teacher's algorithm, way off.

1/6 of the time you get ab, and 5/6 of the time you get ba.