Web Rarely

Chinese saying: "He who speak with forked tongue, not need chopsticks."

A brief investigation of card shuffling techniques

2024-01-07

Introduction

In playing card games with my daughter, I've come to wonder how I can reshuffle the cards with a minimum of effort, so I decided to do a brief investigation of the qualities of the different shuffling techniques.

Techniques

There are four techniques I looked at: overhand, over-under, pile, and riffle shuffling.

About the visualizations

Each technique, and some combinations of techniques, has an associated visualization. The background of the visualization shows two histograms. The colored histogram shows, for each card in the original deck, where in the new deck it's likely to end up. The dot in each column shows how likely that card is to end up before or after cards that it was before or after in the original deck. If the dot is at the bottom, the card is very likely to still be after any cards that it was originally after, and before any cards that it was originally before. If the dot is at the top, the card is very likely to be before any cards it was originally after, and after any cards it was originally before. If the dot is in the middle, the card is about equally likely to be before or after cards that it was originally before or after. The foreground of the visualization shows a single, archetypical example of the shuffle, chosen to have characteristics similar to the average statistics for the shuffle.

Overhand shuffling (visualize)

In overhand shuffling, you repeatedly strip off small groups of cards from the top of the deck, stacking each group on the next to form the shuffled deck. Typically, you'll get five to ten groups in a shuffle. The top group from the original deck becomes the bottom group of the new deck, while the bottom group from the original deck sits on top of the new deck, but within each group the order is the same as in the original deck. In other words, the order of the groups is reversed but the order within groups is preserved. The technique is functionally equivalent to the Hindu shuffle, but seems a bit more ergonomic.

Because each group contains about five to ten cards whose order relative to each other is not changed, overhand shuffling is not good for breaking up runs of cards. In fact, you need dozens of overhand shuffles before the deck will start to look random, but it's one of the faster shuffles and can be effective when combined with other techniques.

Over-under shuffling (visualize)

Over-under shuffling is a technique I either invented or picked up from somewhere. I don't know if it has a name, but it's somewhat similar to overhand shuffling. You pick up the deck in one hand and drop groups of cards from the top into the other hand on edge, alternating dropping the cards on "top" of the new deck (on one side) and on the "bottom" of the new deck (on the other side). The top group from the original deck becomes the middle of the new deck, the second group sits next to it, above or below, the third group sits next to it on the other side, and so on. The bottom group sits either on the top or bottom of the new deck. Even though dropping the second group on the bottom is equivalent to simply making the first group bigger, and thus it seems intuitively better to always drop it on the top instead to break up the card sequence better, simulations show that it's best to choose at random whether you'll drop the second group on the top or bottom.

Because it's slightly awkward, you'll typically get fewer, larger groups in over-under shuffling than you do in overhand shuffling, resulting in runs being even less broken up, but it outperforms overhand shuffling in other ways, as I'll show later.

Pile shuffling (visualize)

Pile shuffling is what I do when I really want to mix up the deck, such as after a game of Solitaire. I deal the cards into five piles, trying to choose a random pile for each card, and then stack the piles on each other in a random order (visualize) or mush them together (visualize) to create the shuffled deck. Because they're dealt one by one, the cards in each pile are in the reverse order compared to the original deck. The top card of the new deck is a card from near the bottom of the original deck, and vice versa.

Pile shuffling is probably the best simple shuffle you can do, at least in the variant where you stack the piles in a random order. (Mushing the cards together is less effective.) Unfortunately, it's much slower than other techniques, and can be beaten by a combination of simpler, faster shuffles.

Riffle shuffling (visualize)

Riffle shuffling is a common shuffling technique in which the deck is divided into two halves, which are then approximately interleaved. Unless you have great technique and a good deck, the cards won't end up perfectly interleaved. Rather, small groups of cards from either side will be interleaved. Top and bottom cards will end up very near the top and the bottom respectively, while the middle cards will be reordered somewhat. The closer a card is to the middle of the original deck, the more randomly it will be shuffled into the new deck.

Riffle shuffling is an effective technique, but needs to be repeated - canonically, seven times - to really randomize the deck. It also doesn't always work well, mechanically speaking, especially with cards that are too new (or too old?) to riffle nicely. The main problem with riffle shuffling is that it does a poor job of randomizing the top and bottom of the deck; this can be addressed by mixing riffle shuffles with over-under shuffles or sloppy cuts.

Interestingly, a single riffle shuffle of a new deck neatly puts the red cards on top and the black cards on the bottom (visualize).

