English subtitles

← Is It Random Solution - Design of Computer Programs

Get Embed Code
1 Language

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. [Norvig] And the answer is that every permutation has a non-zero probability,
  2. but they don't all have the same probability.
  3. And let's see how I discovered that.
  4. I wrote some test code that generated this output,
  5. and what I did is I gave it some example inputs, some example decks, that were very simple.
  6. First I gave it the deck consisting of 3 items--a, b, and c--
  7. and then I gave it the deck consisting of 2 items--a and b--
  8. and I had it test for both shuffle algorithms--the correct algorithm and the teacher's algorithm.
  9. I had it generate a few thousand decks, shuffle them,
  10. and then figure out how many times each of the possible outcomes come out.
  11. For 3 cards there's 6 possible permutations.
  12. Both shuffle algorithms generated all 6.
  13. For the correct shuffle algorithm you can see that they're all about 1/6 of the time.
  14. 1/6 of the time would be 16.6667%, and they're all pretty close to that.
  15. For the teacher's shuffle algorithm, not so much.
  16. Notice that the combination abc only shows up 5% of the time,
  17. whereas some of the other combinations show up 27% of the time.
  18. Not very good distribution of probability at all,
  19. so there's something wrong with that algorithm.
  20. And it's even more obvious when we just give it the trivial case of a 2-card deck.
  21. With the correct algorithm it turns out to be exactly 50-50.
  22. It might have been 49.1, 50.1.
  23. This is just luck that it was exactly 50-50 in my simulation.
  24. But with the teacher's algorithm, way off.
  25. 1/6 of the time you get ab, and 5/6 of the time you get ba.