Krdytkyu

I play a few card games, and I thought it would be fun to write a card shuffling program, to see how many shuffles it takes to randomize the deck.

The algorithm is:

1. Cut the deck in the middle ± random offset.


2. while one hand is still full, place a small but random number of cards into the second hand in the front/back/both.


3. repeat until random.

The question is, how do I check for randomness? I've considered that this might be a 52-spin Ising model, and I can make some function 'cost energy's when they are ordered (ie ace of clubs followed by two of clubs 'cost' more than being next to say the seven of hearts) but this might be overkill...

Is there a mathematical test for randomness I could use here, to check the order of my cards?

Randomness is not a property of a deck, it is a property of a probability distribution over decks. xkcd said it best:

This is not the algorithm you want. What you actually want to check is whether your algorithm, after $n$ iterations, produces a distribution over decks that is approximately uniform. Fortunately, someone has already done the work for you: Persi Diaconis showed that it takes about $7$ riffle shuffles.

If you don't want to rely on that result, just run your algorithm lots of times and keep track of which decks show up depending on how many times in a row you run it. (Probably you shouldn't keep track of decks themselves but rather the first $k$ cards in them for some reasonable $k$.)

If you do a few thousand or tens of thousands of runs of your algorithm, you can look at the distribution of where the first (and each other) card ends up. It should be reasonably uniform, and the chi-square test can tell you if the unevenness that you see is to be expected. I would also check how far apart cards that started out together finish. It looks like your algorithm might not split them apart soon enough.

Valid or useful or interesting notions of "random-ness" need more than basic probability notions, since the probability of 100 "heads" in flipping a fair coin has the same probability as any other specific sequence of outcomes, but is arguably implausible as a "random" outcome.

To my mind, the "Kolmogorov-Solomonoff-Chaitin" notion of "complexity" is the apt notion. This is discussed wonderfully and at length in the first part of Li-Vitanyi's book on the subject.

A crude approximation of the idea is that a "thing" is "random" if it admits no simpler description than itself (!). Yes, of course, this depends on the language/descriptive apparatus, but has provable sense when suitably qualified.

Given that most card games refer to discernible "patterns" (things with compressible descriptions), a "random" hand would be one lacking two-of-a-kind, and so on. A "random" distribution in a deck would, in particular, have no more pattern in it than might be "expected".

The question of whether there is a notion of "too-violent-to-be-random" non-pattern-forming in a given context seems to be ambiguous: while long runs of all heads or all tails are suspicious, lack of them is also suspicious. This kind of example suggests that a configuration of a deck of cards to that no one has a playable hand might also be suspicious... depending on the context.

The operationally significant question of whether or not an innocent-seeming "mixing" can produce "randomness" with relatively few iterations is slightly different. However, from the viewpoint of "complexity", surely the answer is "no", since the hands-of-cards which arise in this way immediately admit a much simpler description than themselves. Nevertheless, or perhaps because of this observation, we can decide to declare a merely relative notion of randomness for a deck of cards, in terms of a small proper subset of "genuine" tests of "randomness/compressibility".

Of course, if the only "deals" of hands of cards that were allowed were "random" in any strong sense, the probability would be very low that anyone would have a playable hand...