Hand Shuffle

I did some interesting research on shuffling back in March. I wanted to know how many times it is necessary to hand shuffle a deck of cards before it is well-shuffled. First I had to determine what is meant by "well-shuffled". I decided that a good shuffle technique was one which when observed for a large number of shuffles was indistinguishable from a perfect shuffle in the following ways:

Probability that card i ends up in location j. This should be the same for any (i,j).
Number of pairs which were adjacent in unshuffled deck and are still adjacent in shuffled deck (this number should be 1 for any size deck).
Average distance between 2 cards which were adjacent in unshuffled deck. For a well-shuffled 52 card deck, this should be about 20.96.

I wrote an algorithm to simulate a hand-shuffle. I would cut the deck at some point near the middle and then interleave the cards, taking one or two cards from one half and then from the other. Then I would gather stats on the resulting deck, and compare them to the stats for a perfect shuffle, like the one I sent you yesterday.

It turned out that it took about 13 shuffles of a 52 card deck before it was indistinguishable from a perfect shuffle. This is a lot more than the typical card player shuffles the deck. After 5 shuffles, there are still 4 times too many cards which started out adjacent and never were separated, and some cards are five times more likely to end up in one particular location than another.

Shuffling 10 times is pretty good, but 13-15 is what is required to be completely random.

-- DonDodson

On the other hand, it only takes 8 applications of PerfectShuffle? to put the deck in the original order. It turns out that if you are really good at shuffling, you aren't very good at shuffling.

-- RonJeffries

There was a study published on this back in 1993 or so. (I saw it in the New York Times, probably in the Tuesday ``Science News.'') The study claimed (if I remember correctly) at least 6 shuffles were necessary, and more than 7 didn't increase the randomness.

I don't remember how they measured randomness. (They simulated casino card shuffling machines.) But I do remember there's literature on this! --PaulChisholm

The description of the hand shuffling method

"I would cut the deck at some point near the middle and then interleave the cards, taking one or two cards from one half and then from the other."

leaves open the question of the probability with which the "cut" occurs after the nth card as well as the probability of "taking one card" versus "two cards". Without these data, it is hard to determine how many shuffles it takes to satisfy criterion 1.

"1. Probability that card i ends up in location j. This should be the same for any (i,j)."

Presumably, the shuffler could end up with more than two cards in one of the halves at the point when the other half is exhausted.

Its unclear to me why the second and third criteria were included.

"2. Number of pairs which were adjacent in unshuffled deck and are still adjacent in shuffled deck (this number should be 1 for any size deck)."

"3. Average distance between 2 cards which were adjacent in unshuffled deck. For a well-shuffled 52 card deck, this should be about 20.96."

I'd say that if one satisfied the first criterion, the others are irrelevant. However, I'm sure that most card players would prefer the other criteria to hold sway over the first in the shuffled deck -- preferring to have the shuffled deck bear little resemblance to the deck prior to shuffling.

One *can* say that one cannot achieve the second or third criteria without violating the first criterion. They are inconsistent. One can also say that the parenthetical remark in the second criterion is incorrect. Discounting decks of size 0 and 1, the first size for which it is true is 4.

All told, then I'm not sure which of the criteria is satisfied in shuffling the deck 13-15 times.

All this aside, however, the result makes me feel inadequate when I remember that I usually perform a bridge shuffle in clumps of 3 to 6 cards from each half and only do 4 or 5 shuffles before botching it and spilling cards onto the table. The whole discussion makes me want to attend Shufflers Anonymous until I repent the error of my way and find enlightenment on the Path of the True Shuffle. I don't think I'll play cards for the next few weeks. Respectfully (as much so as I can manage)...

-- ChuckSiska

Imagine a shuffling algorithm whereby the entire deck is rotated by random(52) positions while maintaining relative card order. Although this algorithm satisfies criterion 1) above, the new deck has been shuffled very poorly indeed. So criterion 1) is insufficient to guarantee a "good shuffle".

Criterion 2) and 3) could be generalized to something like:

2. The probability P that the distance from arbitrary card i to arbitrary card j (treating the deck as circular) is N after the shuffle should be the same for all values of N (mod decksize).

3. Random is a real tough concept to test for. Even when you satisfy these conditions. It is still possible that every time card B follows A (P=1/52) then card C always follows B! To do this and be consistent with C follows B P=1/52 then C never follows B unless B follows A. This could be described as a third order effect.

4 There are fourth order effects.(confusing description ommitted)

N There are Nth order effects.

Then there are time high order time series effects.

: Every second time B follows A C is in the half of the deck closest to B, every other time this happens it is in the other half (distance modulo 52)

The list of possible bizarre rules that can be made up that are non random that a deck can conform but appear random is endless.

: Here is another good one. Any shuffling algorithm even Knuths if driven by a pseudo random number generator cannot produce more distinct shuffling patterns than the length of the generator. Thus with a congruential RNG with a 32 bit seed there are only 2^32 possible results from shuffling the deck! This number is much much less than 52! thus the deck will, to GOD, appear very non random.

