0:00:00.000,0:00:04.000
[Norvig] And the answer is that every permutation has a non-zero probability,
0:00:04.000,0:00:06.000
but they don't all have the same probability.
0:00:06.000,0:00:08.000
And let's see how I discovered that.
0:00:08.000,0:00:11.000
I wrote some test code that generated this output,
0:00:11.000,0:00:16.000
and what I did is I gave it some example inputs, some example decks, that were very simple.
0:00:16.000,0:00:19.000
First I gave it the deck consisting of 3 items--a, b, and c--
0:00:19.000,0:00:23.000
and then I gave it the deck consisting of 2 items--a and b--
0:00:23.000,0:00:29.000
and I had it test for both shuffle algorithms--the correct algorithm and the teacher's algorithm.
0:00:29.000,0:00:34.000
I had it generate a few thousand decks, shuffle them,
0:00:34.000,0:00:38.000
and then figure out how many times each of the possible outcomes come out.
0:00:38.000,0:00:42.000
For 3 cards there's 6 possible permutations.
0:00:42.000,0:00:46.000
Both shuffle algorithms generated all 6.
0:00:46.000,0:00:52.000
For the correct shuffle algorithm you can see that they're all about 1/6 of the time.
0:00:52.000,0:00:58.000
1/6 of the time would be 16.6667%, and they're all pretty close to that.
0:00:58.000,0:01:01.000
For the teacher's shuffle algorithm, not so much.
0:01:01.000,0:01:06.000
Notice that the combination abc only shows up 5% of the time,
0:01:06.000,0:01:11.000
whereas some of the other combinations show up 27% of the time.
0:01:11.000,0:01:13.000
Not very good distribution of probability at all,
0:01:13.000,0:01:16.000
so there's something wrong with that algorithm.
0:01:16.000,0:01:20.000
And it's even more obvious when we just give it the trivial case of a 2-card deck.
0:01:20.000,0:01:24.000
With the correct algorithm it turns out to be exactly 50-50.
0:01:24.000,0:01:27.000
It might have been 49.1, 50.1.
0:01:27.000,0:01:31.000
This is just luck that it was exactly 50-50 in my simulation.
0:01:31.000,0:01:34.000
But with the teacher's algorithm, way off.
0:01:34.000,0:01:40.000
1/6 of the time you get ab, and 5/6 of the time you get ba.