(Metagame Archive) Strength in Numbers, Shuffling, Part 2: The Problem with Rising Sequences

Olav Rokne

Several people have asked me why five riffle shuffles aren’t enough to randomize a deck. To explain why this is so, we’ll need to look at rising sequences. A rising sequence is an increasing sequential ordering of cards that appears in a deck (with other cards possibly interspersed) as you run through the cards from top to bottom.

Confusing, eh? Here’s an example that might help clear things up. Imagine that you’ve numbered the cards in your 60-card Vs. deck by assigning the value of 1 to the first card and descending sequentially to 60 for the bottom card. Before you shuffle, there is one rising sequence that goes 1, 2, 3, 4, 5, and so on up to 60.

After one riffle shuffle, you will find a sequence that resembles something like 31, 1, 32, 2, 33, 3, 34, 4, 35, 5, and so on. In this order, there are now two separate rising sequences: one of the first 30 cards, and the other of the second 30 cards. If you follow this with a second riffle shuffle, you will have at most four rising sequences, since each of the rising sequences created by the first shuffle has a chance of being split in the second shuffle.

The number of maximum possible rising sequences increases exponentially as you riffle shuffle and potentially split each existing rising sequence. After three riffle shuffles, you will have a maximum of eight rising sequences, and after four, you will have a maximum of sixteen.

So, what does this mean for your average Vs. deck? Until the sixth riffle shuffle is done, not only are some sequences of cards more likely than others, but some shuffling outcomes are entirely impossible.

The best example of an impossible shuffling outcome would be to find the deck in the reverse order from how it started out (with card number 60 on top and the remaining cards running sequentially down to card 1 at the bottom). This order of cards requires 60 rising sequences, and since the maximum number of possible rising sequences after five shuffles is 32, that outcome is not possible until the sixth shuffle. Even after the sixth shuffle, inverting the order of the cards is still of a particularly low probability, which is why a seventh shuffle is important.

After five riffle shuffles, you will be left with a maximum of 32 rising sequences. Since each of the five shuffles after the first one is only 50% likely to split an existing rising sequence, you end up with a 6% chance of having 32 rising sequences and a 6% chance of having only 2 rising sequences. There’s a 19% chance of 4 or 16 rising sequences. What is most likely to occur is 8 rising sequences.

The average length of a rising sequence is 7.5 cards, and the distance between cards within a sequence will average 8 places.

Now, what does this mean in practical game terms? When you start a large tournament or after your deck gets checked, your cards will be in order with all copies of a particular card together.

Since it’s an easy deck to understand, we’ll use an Avengers deck for this example. The numbers in parentheses represent the order of the cards in the rising sequence.

Characters

4 Black Panther (1-4)

4 Rick Jones (5-8)

4 Natasha Romanoff ◊ Black Widow, Super Spy (9-12)

4 Quicksilver, Mutant Avenger (13-16)

3 Beast, Furry Blue Scientist (17-19)

4 Dane Whitman ◊ Black Knight (20-23)

2 Hercules (24-25)

4 Wonder Man (26-29)

4 Carol Danvers ◊ Warbird (30-33)

4 Hawkeye, Clinton Barton (34-37)

4 She-Hulk, Gamma Bombshell (38-41)

Plot Twists

3 Flying Kick (42-44)

3 Savage Beatdown (45-47)

2 System Failure (48-49)

3 Heroes in Reserve (50-52)

3 Mega-Blast (53-55)

3 Call Down the Lightning (56-58)

Locations

2 Avengers Mansion (59-60)

You have riffle shuffled your deck five times, and an opponent has cut it. You draw your opening hand, mulligan, and then draw your first two cards. You have now seen the top ten cards of your deck. This is enough to see either an entire rising sequence if that occurs, or to see pairs of cards within most sequences of your deck.

Let’s say you draw the following sequence in your first ten cards, with their possible starting positions in parentheses:

Beast (17-19)

Quicksilver (13-16)

Rick Jones (5-8)

She-Hulk (38-41)

Carol Danvers (30-33)

Hercules (24-25)

Hawkeye (34-37)

Dane Whitman (20-23)

Quicksilver (13-16)

Savage Beatdown (45-47)

From these ten cards, there are a number of things you can guess about what cards are likely to come up in your subsequent draws. First off, you have (as will be the case in half of all such shuffles) eight rising sequences. In this hand, the number of cards in each sequence is likely to be seven or eight.

You can expect not to draw any copies of Hercules or Wonder Man, because in the original order of the cards, they appear more than four cards after the copies of Quicksilver and Beast. The sequences they are likely to appear in (the sequence of Beast to Dane Whitman and the sequence of Quicksilver to Quicksilver) have just started rising sequences that are four cards away from your 6- and 7-drops. Since there are 7 cards between cards within a sequence, there will be another 24 cards in the deck until you start drawing these key cards.

Keep an eye out for pairs of the same card within your first ten cards, and see if you can figure out the interval at which cards within a rising sequence seem to appear. If you are able to do this, then try to make predictions as to what cards come next within the sequence, and see if those predictions bear out.

What is particularly interesting to note is that the predictability of decks has a sharp drop-off at seven shuffles. In other words, a deck does not become random gradually, but rather in one fell swoop. The ability to figure out the pattern in a deck suddenly vanishes at seven shuffles; at seven shuffles, every card has an equal chance of being in any particular place in the deck, and even if you can look at the top 58 cards and undergo massive computations, it is impossible to predict the order of the last 2. It’s a drop-off of predictability that is frankly fascinating.

There are several really pleasant advantages to having such a perfectly shuffled deck. First off, nothing your opponent can do (short of looking at the cards face up) can change the randomness. Pile shuffles will not undo the riffle shuffles and riffle shuffles will not undo the pile shuffles.

Decks are often built with probability-based predictions in mind, which is to say that since most people want to draw a 7-drop by the seventh turn, a decklist will include enough copies and tutors to make drawing one or two a likely eventuality, but not so many that hands are flooded with such cards. Due to the mathematical miracle of rising sequences, an insufficiently shuffled deck is likely to lead to a dearth or a glut of them, as evidenced in the example.

As a side note, while researching shuffling, I found an interesting bit of trivia—a coin toss is not entirely random, either. Apparently, a magician-turned-mathematician named Persi Diaconis and some bright boys at MIT have proven that because the leverage a thumb exerts on a coin depends on how far along the nail it is, a coin is more likely to land on the side it started out on. This happens to the degree that, both in lab experiments and in mathematical modeling, 51% of coins land with the same side up that had been up when it was sitting on the coin-flipper’s thumb.

This isn’t a large enough bias for the casual observer to notice unless he or she flips a coin 10,000 times, but all I know is that I’ll be using a set of dice to determine priority at my next PCQ.

— Olav “Even Shuffles His Feet” Rokne

Questions about shuffling? Email me at olavrokne(at)gmail.com.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: