How to Randomize a Cube
For almost a decade now, I’ve hosted a weekly-ish cube draft. For those who aren’t in the know, a “cube” is a collection of hundreds of curated Magic: the Gathering cards that are shuffled up, dealt into 15-card “booster packs”, and drafted into decks that are played against each other.
Cube drafting with my friends is hands-down the most fun I’ve ever had playing Magic, but it poses a logistical challenge: before each draft, all the cards in the entire cube must be randomized. Most cube owners seem to use the same technique for this: they put the cube into a bunch of face-down piles of 40 or so cards apiece, and repeatedly shuffle two piles together and split them apart. While this usually injects enough randomness to avoid entire packs of the same color, the haphazard nature of trying to ensure that each little pile has had enough opportunity to cross-pollinate with each other pile provides neither a lot of randomness nor a clear signal of when shuffling is complete and the cube is fully random.
To address these problems, I came up with my own technique that meets both of these criteria. While it doesn’t fully randomize the cube in the sense that every possible permutation is equally likely, it’s quick to execute and guarantees that each individual card’s final position is random. I provide a proof of this guarantee after I describe the technique.
The Technique
This process can randomize an extremely large set of cards (up to about 10,000), and can in principle be extended to randomize even more than that. It begins by pile-stacking the entire cube:
- Choose a number p of piles such that, once the cube is divided into p piles, each one will be easy to shuffle by hand. For my 540 card cube, I usually use 8 piles. (It probably goes without saying, but make sure p is also small enough that each pile ends up with more than p cards.)
- Cycle through the piles putting one card from the top of the cube into each one. Each time all the piles have the same number of cards, put the next card into the first pile again and keep going. Do this until you’re out of cards in the cube.
- You’ll end up with p piles each with the same number of cards (possibly minus 1 if the number of cards in your cube isn’t divisible by p).
(Note that what I call “pile-stacking” is more commonly referred to as “pile-shuffling”, but this is a misnomer: it doesn’t actually create any randomness, so it’s not a true shuffle.)
Once you have your piles, shuffle each one by hand. Once each pile is fully randomized, return it to your cube’s box along with all the rest of the shuffled piles. Once you’ve shuffled every pile, the box will once again contain the entire cube.
Now repeat this process: pile-stack the cube again, shuffle the piles, and return them to the box. Finally, pile-stack the cube one more time. This final pile-stack doesn’t actually add randomness, but it helps distribute the randomness from the second shuffle so that any remaining patterns are spread across booster packs rather than being evident within a single pack.
If you want, you can use the final pile-stack to create the booster packs that you use to draft, or you can simply put the piles back in the cube box afterwards safe in the knowledge that the cube is now random enough to deal out packs as soon as the need arises.
This technique has a couple added bonuses:
- You can pile-stack the cards face-up the first two times without giving yourself any real insight into which cards will end up in which packs. This gives you an opportunity to catch upside-down cards or swap in cards from the latest set.
- Pile-stacking provides a convenient checksum to verify that your cube has the correct number of cards. For example, if I pile-stack my 540-card cube into 8 piles, the last card I place will always go in the fourth pile. If it doesn’t, I know something’s wrong.
The Proof
Thanks to John Philpott for pointing out that my argument that this technique fully randomized the cube was flawed!
This technique doesn’t fully randomize the cube — if we define C as the total number of cards in the cube, some of the C! possible orderings of the cube can’t be generated by this technique and others will be generated multiple times. However, it’s random enough for cube drafting purposes. In particular, it guarantees that each card’s final position is random. That is to say, for any given card in the cube it’s equally likely that that card will end up at any position after my technique is applied.
To prove this property, we just need to assume that shuffling a pile of size C/p fully randomizes that pile. After the first pile-stack, choose a card A in the first pile without loss of generality. When A’s pile is shuffled and returned to the cube box, A’s position mod p in the cube becomes random. Thus in the next pile-stack, A ends up in a random pile, since its pile depends entirely on its position mod p within the cube box.
After A’s new pile is shuffled, its position within that pile is random as well. Thus when it’s returned to the cube box, it’s equally likely to be at any position within the entire cube, since it’s equally likely to be in any C/p-card partition and equally likely to be in any position within its partition. The next pile-stack doesn’t change this randomness, since it can’t add order to an already random position.
Not Fully Random
What my technique doesn’t guarantee is that there won’t be patterns across multiple cards in the cube. For example, suppose the first pile-stack puts all the blue cards in the cube in a single pile. The first shuffle merely randomizes the order of the blue cards within the stack, and the second pile-stack evenly distributes blue cards among all p piles.
When you do the second shuffle, the blue cards are randomly distributed within each pile, but there are still exactly C/p² blue cards in each pile, which isn’t truly random. The final pile-stack can’t add randomness so it doesn’t change this fact, although it does distribute the cards so that they make the way these patterns intersect with booster packs essentially impossible to predict.
If you want, you can use this lack of randomness to your advantage. Real draft boosters aren’t fully random themselves: they have a degree of color balancing to make sure that drafts aren’t completely lopsided. If you intentionally sort your cube by color instead of doing the initial pile-stack, and omit the final pile-stack, then each pile will have a random assortment of cards that’s still relatively balanced between colors, and so each booster is more likely to itself be color-balanced.
Bonus: True Randomization
If you really want to truly randomize your cube and you’re willing to do a bit more labor, there is a way to do so. It requires the aid of a computer and will probably take a lot more time than my good-enough method above, so I don’t really recommend it, but it’s fun to think about as a theoretical exercise.
First, choose a number p of piles as above. Generate a random list of C integers between 1 and p inclusive such that each number appears exactly C/p times. (If C isn’t divisible by p, each number can appear either ⌈C/p⌉ or ⌊C/p⌋ times.) I’ve written a handy script for this where you can just plug in C and p and press Run to get your sequence.
Now, for each card in the cube, look at the next number in the list and put that card in the corresponding pile. Once this is done, shuffle each pile individually and place it back into the cube box. The result will be a fully randomized cube.
We can verify this combinatorially: there are C! possible orderings of the cube, so if this technique generates C! unique orderings it must be truly random.
The number of unique orderings is equal to the number of unique ways the piles can be constructed multiplied by the number of unique ways all the piles can be shuffled.
The former is identical to the number of distinct sequences, since the sequences uniquely determine the arrangement of cards. The number of permutations of a sequence of length n with m₁ instances of one repeated element, m₂ of another, and so on is n!/(m₁!m₂!…). In our case, n = C and each mᵢ = C/p (the number of cards in each pile). There are p repeated sequences, so the number of unique possible sequences is C!/(C/p)!ᵖ.
Since there are C/p cards in each pile, it can be shuffled into one of (C/p)! possible orderings. And since there are p piles, there are (C/p)!ᵖ unique ways that all piles can be shuffled. This cancels out with the denominator of the number of unique possible sequences, so this technique can generate exactly C! unique orderings and is therefore truly random.