Cutting the deck (visualize)

Cutting the deck is not a shuffle, but is simply splitting the deck in half, swapping the two piles, and putting them back together. It places the middle cards on the top and bottom, and the top and bottom cards in the middle. It hardly shuffles the deck at all, but is very fast and may combine with other techniques to enhance them. Note, however, that this enhancement effect often relies on the cuts not being perfect! This is discussed more later.

Combinations

No technique is great in and of itself, except pile shuffling, which is slow. Can we combine techniques so that the weaknesses of each technique are countered by the strength of another technique? First we'll need to develop a way to measure how well shuffled a deck is before we can judge which combinations work best.

Quantifying a Shuffle

After shuffling the deck, how can we know it's good? I'm sure there is some accurate and complicated statistical theory about this, but I developed a few metrics of my own which I'll use instead.

Absolute distance

In a perfect shuffle, there should be no correlation between the absolute position of a card in the original deck and the in the shuffled deck. We can take the position of each card in the original deck, counting from the top, and compare it to its position in the shuffled deck. Intuitively, the cards should be, on average, about "half a deck" away from each other. (The actual figure is more like a third of a deck, due to cards on the ends having less freedom of motion than cards in the middle.) We can average the absolute values of the distances for each card to find the mean absolute distance for the whole deck, and compare it to the ideal value.

Histogram

In a perfect shuffle, a card should be equally likely to end up in any place in the deck. We can create a histogram of where each card ends up and see how much it deviates from the ideal uniform distribution.

Order

In a perfect shuffle, any two pairs of cards should have a 50% chance of being in the same order relative to each other in the shuffled deck as they are in the unshuffled deck. We can compute this value for a deck and compare it to the expected value. (If you do no shuffle, 100% of the pairs will be in the same order relative to each other; if you reverse the deck, 0% of the pairs will be in the same order relative to each other. Both cases are 50 percentage points off from the expected 50% value - the largest error possible.)

Relative distance

In a perfect shuffle, most runs of cards (like 2, 3, 4, 5) should be broken up in the shuffled deck, whereas overhand and over-under shuffling tend to keep them together. We can measure this by taking an average of the distance from each card to several of its neighbors in the original deck (weighted by how close together they are), and comparing this to the weighted average distance of those same cards in the sorted deck. (I chose to compare against six neighbors on each side.)

Summary

It would be nice to combine the four measures above into a single number so we can easily rank the techniques. There are a number of ways to do this, most of them completely arbitrary, such as averaging them, averaging their squares or square roots (or some other power), or taking a weighted average. I tried a few summary measures and arbitrarily decided that the histogram is more important than the relative distance, which is more important than absolute distance, which is much more important than overall order in making a shuffle "good", and thus arrived at a weighted average of the four (overall error = (absolute error / 2 + histogram deviance * 2 + order error / 16 + relative error) / 3.5625).

Performance of techniques

Using the measures developed above we can measure and rank the techniques and their combinations. The short answer is that the best quick way of shuffling the cards is some number of riffles or an over-under shuffle followed by some number of riffles. Generally you want at least three shuffles (either three riffles or an over-under and two riffles). The best medium-speed way is to do two over-unders and a pile shuffle (with the stacking variant). This is pretty close to a perfect shuffle. The best slow way is to do three pile shuffles (again with the stacking variant). This is quite nearly perfect. Most combinations of techniques can be interspersed with cuts to improve them - especially sequences of riffle shuffles - but only if the cuts are a bit sloppy, as described later.

Read on for the longer answer.

Basic performance

We'll start with the performance of the individual techniques. Each technique was simulated in the form expected for a typical card handler. For example, overhand and over-under groups were somewhat uneven, cuts were not always in the center, and riffle shuffling worked on small, randomly sized groups rather than assuming a perfect riffle. To help show that the measures are working as intended, I've included "no shuffle", which should have maximal error (near 1.0), and "perfect shuffle", a Fisher-Yates shuffle which should have minimal error (near zero, visualize). Here are the results for the individual techniques. All numeric results are aggregated from 100,048 shuffles. Click the links for each technique or combination to view a visualization.

