Shuffling, part 3

by MTGViolet

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?