Why does this simple shuffle algorithm produce biased results?

by

See this:
The Danger of Naïveté (Coding Horror)

Let’s look at your three card deck as an example. Using a 3 card deck, there are only 6 possible orders for the deck after a shuffle: 123, 132, 213, 231, 312, 321.

With your 1st algorithm there are 27 possible paths (outcomes) for the code, depending on the results of the rand() function at different points. Each of these outcomes are equally likely (unbiased). Each of these outcomes will map to the same single result from the list of 6 possible “real” shuffle results above. We now have 27 items and 6 buckets to put them in. Since 27 is not evenly divisible by 6, some of those 6 combinations must be over-represented.

With the 2nd algorithm there are 6 possible outcomes that map exactly to the 6 possible “real” shuffle results, and they should all be represented equally over time.

This is important because the buckets that are over-represented in the first algorithm are not random. The buckets selected for the bias are repeatable and predictable. So if you’re building an online poker game and use the 1st algorithm a hacker could figure out you used the naive sort and from that work out that certain deck arrangements are much more likely to occur than others. Then they can place bets accordingly. They’ll lose some, but they’ll win much more than they lose and quickly put you out of business.

More Related Contents:

  1. What distribution do you get from this broken random shuffle?
  2. The number prodigy : reverse sum of pattern
  3. Unique (non-repeating) random numbers in O(1)?
  4. Circle line-segment collision detection algorithm?
  5. How to create the most compact mapping n → isprime(n) up to a limit N?
  6. How do I calculate a point on a circle’s circumference?
  7. Fast permutation -> number -> permutation mapping algorithms
  8. Algorithm to detect intersection of two rectangles?
  9. Sort points in clockwise order?
  10. How do you calculate the average of a set of circular data? [closed]
  11. How do Trigonometric functions work? [closed]
  12. Precise subpixel line drawing algorithm (rasterization algorithm)
  13. Choosing n numbers with fixed sum
  14. Algorithm for finding similar images
  15. Mapping N-dimensional value to a point on Hilbert curve
  16. What’s a good algorithm to determine if an input is a perfect square? [duplicate]
  17. Check if one integer is an integer power of another
  18. nᵗʰ ugly number
  19. Calculate largest inscribed rectangle in a rotated rectangle
  20. 3D Least Squares Plane
  21. Two Rectangles intersection
  22. Fastest primality test
  23. Shortest distance between points algorithm
  24. The Sieve of Atkin
  25. Efficient maths algorithm to calculate intersections
  26. finding a^b^c^… mod m
  27. Test if a number is fibonacci
  28. An inverse Fibonacci algorithm?
  29. what is the fastest way to find the gcd of n numbers?
  30. “Rounding” colour values to the nearest of a small set of colours

Leave a Comment