TechniqueAbsoluteHistogramOrderRelativeOverall
No shuffle1.0001.0001.0001.0001.000
Perfect shuffle0.0000.0000.0000.0000.000
Reverse the cards0.5001.0001.0001.0000.930
Cut the deck0.4930.4890.0150.8640.587
Overhand shuffle0.4890.3210.7550.8530.502
Over-under shuffle0.0120.2470.1400.8030.368
Pile shuffle (stacking)0.1010.0800.1940.2270.126
Pile shuffle (mushing)0.4180.1290.6310.4870.279
Riffle shuffle0.2530.3330.4920.2320.296

As you can see, overhand and over-under shuffling are about the same when it comes to relative distance, but over-under shuffling is significantly better in both ordering and absolute distance. Riffle shuffle, as expected, is much better at breaking up runs of cards and so obtains a lower relative distance. Pile shuffle, at least with the stacking variant which I recommend, beats the others overall. The mushing variant seems inferior.

Combinations

By exhaustively trying combinations of techniques, we can find the combination that best approximates a perfect shuffle. Then, we can look among the good performers to find which one we can execute the fastest. Not surprisingly, the best performer by far is repeated pile shuffles, but that is too slow. Restricting the results to at most one pile shuffle gives the following abbreviated tables, each of which is ordered from best to worst. (Combinations with an overall error greater than a threshold were excluded.)

Before describing the combinations, I'll make a note about mixing cuts into them. In several places, I say that you can mix cuts into combinations - especially between riffles - to improve the quality, but this comes with an important caveat: it only works when the cuts are a bit sloppy, and the deck is not always cut in the exact middle. Consider that a riffle shuffle consists of cutting the deck in half and riffling the halves back together. If you do a cut before the riffle, and your cuts in both cases are perfect, then all you've done is swap the two halves used in the riffle, i.e. swap the hands in which the two halves are held, which is no improvement at all! So, when cutting the deck, including when doing the cut at the start of a riffle shuffle, don't try to divide the deck exactly in half. Just choose a point roughly near the center. This random factor added to the cut is what makes it work to improve our shuffles.

Legend: C = cut, OH = overhand, OU = over-under, P = pile (stacking), R = riffle

Combining up to two, excluding pile shuffles

It seems the best combination of up to two techniques, excluding pile shuffles, is two riffles (visualize), but an over-under and a riffle (visualize) beats it in some ways (but is worse in others). You can do a cut before the two riffles (C + R + R, visualize) to produce a combination that beats both of them, with only a small loss of speed, assuming all your cuts are slightly sloppy. Note that none of these combinations are all that good, and I can't really recommend any of them. Pile shuffles are included in the table to show how they compare to the combinations.

TechniqueAbsoluteHistogramOrderRelativeOverall
R + R0.1240.1190.2410.0810.111
OU + R0.1270.0720.1170.2210.123
Pile shuffle (stacking)0.1010.0800.1940.2270.126
OH + R0.2400.1110.2770.2010.157
R + OU0.0350.1720.0690.2020.160
OU + OU0.0070.0840.0870.5490.204
C + R0.1440.2220.3540.1900.204
R + OH0.2400.2220.3720.2160.225
R + C0.1210.2820.0050.1910.229
OU + OH0.0090.1210.0200.5950.237
Pile shuffle (mushing)0.4180.1290.6310.4870.279
C + OU0.0060.2050.1220.6250.294
Riffle shuffle0.2530.3330.4920.2320.296
...     
Over-under shuffle0.0120.2470.1400.8030.368
Overhand shuffle0.4890.3210.7550.8530.502

Combining up to three, excluding pile shuffles

It seems the best combination of up to three techniques, excluding pile shuffles, may be an over-under shuffle followed by two riffles (visualize), but the over-under shuffle could be replaced by a cut (visualize) to make it faster with a moderate loss of quality, or replaced by another riffle shuffle (visualize) to produce a combination that beats it in relative position error. Alternatively, you can do cuts between the riffles (e.g. R + C + R + C + R, visualize) to significantly improve the quality without much loss of speed, again assuming that all your cuts are a bit sloppy.

