# Random Shuffle - expected distributions **URL:** \ **Category:** Factual Questions\ **Created:** [November 6, 2019, 7:45am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067 "2019-11-06T07:45:57Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 7, 2019, 3:02am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/21 "2019-11-07T03:02:14Z")
> [@ftg](#): > > Um, it’s not a uniform distribution. Some permutations occur more than others… > > Example: with 3 elements you get will generate one of 3[sup]3[/sup]=27 outcomes, and there are 3!=6 permutations. 27/6 is 4.5. [corrected typo – sgs7] So some permutations occur 4 times in the outcomes and some occur 5 times. If you do it right all appear the same number of times. In this case once. It gets even worse for larger decksizes, e.g. 6. Just now, hoping my coding skill isn’t _too_ rusty, I did something like ```auto ln -s /dev/tty badsort.c cc -o badsort badsort.c #include #include #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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 7, 2019, 3:36am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/22 "2019-11-07T03:36:30Z")
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. ---
**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\ **Post date:** [November 7, 2019, 6:15am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/23 "2019-11-07T06:15:25Z")
> [@Slash1972](#): > > What’s wrong with doing it this way? 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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 7, 2019, 1:37pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/24 "2019-11-07T13:37:04Z")
Yeah, repeat it a thousand times, and even a not-very-good shuffling procedure will probably be acceptable. But random numbers are expensive. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 7, 2019, 9:14pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/25 "2019-11-07T21:14:58Z")
> [@Slash1972](#): > > Sorry, I don’t understand the difference between “outcomes” and “permutations” in this context. There are 27 different ways the array can be shuffled. A permutation is … a [permutation](https://en.wikipedia.org/wiki/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. ---
**Author:** ![Slash1972](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/slash1972/32/6461_2.png) [@Slash1972](https://boards.straightdope.com/u/Slash1972)\ **Post date:** [November 7, 2019, 9:35pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/26 "2019-11-07T21:35:02Z")
> [@md2000](#): > > 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) With the code from above: > [@septimus](#): > > Swap #1 with #j (j uniform random on {1, 2, 3, …, 52}) What if j is 1 for card number 1? Doesn’t that mean the number stays in its original slot? > [@](#): > > 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. 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 🙂 ---
**Author:** ![zimaane](https://avatars.discourse-cdn.com/v4/letter/z/a3d4f5/32.png) [@zimaane](https://boards.straightdope.com/u/zimaane)\ **Post date:** [November 7, 2019, 9:46pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/27 "2019-11-07T21:46:18Z")
> [@](#): > > What if j is 1 for card number 1? Doesn’t that mean the number stays in its original slot? Yes. If you want a random reordering of the deck, you have to have the possibility that the top card stays on top. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [November 7, 2019, 10:26pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/28 "2019-11-07T22:26:02Z")
> [@md2000](#): > > 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. 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](http://mathworld.wolfram.com/PermutationCycle.html)), 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. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [November 7, 2019, 10:32pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/29 "2019-11-07T22:32:22Z")
Epilogue: Our recommended fix? Just use a Fisher Yates shuffle like you should have in the first place. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [November 7, 2019, 10:48pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/30 "2019-11-07T22:48:43Z")
> [@Slash1972](#): > > 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 🙂 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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 7, 2019, 11:09pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/31 "2019-11-07T23:09:46Z")
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. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [November 7, 2019, 11:57pm UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/32 "2019-11-07T23:57:26Z")
> [@Chronos](#): > > 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. 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… ```auto 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](https://docs.python.org/3/library/random.html). ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 8, 2019, 1:01am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/33 "2019-11-08T01:01:18Z")
> [@](#): > > …and more than half the time fatally flawed. 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. ---
**Author:** ![Slash1972](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/slash1972/32/6461_2.png) [@Slash1972](https://boards.straightdope.com/u/Slash1972)\ **Post date:** [November 8, 2019, 1:09am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/34 "2019-11-08T01:09:24Z")
> [@Lance\_Turbo](#): > > 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. 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? 🙂 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” ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 8, 2019, 1:41am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/35 "2019-11-08T01:41:04Z")
> [@Chronos](#): > > … But random numbers are expensive. 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. > [@Lance\_Turbo](#): > > [random — Generate pseudo-random numbers — Python 3.12.2 documentation](https://docs.python.org/3/library/random.html)"]random library 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. > [@Slash1972](#): > > Much longer than searching for “Fisher Yates shuffle” and then trying to explain that. 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. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [November 8, 2019, 1:58am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/36 "2019-11-08T01:58:15Z")
> [@septimus](#): > > 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. It’s a straightforward implementation of Fisher Yates which is logically equivalent to what you posted. Here’s the source… ```auto 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* ``` ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 8, 2019, 2:03am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/37 "2019-11-08T02:03:07Z")
> [@Lance\_Turbo](#): > > … Optional arg random is a 0-argument function returning a random > float in [0.0, 1.0); by default, the standard random.random. 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. ---
**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\ **Post date:** [November 8, 2019, 2:28am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/38 "2019-11-08T02:28:03Z")
It’s equivalent to the algorithm you outlined in post #3. ---
**Author:** ![Slash1972](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/slash1972/32/6461_2.png) [@Slash1972](https://boards.straightdope.com/u/Slash1972)\ **Post date:** [November 8, 2019, 2:31am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/39 "2019-11-08T02:31:42Z")
> [@septimus](#): > > 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. 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! ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 8, 2019, 2:41am UTC](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067/40 "2019-11-08T02:41:04Z")
> [@Lance\_Turbo](#): > > It’s equivalent to the algorithm you outlined in post #3. 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. [Previous page](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067.md?page=1) [Next page](https://boards.straightdope.com/t/random-shuffle-expected-distributions/843067.md?page=3)