Because math isn't always boring

## Month: July, 2012

### Randomness, part 3

First off, I’d like to apologize for not posting this week. This Wednesday, which is when I usually post these, happened to be my thirtieth birthday, and I was out of town. So this week’s post is a bit delayed. I’ll try to get back on schedule for next week.

If you read last week’s article, you may despair that you can ever truly randomize your deck. Can your deck ever truly be random, if every shuffle is deterministic?

Well, yes, and no. The answer veers a bit out of mathematics and into philosophy (and a bit of biology).

When we talk about randomization, we might be content with a definition of “the deck is sufficiently random if neither player can be reasonably expected to know the (absolute or relative) location of any card or cards.” In other words, if the human brain isn’t capable of tracking the cards’ positions as you shuffle, that’s good enough for us. But what are the limits of the human brain?

Since I’m not a neurobiologist (shocking, I know), I can’t say for sure, but I’d say that, for a large percentage of the population, a pile shuffle would already meet this definition. For professional players, even a single riffle shuffle might be enough to confound their tracking skills, or at the most two. Then there are the Vegas card counter types – and, before you say anything, they do exist, at every level of play – who can track cards through an arbitrary number of ideal riffle shuffles without much effort. So clearly we can’t rely on the fallibility of the human brain to consider a deck shuffled.

luckily, there is another answer. I mentioned the riffle shuffle above. In an ideal riffle shuffle, we split the deck in half and into two piles (using a 12 card deck as an example)
``` 1 7 2 8 3 9 4 10 5 11 6 12 ```

Then we alternate the cards from one pile and then the other, ending up with the order

`1 7 2 8 3 9 4 10 5 11 6 12`

And the corresponding permutation

`(2 7 4 8 10 11 6 9 5 3)`

1 and 12 are mapped to themselves, so we don’t need to mention the, in the permutation. (already we should be suspicious of this form of shuffling)

Of course, you might be asking yourself, how is this any more random than a pile shuffle? Well… It’s not, honestly. But here we save ourselves through human fallibility.

The average magic player won’t be able to cut a sixty card deck exactly in the middle. When letting the cards fall, allowing one card to alternate with the other exactly over sixty cards is incredibly hard. When we riffle shuffle, we are actually choose a random riffle-ish shuffle from the hundreds of thousands of possible permutations over sixty cards. Granted, most riffle shuffles will still have the problem of keeping the top and the bottom cards in the same place, but that’s why we cut after shuffling, to remove even that regularity. And, last but not least, and this is important. when your opponent presents his or her deck to you, you should always not just cut it, but shuffle it. that way, even if your opponent is a Vegas card shark who has mastered the art of the ideal riffle shuffle (more common than you might think), you can still be assured he or she will have a sufficiently random deck, because you’ll be sure to follow what you’ve learned here to shuffle the deck in a way that even your opponent can’t know the location of any of the cards.

Of course, these cards will still not actually random. They are deterministically distributed in your deck in a non-random way. We just don’t know what the order is until we draw the cards themselves. We could link the cards to a random number generator, bringing true quantum randomness into play, but, as I defined it above, it’s enough for us as magic players to just not know where the cards are, they needn’t be truly random. Once the deck is properly shuffled, we can treat it as though it were truly randomized for the rest of these articles.

Exercises

• What is the permutation for an ideal riffle shuffle over a sixty card deck?
• After how many ideal riffle shuffles will the deck be in the same order as it started?
• What other forms of shuffling do you know? How would you describe their potential for randomness? You don’t have to do so mathematically, just describe it.
• ### Shuffling, part 3

This week we’re tackling a mathematical concept that is going to be important as we continue to look at how Magic can be broken down mathematically: the group.

A group can be anything really – a set of objects, a vector space, a geometrical construct, a system of numbers – as long as it has a set of elements and an operation that takes two of those elements and uses them to create a third (also known as a binary relation). We usually use the multiplication symbol * to signify the relation.

Furthermore, the relation has to follow the following three rules.
1) the relation has to be associative, or a*(b*c) = (a*b)*c
2) there exists a neutral element, which we call 1, so that 1*a=a=a*1, and
3) every element has an inverse element, or there is always a b so that a*b=1=b*a

Let’s look at shuffling. Shuffling is associative, in that if we combine two shuffles into a single operation, it doesn’t matter whether we combine the first two or the second two. There’s a neutral element, where we just don’t shuffle (the equivalent of tapping on the top of the deck), and every shuffle has an inverse, as you can well imagine (you just do the shuffle backwards).

So shuffling is a group,which is very interesting, for a few reasons. For one, let’s take the example of pile shuffling from above. If you do the exact same shuffle enough times, you will eventually get back to your starting point. The interesting thing is, this is true no matter what kind of shuffle you use. If you don’t change up your shuffling, you will eventually end up at your starting point.