TechniqueAbsoluteHistogramOrderRelativeOverall
OU + R + R0.0000.0070.0810.0980.033
R + R + R0.0600.0170.1180.0560.036
OH + R + R0.1170.0140.0830.0840.049
R + OU + R0.0030.0480.0580.0770.050
C + R + R0.0340.0460.1280.0660.051
OU + OH + R0.0310.0180.0330.1710.063
R + R + OU0.0040.0720.0350.0820.064
R + OH + R0.1140.0480.1350.0730.066
OU + R + OU0.0040.0340.0530.1630.067
R + C + R0.0710.0820.1730.0650.077
R + OU + OU0.0010.0630.0430.1510.079
OU + R + OH0.0660.0480.0230.1680.084
R + R + C0.0590.1060.0000.0660.086
OH + OU + R0.0660.0450.0240.1900.088
C + OH + R0.0410.0790.0280.1430.090
OH + R + OU0.0040.0740.0310.1770.093
R + R + OH0.1170.0900.1810.0850.094
R + OU + OH0.0040.0930.0100.1660.099
OU + OU + OH0.0040.0200.0370.3440.109
OU + R + C0.0990.0650.1070.2090.111
OU + C + R0.1230.0570.1150.2140.112
OH + C + R0.1430.0760.1560.1650.112
OH + OH + R0.2310.0540.3570.1830.121
C + OU + R0.1100.0620.0910.2480.121
OH + R + C0.1210.0980.1920.1670.122
C + R + OU0.0310.1270.0620.1620.122
OU + OU + OU0.0020.0120.0680.4150.125
Pile shuffle (stacking)0.1010.0800.1940.2270.126
R + C + OU0.0240.1460.0610.1530.130
R + OH + OU0.0140.1400.0090.1910.134
OH + R + OH0.2310.0900.3350.1860.141
R + OU + C0.0310.1480.0610.1990.144
OU + OH + OU0.0060.0520.0490.4230.150
...     
Pile shuffle (mushing)0.4180.1290.6310.4870.279
Riffle shuffle0.2530.3330.4920.2320.296
Over-under shuffle0.0120.2470.1400.8030.368
Overhand shuffle0.4890.3210.7550.8530.502

Combining up to three, including up to one pile shuffle

The best technique with a single pile shuffle is clearly two over-unders and a pile shuffle (visualize).

TechniqueAbsoluteHistogramOrderRelativeOverall
OU + OU + P0.0000.0040.0120.0060.004
R + P + OU0.0030.0060.0340.0410.016
OU + R + P0.0010.0140.0190.0300.017
R + P + C0.0040.0150.0220.0300.018
R + R + P0.0240.0250.0450.0030.019
R + OU + P0.0010.0240.0100.0210.020
R + P + R0.0440.0090.0840.0350.022
R + P + OH0.0440.0090.0300.0400.023
OH + R + P0.0460.0240.0580.0240.027
C + OU + P0.0000.0270.0190.0590.032
OU + R + R0.0010.0060.0810.0980.033
R + R + R0.0600.0170.1180.0560.036
OU + OH + P0.0020.0220.0010.0970.040
C + R + P0.0290.0450.0660.0340.040
R + C + P0.0240.0520.0050.0300.041
R + OH + P0.0480.0460.0770.0370.045
OU + P + R0.0010.0040.0230.1550.046
OU + P + C0.0000.0080.0190.1550.048
P + R + OU0.0040.0040.0480.1600.049
OH + R + R0.1170.0140.0820.0840.049
OU + P + OU0.0080.0010.0250.1690.050
OH + P + C0.0100.0150.0140.1420.050
R + OU + R0.0030.0480.0580.0770.050
OU + P + OH0.0010.0030.0220.1720.050
C + R + R0.0350.0450.1280.0660.051
OH + OU + P0.0020.0280.0010.1300.052
P + R + OH0.0900.0060.0880.1290.054
P + C + R0.0170.0010.0780.1770.054
P + OU + R0.0220.0010.0310.1800.055
P + R + C0.0030.0060.0550.1810.055
P + C + OU0.0010.0000.0560.1950.056
OU + C + P0.0000.0290.0190.1470.058
P + C + C0.0260.0060.0920.1770.058
P + C + OH0.0090.0010.0620.1980.058
P + OU + OH0.0120.0030.0240.1970.059
P + OH + OU0.0020.0040.0440.2020.060
OH + P + OU0.0110.0060.0390.1940.060
P + OU + OU0.0020.0020.0500.2070.061
P + R + R0.0880.0060.1700.1520.061
C + P + R0.0410.0100.0030.1780.061
C + P + OU0.0060.0060.0510.2010.062
C + P + C0.0090.0180.0700.1750.062
OU + OH + R0.0310.0180.0340.1710.063
R + R + OU0.0030.0720.0340.0820.064
R + OH + R0.1140.0480.1350.0730.066
P + OH + R0.0780.0040.0380.1850.066
OU + R + OU0.0030.0350.0520.1640.067
OH + P + R0.0900.0100.1370.1710.069
P + OU + C0.0260.0050.0230.2240.070
P + OH + OH0.0950.0050.1470.1820.070
P + OH + C0.0200.0070.0730.2220.070
C + OH + P0.0500.0540.0410.1220.072
C + P + OH0.0490.0110.1130.2060.073
OH + P + OH0.0950.0110.0870.1900.074
OH + C + P0.0500.0510.0410.1430.076
R + C + R0.0710.0820.1730.0640.077
R + OU + OU0.0000.0630.0430.1510.078
OU + R + OH0.0660.0490.0230.1680.084
R + R + C0.0590.1050.0000.0660.086
OH + OU + R0.0660.0450.0230.1910.089
C + OH + R0.0410.0790.0280.1420.090
OH + OH + P0.0940.0490.1560.1700.091
OH + R + OU0.0050.0740.0310.1770.093
R + R + OH0.1170.0900.1810.0860.094
R + OU + OH0.0050.0930.0100.1660.099
C + C + P0.0790.0660.1640.2070.109
OU + OU + OH0.0040.0200.0370.3450.109
OU + R + C0.0990.0650.1070.2090.111
OU + C + R0.1240.0570.1160.2140.112
OH + C + R0.1440.0760.1570.1660.112
OH + OH + R0.2320.0540.3570.1840.121
C + OU + R0.1110.0620.0910.2480.121
C + R + OU0.0310.1270.0620.1620.122
OH + R + C0.1210.0980.1920.1670.122
OU + OU + OU0.0030.0120.0670.4150.125
Pile shuffle (stacking)0.1010.0800.1940.2270.126
R + C + OU0.0250.1460.0600.1540.130
R + OH + OU0.0150.1400.0100.1910.134
OH + R + OH0.2310.0890.3350.1860.141
R + OU + C0.0300.1480.0600.1990.144
OU + OH + OU0.0060.0520.0490.4230.150
...     
Pile shuffle (mushing)0.4180.1290.6310.4870.279
Riffle shuffle0.2530.3330.4920.2320.296
Over-under shuffle0.0120.2470.1400.8030.368
Overhand shuffle0.4890.3210.7550.8530.502

