Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
By the way Donald Knuth's TAOCP has some extended material on shuffling decks and analysis thereof. Just thought you might be interested. –  Kaz Oct 21 '12 at 2:05

3 Answers 3

up vote 14 down vote accepted

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

enter image description here

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$.)

share|improve this answer
2  
To make my point about evaluating decks vs. probability distributions more explicitly, consider an algorithm which returns the same very good shuffle each time. This is not the algorithm you want even though, every time you run it, a "randomness test" would certify that its output is very "random"! For a more realistic example, consider an algorithm which returns one of $10^{10}$ very good shuffles each time. This is still not the algorithm you want even though you probably wouldn't be able to tell for awhile. –  Qiaochu Yuan Oct 20 '12 at 22:16
1  
There are actually $52! \approx 8 \cdot 10^{67}$ possible decks and $10^{10}$ of them is really not very many! –  Qiaochu Yuan Oct 20 '12 at 22:19
    
Persian Diaconis is actually my inspiration, but my algorithm doesn't do a riffle shuffle. I don't know what the official name is of the shuffle I get the program to do. You're right however, i want uniform distribution of cards after x iterations of this algorithm, and I want to find x. So that between games the same runs don't appear. –  Pureferret Oct 21 '12 at 7:00

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.

share|improve this answer

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...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.