Random Shuffle - expected distributions

Factual Questions
21

It gets even worse for larger decksizes, e.g. 6. Just now, hoping my coding skill isn’t too rusty, I did something like



ln -s /dev/tty badsort.c
cc -o badsort badsort.c
#include        <stdio.h>
#include        <stdlib.h>

#define NUMEL   6

int main(int argc, char **argv)
{
        int     a[NUMEL], b[NUMEL], u, t, k;

        for (a[0] = 0; a[0] < NUMEL; a[0]++)
        for (a[1] = 0; a[1] < NUMEL; a[1]++)
        for (a[2] = 0; a[2] < NUMEL; a[2]++)
        for (a[3] = 0; a[3] < NUMEL; a[3]++)
        for (a[4] = 0; a[4] < NUMEL; a[4]++)
        for (a[5] = 0; a[5] < NUMEL; a[5]++) {
                for (k = 0; k < NUMEL; k++)
                        b[k] = k;
                for (k = 0; k < NUMEL; k++) {
                        t = a[k];
                        u = b[t];
                        b[t] = b[k];
                        b[k] = u;
                }
                for (k = 0; k < NUMEL; k++)
                        printf("%c", b[k] + 'A');
                printf("
");
        }
}
^D
badsort | sort | uniq -c | sort -nr | more

and discovered that BCAEFD occurred a whopping 159 times, while FABCDE occurred just 32 times, barely a fifth as often! Each should have occurred 6^6/6! = 64.8 times.

22

Which in turn means that, once you see a few cards, you can make a much better guess than you should be able to about which cards will be coming next. Which breaks pretty much any card-based casino game.

23

If you do 52 swaps where the first swap element is random (not sequential) there must be a bigger chance that a number of slots did not get selected to be swapped from. Of course they may be on the receiving end of a swap but intuitively (which is a bad thing to say in probability) the odds of a slot not being swapped from or to is higher. Whereas doing each slot sequentially, the only way a number ends up in its original slot is if it is swapped out and then back again (or swapped through three or more slots)

OTOH, there’s no reason to stop at 52 if the slot you swap from is selected at random. Do 1000 swaps of random slots and it’s highly unlikely There’s a slot that does not get swapped from or to.

24

Yeah, repeat it a thousand times, and even a not-very-good shuffling procedure will probably be acceptable. But random numbers are expensive.

25

There are 27 different ways the array can be shuffled. A permutation is … a permutation.

Doing it the right way and there are 6 different ways the array can be shuffled.

6 is a multiple of 6. 27 isn’t. Some outcomes are going to occur more often than others. That’s not likely to be desired.

26

With the code from above:

What if j is 1 for card number 1? Doesn’t that mean the number stays in its original slot?

Actually, thinking about this more, this came up when my son had a blackjack game he had to program for school, and I was just showing him a quick way to shuffle the deck - first card random, second card random, swap them, do that 1000 times and it’s good enough for your program. He then proceeded to ask me “What if each number is the same, isn’t it swapping the card with itself?” at which point I grounded him for talking back :slight_smile:

27

Yes. If you want a random reordering of the deck, you have to have the possibility that the top card stays on top.

28

I have a personal anecdote that is exactly on point. Big ass technical post follows…

In a former job one of the things my company did was verify the math models of casino games. This included analysis of PRNGs in general and PRNG applications that shuffled decks of cards. Part of this was done by generating millions of shuffles and analyzing those with a battery of tests that determined if the data set was statistically distinguishable from perfectly uniformly random.

A different mathematician was evaluating a blackjack game that used the following algorithm for shuffling blackjack shoes that contained 1, 2, 6, and 8 decks:

  1. Start with an array [0, 1, … , 50, 51] * (number of decks).
  2. Randomly choose two distinct indices of this array and swap the elements in those spots. (The underlying PRNG used for this was the Mersenne Twister for those interested.)
  3. Do step 2 a total of 1000 * (number of decks) times.

This was not a perfectly uniformly random shuffle for a couple reasons, but we could certify for use in the field if it was statistically indistinguishable from an unbiased shuffle.

So this algorithm was passing most of the tests. As an aside, one of the tests was essentially the test that was proposed in the OP. Look at what shows up at every position and see if that matches the expected distribution (uniform in this case).

It was, however, super failing one of the tests. This test was called the longest cycle test. This looked at each shuffle as a permutation in disjoint cycle notation (Seen here), and compared the distribution of the length of the longest cycle of each to the expected distribution of an unbiased shuffle (very very not uniform, fyi).

The manner of the failure was pretty bizarre, and the reason I was called in to the project. Only the single deck implementation was failing and it was failing because it never produced a shuffle with a longest cycle of length 52. In the grand scheme of things, these are relatively rare, but we had a huge data set and were expecting thousands and were instead getting exactly zero.

What was the problem? Permutations come in even and odd varieties. There’s a couple different logically equivalent to define this, but I’ll go with every there is a canonical matrix group representation of every perumutation group. Half the matrices in this group will have a determinant of 1, we’ll call these even, and the other half will have a determinant of -1, which we will call odd (provided we a permuting more than one item). The reason I’m defining things this way is that the determinant of the product of matrices is the product of the determinants of the matrices.

One more fact that we need is that the determinant of a transposition (swapping two elements) is always -1.

So the algorithm always produced a shuffle equivalent to the product of 1,000 transpositions so it had a determinant of (-1)^1000 = 1. While every cycle of length 52 can be written as the product of 51 transpositions so it has a determinant of (-1)^51 = -1. So while the algorithm was pretty good in most ways, it was incapable of producing a specific type of permutation and we lucked out in that a subset of that set was a kind of permutation that we were looking for.

One extra bit of weirdness was that the multi-deck versions of algorithm weren’t failing because sometimes the algorithm we swap a card for a copy of itself which was equivalent to doing nothing. Thus the multi-deck version could produce both even and odd permutations and did so with equal frequency. I’m leaving out some technical details of decomposing multi-deck shuffles into disjoint cycles, but that’s the gist of it.

29

Epilogue: Our recommended fix? Just use a Fisher Yates shuffle like you should have in the first place.

30

As my anecdote shows, you definitely want this to be the case. At least once in a while.

But also your described algorithm is almost 40 times the work of a Fisher Yates shuffle and the results aren’t as good. Although this difference is in all likelihood undetectable.

31

On the one hand, at some point programmer time is more valuable than computer time, so you want something that can be programmed quickly.

On the other hand, what takes least programmer time of all is to just copy-and-paste someone else’s implementation of a standard algorithm.

And to sum up the bug in Lance Turbo’s example, it only gave half of all possible shuffles. Which means that if you dealt out 50 of the 52 cards, you’d be able to say, with 100% certainty, what order the last two were in. OK, games rarely go all the way through a deck, but that’s still something you want to avoid.

32

One crazy thing is that almost every roll your own shuffle algo that I’ve seen is much more complicated than a Fisher Yates shuffle and more than half the time fatally flawed.

Here’s a Python implementation…


from random import randrange

def FYShuffle(items):
    i = len(items)
    while i > 1:
        i = i - 1
        j = randrange(i)  # 0 <= j <= i-1
        items[j], items* = items*, items[j]

It’s also already coded up for you in the random library.

33

And that’s the great thing with using a standard algorithm: You don’t have to waste any valuable programmer time determining whether it works.

34

I understand that it would happen due to the nature of randomness. I was just happy that he saw it. Plus, I didn’t really ground him, you know? :slight_smile:

Also, that depends on your definition of “work”. Took me about 2 minutes to explain it and code it up. Much longer than searching for “Fisher Yates shuffle” and then trying to explain that.

Programming is based on requirements, this one being “fast to code up and easily explainable”

35

Most programmers don’t seem overly concerned about the cost. 32 random bits are usually spent just to pick a uniform variate on 1 <= x <= 52; instead less than 6 bits are needed (on average) if you do it properly.

How many random bits do they spend to shuffle a deck? I spend about 7.05*32 bits, in close agreement with log[sub]2/sub. I think my code is correct, but will PM it to skeptics.

Fisher-Yates is trivial if you think methodically. You want one of 52 cards to appear in the #1 slot with equal likelihood; the 1st line of my pseudocode above does exactly that. And so on.

36

It’s a straightforward implementation of Fisher Yates which is logically equivalent to what you posted.

Here’s the source…


def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.
    
    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """
    
    if random is None:
        random = self.random
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x*
        j = int(random() * (i+1))
        x*, x[j] = x[j], x*
37

So does it grab 51 random floats when sorting a 52-deck? In that case it is MUCH more spendthrift than my code which, as I said, uses only 7.05 32-bit random words on average.

38

It’s equivalent to the algorithm you outlined in post #3.

39

True. But that only helps if you already know Fisher-Yates. Which I didn’t. I DID know swap two random cards. And I did make sure to tell him it wasn’t the best way to do it.

But now I do know Fisher-Yates, so there’s that. Thanks!

40

I’d better stop after this post since you seem to be missing the complete context of my question. We’re not speaking about the validity of the random shuffle. We’re asking How many random bits are consumed?
A naive implementation of shuffle will consume 51 random words, however the library provides a word, but ’ random on {1,2,3,4,5,6,7,8} ’ only needs to consume three random bits.

And nevermind that (random_word % 49) is very very slightly biased against large residues. Similarly (random_float * 49) must also be biased unless the exact number of possible random_floats is a multiple of 49.