[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.00,Default,,0000,0000,0000,,[Norvig] And the answer is that every permutation has a non-zero probability,
Dialogue: 0,0:00:04.00,0:00:06.00,Default,,0000,0000,0000,,but they don't all have the same probability.
Dialogue: 0,0:00:06.00,0:00:08.00,Default,,0000,0000,0000,,And let's see how I discovered that.
Dialogue: 0,0:00:08.00,0:00:11.00,Default,,0000,0000,0000,,I wrote some test code that generated this output,
Dialogue: 0,0:00:11.00,0:00:16.00,Default,,0000,0000,0000,,and what I did is I gave it some example inputs, some example decks, that were very simple.
Dialogue: 0,0:00:16.00,0:00:19.00,Default,,0000,0000,0000,,First I gave it the deck consisting of 3 items--a, b, and c--
Dialogue: 0,0:00:19.00,0:00:23.00,Default,,0000,0000,0000,,and then I gave it the deck consisting of 2 items--a and b--
Dialogue: 0,0:00:23.00,0:00:29.00,Default,,0000,0000,0000,,and I had it test for both shuffle algorithms--the correct algorithm and the teacher's algorithm.
Dialogue: 0,0:00:29.00,0:00:34.00,Default,,0000,0000,0000,,I had it generate a few thousand decks, shuffle them,
Dialogue: 0,0:00:34.00,0:00:38.00,Default,,0000,0000,0000,,and then figure out how many times each of the possible outcomes come out.
Dialogue: 0,0:00:38.00,0:00:42.00,Default,,0000,0000,0000,,For 3 cards there's 6 possible permutations.
Dialogue: 0,0:00:42.00,0:00:46.00,Default,,0000,0000,0000,,Both shuffle algorithms generated all 6.
Dialogue: 0,0:00:46.00,0:00:52.00,Default,,0000,0000,0000,,For the correct shuffle algorithm you can see that they're all about 1/6 of the time.
Dialogue: 0,0:00:52.00,0:00:58.00,Default,,0000,0000,0000,,1/6 of the time would be 16.6667%, and they're all pretty close to that.
Dialogue: 0,0:00:58.00,0:01:01.00,Default,,0000,0000,0000,,For the teacher's shuffle algorithm, not so much.
Dialogue: 0,0:01:01.00,0:01:06.00,Default,,0000,0000,0000,,Notice that the combination abc only shows up 5% of the time,
Dialogue: 0,0:01:06.00,0:01:11.00,Default,,0000,0000,0000,,whereas some of the other combinations show up 27% of the time.
Dialogue: 0,0:01:11.00,0:01:13.00,Default,,0000,0000,0000,,Not very good distribution of probability at all,
Dialogue: 0,0:01:13.00,0:01:16.00,Default,,0000,0000,0000,,so there's something wrong with that algorithm.
Dialogue: 0,0:01:16.00,0:01:20.00,Default,,0000,0000,0000,,And it's even more obvious when we just give it the trivial case of a 2-card deck.
Dialogue: 0,0:01:20.00,0:01:24.00,Default,,0000,0000,0000,,With the correct algorithm it turns out to be exactly 50-50.
Dialogue: 0,0:01:24.00,0:01:27.00,Default,,0000,0000,0000,,It might have been 49.1, 50.1.
Dialogue: 0,0:01:27.00,0:01:31.00,Default,,0000,0000,0000,,This is just luck that it was exactly 50-50 in my simulation.
Dialogue: 0,0:01:31.00,0:01:34.00,Default,,0000,0000,0000,,But with the teacher's algorithm, way off.
Dialogue: 0,0:01:34.00,0:01:40.00,Default,,0000,0000,0000,,1/6 of the time you get ab, and 5/6 of the time you get ba.