﻿[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.