It's amazing how high a number you can get to with a deck of cards!

[andrewducker]

Would you like your mind blown?

To imagine the number of ways a standard pack of playing cards can be uniquely shuffled, follow these simple instructions:

Go to the equator with a deck of cards and start shuffling them. Shuffle them so that every second you produce a new and unique ordering of cards. Keep shuffling them over and over, a new ordering, every second, for a billion years.

At the end of a billion years take a single step forward.

Keep shuffling.

Every billion years keep taking a single step forward.

Once you have circumnavigated the Earth, take a single drop of water out of the Pacific Ocean. Keep shuffling. Keep taking a single step every billion years. Keep taking a single drop of water out of the Pacific Ocean each time you walk around the Earth.

Once the Pacific Ocean is dry, refill it and place a single piece of paper on the ground.

Keep shuffling.

Keep taking billion year steps. Keep taking a drop out of the Pacific Ocean with each return to your start point. Keep refilling the Pacific Ocean once dry. Keep building your tower of paper one sheet at a time.

Once your tower of paper is as tall as Mount Everest, throw it away and place a single grain of sand on a weighing scale.

Don't stop shuffling.

Don't stop taking a step every billion years.

Don't stop emptying the Pacific Ocean and refilling it to build an Everest of paper.

Don't stop throwing your paper tower away to place another grain of sand on your weighing scales.

On the other side of your scale is a bull elephant. When it raises off the ground you will be half way done.

To see the maths behind this, click here.

(With thanks to my brother Mike, who saw a version of this which wasn't as good, rewrote chunks of it and did the maths.)

Comments

[wildeabandon]

IANA programmer, but my naive assumption would be that if you wanted to represent a shuffle digitally then you'd do it as a series of 51 integers, the first between 1-52, the second between 1-51, and so on, rather than enumerating all the possibilities. And so to generate a random shuffle the largest input your RNG would have to cope with is 52. Is this naive in a stupid way?

[fanf]

Not at all stupid, it isn’t very intuitive :-)

For shuffling cards it’s the outputs of the RNG that are limited to 52. All of those outputs come from the RNG’s seed which is set once when the program starts; the RNG in effect stretches out one input number, the seed, into some arbitrarily long sequence of output numbers. The size of the seed and the size of the internal state of the RNG both determine how many different sequences it can produce, and how long before a sequence starts repeating.

The seed is often, in old bad RNGs, not a very large number, up to a couple of billion or 2³¹. If your seed is that small your RNG can only produce 2³¹ different shuffles, not all 2²²⁶ shuffles. So the program needs to take care to get a seed that fills the RNG’s entire state with randomness (usually from the operating system’s RNG that uses measurements of the computer’s environment and activity to continually reseed itself with fresh randomness).

Then of course the RNG’s internal state needs to be large enough to produce at least 2²²⁶ different sequences. For instance, a state-of-the-art RNG called PCG64 uses two 128 bit numbers, s and i, and it repeatedly calculates s := s * m + i, using a multiplier m that was chosen by PCG’s designer to produce good randomness. The sequence is the successive values of s (with some extra mixing to improve the output’s randomness). It can produce 2¹²⁷ different sequences (corresponding to different values of i, which must be odd) starting at 2¹²⁸ different points in the sequence (corresponding to the initial value of s). So it can produce 2¹²⁷ * 2¹²⁸ / N sequences of length N, which is about 2²⁴⁹ when N is 52, decently larger than 52!.

When shuffling we take the huge number produced by the RNG and use the remainder after dividing by 52 to pick a card. (Then repeat for 51, 50, …) The hugeness of the numbers in the RNG ensures the number of possible sequences is larger than the number of possible shuffles, even though the size of the numbers we need for shuffling and the length of the sequence are both quite modest.

Another way to think of it is starting from your list of 52 numbers between 1 and 52. We can estimate how much space that list needs by rounding each number up to 6 bits (2⁶ = 64 > 52), giving a total of 6*52 = 312 bits. (Which is an overestimate for the actual number of shuffles because we rounded up, but 312 is not outlandishly more than 226.) And we want all of those bits to be chosen randomly to produce every possible shuffle, so our RNG needs at least that much randomness to work from.

[andrewducker]

Thank you, that was a great explanation.

[bens_dad]

Naive, but not in a stupid way.

Some ? many RNGs can produce a provably random number, but if you ask for 2 random numbers it can be shown that there is a (statistical ?) connection between them.

Thus if you cannot get the whole shuffled deck in one go you could find that once you have the first n cards, you can predict the order of the remaining 52-n cards.