Repetitions

Also of some interest is how well each technique improves the shuffle if repeated. As you can see, overhand improves very slowly, while riffle approximately halves the error on each iteration and pile shuffle reduces it by about 80%. (This 80% figure is probably directly related to the fact that I use 5 piles. 1-1/5 = 80%.) Other observations: overhand seems to alternate several properties with each iteration; over-under does the same but mixes much more rapidly, although many runs remain unbroken; pile shuffling rapidly approaches perfection; and riffle shuffling quickly mixes the middle of the deck while the top and bottom are much slower to mix.

TechniqueAbsoluteHistogramOrderRelativeOverall
Overhand x10.4890.3220.7550.8530.502
Overhand x20.7300.2290.8060.7600.458
Overhand x30.4680.1850.6660.6850.374
Overhand x40.6340.1570.6960.6220.364
Overhand x50.4470.1360.6010.5690.309
Overhand x60.5650.1200.6170.5220.304
Overhand x70.4250.1070.5480.4800.264
Over-under x10.0120.2470.1400.8030.368
Over-under x20.0070.0840.0870.5490.204
Over-under x30.0040.0120.0660.4150.125
Over-under x40.0000.0010.0520.3460.098
Over-under x50.0000.0000.0400.2880.082
Over-under x60.0000.0000.0320.2410.068
Over-under x70.0000.0000.0270.2050.058
Pile (stacking) x10.1010.0800.1940.2270.126
Pile (stacking) x20.0200.0030.0340.0450.017
Pile (stacking) x30.0040.0000.0050.0010.001
Pile (stacking) x40.0000.0000.0010.0010.000
Pile (stacking) x50.0000.0000.0000.0000.000
Riffle x10.2540.3320.4930.2320.296
Riffle x20.1240.1190.2410.0810.111
Riffle x30.0610.0170.1190.0560.036
Riffle x40.0290.0030.0580.0460.019
Riffle x50.0140.0010.0310.0260.010
Riffle x60.0070.0000.0170.0150.006
Riffle x70.0030.0000.0090.0090.003
Riffle x80.0020.0000.0050.0050.002

Comments

No comments yet.

Add a comment

Note: The information you enter (including your name and email address) will be displayed publicly.




Line breaks are converted to <br>'s, and all HTML tags except b, u, i, tt, and pre are filtered out.