[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 correct answer is that there would be no error. It would still be fair.
Dialogue: 0,0:00:04.00,0:00:08.00,Default,,0000,0000,0000,,Each permutation of the deck would occur with equal probability,
Dialogue: 0,0:00:08.00,0:00:13.00,Default,,0000,0000,0000,,but it would take N divided by N - 1 times longer--just a tiny bit longer.
Dialogue: 0,0:00:13.00,0:00:19.00,Default,,0000,0000,0000,,We can see that what's happening here is if you remember what our deck looked like,
Dialogue: 0,0:00:19.00,0:00:21.00,Default,,0000,0000,0000,,when we got to the second to last element,
Dialogue: 0,0:00:21.00,0:00:28.00,Default,,0000,0000,0000,,we swapped the second to last element with a random selection from the last 2,
Dialogue: 0,0:00:28.00,0:00:31.00,Default,,0000,0000,0000,,so that's up to N - 1.
Dialogue: 0,0:00:31.00,0:00:36.00,Default,,0000,0000,0000,,If we changed the range to go all the way to N, then we would do 1 more step
Dialogue: 0,0:00:36.00,0:00:43.00,Default,,0000,0000,0000,,where we would swap the last element with an item in the range of just the last element.
Dialogue: 0,0:00:43.00,0:00:47.00,Default,,0000,0000,0000,,So swapping the last element with itself--that would be the only choice--
Dialogue: 0,0:00:47.00,0:00:49.00,Default,,0000,0000,0000,,that wouldn't really do anything effective.
Dialogue: 0,0:00:49.00,0:00:51.00,Default,,0000,0000,0000,,It wouldn't hurt. It would just take a little bit longer.
Dialogue: 0,0:00:51.00,0:00:58.00,Default,,0000,0000,0000,,And so to avoid that redundant operation, we'd use N - 1 rather than N.