Shuffling, Part 2

by MTGViolet

Hello, hope you all had a good fourth!

Today we’re going to talk a bit more about shuffling, including bringing up the dreaded A-word: Algebra!

But don’t worry, we won’t be solving for x here, this is a more general use of the term, but I’ll get to that in a bit.

Okay, so we’ve determined that pile shuffling isn’t  really shuffling but just a clever way to waste time, now lets look at what exactly is going on.

One thing we mathematicians like to do is provide notation that can be universally used. For instance, if we look at shuffling we’ll want to give a good way of describing what changes between the original state of the cards and the state after shuffling. I’ll illustrate this based on the example of pile shuffling.

Say you have a deck of sixteen cards arranged in such a way that you have one card of each converted mana cost from one to sixteen. You arrange them neatly in order with the Llanowar Elves on the top (or Ancestral Recall or what have you) and perform an 8-pile pile shuffle.  Your deck starts out like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

And ends like this:

9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8

What happens if we repeat this shuffle? The result is

13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4

The interesting thing is, if you look very carefully, you’ll see an interesting pattern emerge. Let’s follow a certain card, say the card with the CMC of 5. in the first shuffle, the card with the 5 will get rearranged to be in the position 11, or

5->11

In the next shuffle, the card in position 11, which used to hold your Darksteel Colossus (or what have you) and got mapped to position 14, follows the same path your Tattered Drake does in the second shuffle, so in other words

11->14

So we have, over the course of two shuffles

5->11->14

If we imagine both these actions as one shuffle action, a combined pile shuffle so to speak, we can cut out the middle step, and write it as

5->14

If we write down these maps for all the cards, we will end up with the exact order we wrote above, which we will write as

1 2 3 4   5   6 7  8   9 10 11 12 13 14 15 16
13 9 5 1 14 10 6 2 15 11   7   3 16 12    8   4

We call this a permutation. A permutation is any function, or map, that changes the order of a set but not its contents. We will usually write permutations in the manner I did above, in two rows, with the number being mapped from above, and the number being mapped to below. But there is another, simpler way.

Let’s start with one pile shuffle. As a reminder, the map looks like this:

1 2   3 4   5  6  7  8   9 10 11 12 13 14 15 16
9 1 10 2 11 3 12 4 13    5 14   6 15   7 16   8

Take the card in the position 1. it gets mapped to the slot 9:

1->9

What now happens to the card in slot 9? It gets mapped to the position 13

9->13

And in 13? It gets mapped to slot 15.

13->15

If we continue this, we get a sort of chain that looks like this:

1->9->13->15->16->8->4->2->1

and we eventually get back to where we started. We will go ahead and wrap these in parentheses, like so:

(1 9 13 15 16 8 4 2)

Disregarding the double 1. Now, if we want to know what happens to any of these cards, we just go on to the next one down the line and we have our answer. But this doesn’t account for all the cards, so we go through the rest of them until we have accounted for all our cards. We’ll go ahead and just write them one after the other:

(1 9 13 15 16 8 4 2) (3 10 5 11 14 7 12 6)

Those two sets of numbers are called cycles, because if you keep doing the shuffle often enough you cycle back to where you were. And no, you don’t get to draw a card if you discard it. As we have seen before, if you shuffle your deck 8 times using the pile shuffle, you will get back exactly to where you started from. Which is why it’s not actually shuffling.

Now, for the two pile shuffles. We can easily do the same procedure as before, following each card through, but there is an easier way. What we’re going to do is multiply the two permutation or, rather, the permutation with itself. The way this works is we sort of follow what happens to our numbers as they pass through the permutations. So, 1->9->13, so we start with (1 13 … then we follow what happens to 13->15->16, so we write (1 13 16… and so on, until we end up with:

(1 9 13 15 16 8 4 2) (3 10 5 11 14 7 12 6) * (1 9 13 15 16 8 4 2) (3 10 5 11 14 7 12 6)
=(1 13 16 4) (2 9 15 8) (3 5 14 12) (6 10 11 7)

Note that we tend to sort these so that the lowest number is the first in a cycle, and then sort those in order. This permutation has four cycles of length 4, which means that after 4 of these shuffles (or eight single pile shuffles), we end up with the first order.

These permutations form a very interesting structure in mathematics called a group, which we will explore in a further article. Group theory is an interesting subset of Algebra, which is where that particular sticky subject was lurking in this article the whole time.

Next week, we’ll get random again.

Advertisements