Most reasonable tests (created by mortals) for randomness will however pass!

Recently the limitations of possibilities of card deck shuffling using a PseudoRandomNumberGenerator have caused considerable controversy in the community that plays online poker for real money.

-- AndyPierce & AlanChristiansen

There's been some mathematical work on this issue (I think it's what's referred to above) by PersiDiaconis. I don't know anything much about it. I think the idea is this: Consider all possible permutations of the cards. Whenever you can get from one permutation to another by doing a shuffle of whatever kind we're considering, join those two permutations by an edge (so we have a directed graph here). Next to each edge, write down the probability that any given shuffle does actually turn one into the other (so we now have a directed graph with weights on the edges). Repeated shuffling corresponds to doing a random walk on this graph, with probabilities given by the edge weights. We want to know how many steps it takes before the position of the random walker is "evenly enough" distributed. This is sort-of determined by the eigenvalues of a certain matrix associated with the graph; the matrix is huge (52!x52!), but because the graph has a lot of structure on it there are ways to simplify the calculations.

That's all a bit high-powered. We can get some idea of what the results are likely to be by much simpler means:

Consider doing "perfect" riffle shuffles, where the only randomness is in which half of the deck provides the odd-numbered cards and which the even-numbered cards. Since each such shuffle provides only 1 bit of entropy, and there are log_2 52! = 225.6ish bits of entropy in a randomly-ordered pack, you'd expect to have to do hundreds of these shuffles to produce a really well shuffled pack.

What if you interleave randomly-chosen 1-or-2-card blocks? Well, then each half of the deck has about 17 blocks, so we get about 34 bits of entropy per shuffle, so it ought to take at least 6.6ish shuffles to randomise the pack. I think this is in line with the conclusions of Diaconis's (much more sophisticated) analysis.

What if we allow the blocks to have wildly different sizes? Well, the number of ways to add up a bunch of positive numbers to get 26 is 2^25, so we get at most 50 bits of entropy from each shuffle, so it will take at least 4.5ish shuffles to randomise. So Diaconis's results, I think, say that this is slightly but not hugely overoptimistic.

--GarethMcCaughan

Ok; it's been a while for me so please bear with. Once upon a time I figured on a way to mimick hand-shuffling in a computer. I'll spare the details since my native language was assembly (stop laughing) and I have forgotten them anyway.

If you use a deck of well oiled cards (or out of the box if you prefer), shuffling them ammounts to:

separating the pile into left and right hands
rejoining the hands
1. take {0, 1, 2, or 3} cards from the left hand and place them on the new pile
2. repeat for the right hand
3. repeat until the deck is exhausted.
repeat three times (Hoyle says that the deck is sufficiently randomized; right)

simple, right? of course, this being assembly, i wanted to use bit-strings (with lots of RCR's and RCL's for the left and right hands) but the same can be applied to byte-sized or word-sized index numbers for objects, or an index array if you must go high-level on me.... whatever your heart desires. Now the problem is deciding how many cards to transfer from hand to pile; this necessitates another bit-string that is twice the length of the original bit-deck, and random at that. So I decided to use the deck in it's original state, just doubled. Call it the 'control'. Taken two bits at a time, '00' means 'move zero cards' and '11' means 'move three cards'; well, you get the idea. Having a control that is twice the length of the bit-deck helps to ensure that you will run out of deck before you run out of control; but if this happens, just append whatever's left on to the end. It happens a lot IRL, so what the heck, right? Anyway. This creates an end result that is unique for every unique bit-string presented to the shuffling algorithym. More or less a hash; but i'm sure that enough brain power could figure out the original state of the bit-deck. So, take the time that the program was run (which in asm is itself a bit-string), repeat it as often as necessary to make it as long as the control, and then XOR it on top of the control. You can even have the user determine when the time is obtained... anyway. I digress.

The thing I don't like about natural shuffling is that, with the three recommended shuffles, you have, at best, two sets of one suit in order. ie; take a brand new pack, look at the top suit (spades), and shuffle three times. Sift through the deck for spades, and you'll likely get

 8,....9,..10,..J,..Q,..K
 ..A,2,..3,...4,..5,..6,.7,
 --- separate lines used to illustrate the pattern: 8A293... etc

and the same holds roughly true for the rest of the suits. IRL I alternate between a regular shuffle and a New Improved Shuffle (!) which consists of taking the right hand out of the middle of the deck, swaping the top and bottom halves of the left hand before sticking them together, and then shuffling. It goes a lot quicker if you can cut a deck with one hand. If anyone wants to do a stats study on the method I'd love to hear about it...

[BelTorak]

I have always known, that the childrens method of shuffling - scattering all cards face down on the table and moving them wildly around - is probably a better method of RandomShuffle?, that the usual few hand shuffles.

-- GunnarZarncke