Why swapping cards at random is not a fair shuffle: Fisher–Yates and the 27 paths
30seconds
Shuffling three cards by swapping each one with a random card from the whole row looks fair, but it is not. It makes 3 × 3 × 3 = 27 equally likely paths for only 6 possible orders, and 27 cannot be split evenly across 6. Some orders get 5 paths, others 4.
Fisher–Yates fixes this by picking only from the cards not yet placed, so the paths number exactly n!, one per order. Run the shuffle lab to see both bias and fix, and why even a perfect algorithm needs a big enough random source.
More in Computing
View all →
How to find one name among a billion in 30 looks: binary search
Pick a number from 1 to 1,000,000 and you can find it in at most 20 yes-or-no questions. The trick is binary search: look in the middle of a sorted list, throw…
Why common letters get short codes in a ZIP file: Huffman coding
ASCII spends 8 bits on every letter, whether it is a common e or a rare z. In 1951 a graduate student, David Huffman, found a way to give frequent symbols…
How a computer finds one flipped bit and fixes it: Hamming's code
A bit can flip in memory, on a disk or in a radio signal, and nothing tells you which one went wrong. In 1950 Richard Hamming published a code that finds the…
Why 0.1 + 0.2 isn't 0.3: flip the 64 bits a computer uses for decimals
Type 0.1 + 0.2 into almost any programming language and you get 0.30000000000000004. Nothing is broken. Computers count in powers of two, and a tenth is an…
How a Bloom filter says "definitely not" using just a few bits
How can a computer check whether a word is on a huge list using only a few bits per entry? A Bloom filter flips a handful of switches for every word you add…
How one extra digit on your bank card catches your typos
The last digit of your bank card number isn't part of your account. It's a check digit, computed from the other fifteen by a recipe an IBM engineer patented in…