Every element of a group has what’s called an order, which is the number n, so that if you take the element to the power of n, you get 1. But, you might think, what if there is no such n? What if the inverse to x isn’t a power of x at all?

Well, let’s say it’s not. Let’s call the inverse of x “y”, and say that, no matter how often you multiply x with itself, you never get y (because otherwise x^(n-1)=y).

So what do you get for the powers of x? Well, you can’t get y, we already said that. And you can’t get 1, that’s kind of the point. But there are only a finite number of different shuffles possible. A very large number, granted, but finite. If ever two powers of x are the same, say x^a=x^b, then if we decide by the smaller of the two (say a) we have x^(a-a)=x^(b-a). Since x^0=1, we’d have 1=x^(b-a), which we said isn’t the case. So no two powers of x can be the same.

Ah, but there are only finite many different elements that powers of x can be, eventually they have to be two of the same. So therefore, there must be an n, so that x^n=1. (more specifically, the order of x is the smallest such number)

So what does this mean? Well, if you perform the exact same action enough times in a row, you’ll end up where you started from. So, performing the exact same action – no matter how random it may seem – is actually not random at all.

So does this mean that you can never randomize your deck? Is it actually impossible to follow the rules? Well, no, but stay tuned to find out why.

Excises: 1)how many elements does the group S of possible shuffles of a deck of sixty cards have? Start with smaller deck sizes
2) what’s the order of the eight-pile pile shuffle on a deck of sixty cards?

### Randomness, Part 2

Hello again

Before I begin, let me clarify something from last week, regarding how you multiply two permutations.

A permutation like (14235) means that 1 gets mapped to 4, 4 gets mapped to  2, etc. If you perform the same permutation twice, then in the first step 1 will get mapped to 4, and 4 will get mapped to 2, so the resulting permutation will map 1 to 2, so we start by writing “(12”. Next, we’ll see w hat  2 gets mapped to. 2 in the first permutation gets mapped to 3, and 3 gets mapped to 5, so we continue the permutation “(125”. Then we see what 5 gets mapped to, etc. I hope that makes things a bit more clear. If ever a number gets “left out”, we start another set of parentheses for that number and see what it gets mapped to. If it gets mapped to itself, we just leave it out.

Now, on to more randomness. Last time I said that the chances of drawing a card in your opening hand that you are playing four of is 4/60+4/60+..+4/60 = 7/15. But that’s not entirely true, because we’re assuming that each of the card draws has the same probability of drawing that card. But what happens if your first four draws are that card? Then suddenly the probability that the fifth card is that card drops to zero, so clearly something can’t be quite right.

The reason for this is that the probabilities for drawing a given card in each of the first seven draws are not independent, so we need to think about how we can come up with the actual number. There is a tool that we use quite often in probability theory, namely the fact that sometimes it’s easier to look at the probability that something doesn’t happen than it is too look at how likely something  is to happen.

Let’s look at how likely it is that, given seven card draws, how likely is it that we will  not draw at least one of the card we are looking for. The first card we draw has a 56/60 chance of not being that card. Now, if we draw one of the cards with the first draw, we already know that the “event” we are looking at doesn’t match the criteria, so we can assume the first card draw is not the card we want. Which means that there are 59 cards left, 55 of which are not the card. So we now multiply the probability that the first card we draw isn’t the card with the probability that the second card isn’t it, so we have

P’=56/60*55/59*…

We go on like this for the first seven cards, ending up with

P’=56/60*55/59*54/58*53/57*52/56*51/55*50/54 ≈ 0.6 =60%

To come up with the probability we do draw it, we subtract from one (or 100%) the probability that we won’t draw it, so

P=1-P’ ≈ 0.4 = 40%

So, in your first hand you have about a 40%, or two in five, chance of drawing any given one of your four-ofs.

Looking at the complementary event can come in very handy when dealing with a complex situation. If we wanted to look at the probability of drawing at least one copy, we’d have to add the probability of drawing one copy, plus the probability of drawing two copies, and so on.

That will do it for today. I forgot to add exercises last week, so I’ll make sure to add some this time.

Next week we will talk some more about shuffling. Noticing a pattern yet?

Exercises:

1. What is the probability of drawing all four copies of a card in your first hand?

2How does the probability change if you are on the draw.

3Some card games have a minimum deck size of forty, but only allow three copies of a card. Are you more or less likely to draw a three-of in your opening hand if you follow those construction rules?

### Shuffling, Part 2

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.

### Update

Due to the holiday, today’s post will go up late, possibly tomorrow but no later than that.

Have a happy fourth of July, whether you celebrate it or not!

Tosus