Shuffled?

Can I write a program that can tell me whether a deck of cards has been shuffled? If not, why not? If so, where can I find an example?

Sounds easy enough.

But what is your definition of 'shuffled'? If a single card is swapped with one other single card, is the deck 'shuffled'? That's the hard part.

$deck_is_shuffled = 1 if(! DeckIsInOrder());

No, of course not.

Any order of the cards could be produced either by shuffling or by deliberate selection of that order.

Say I have a ticket for one of those lotteries where you choose 6 numbers and win if they match the numbers drawn by the officials. You see my ticket and it has the numbers 3, 5, 13, 15, 19, and 30 on it. Can you tell whether I chose those deliberately or did the equivalent of drawing 6 cards from a shuffled deck, such as running a random number program? Of course not.

ObPuzzle: how did I obtain those numbers?

No.

Because a shuffled deck can be in any order. And, depending on what has been previously done with the cards, maybe an unshuffled deck can be in any order.

It may be possible to write a program which can study a deck and sometimes deduce e.g. 'This deck was not last used for duplicate bridge', or 'This deck was not last used for rubber bridge'. But even this makes assumptions about how tidily people pick up the cards when they have finished the hand.

Yes, there are programs designed to test for randomness. The tests are used to evaluate cryptographic algorithms and random number generators, so you may be able to find more information on one on the cryptography newsgroups.

10 print 'yes'

an example?

...

...

...

Some pretty black/white answers here. Well it comes down to probabilities of course. If you assume that a completely 'unshuffled' deck has all suits grouped and sequentially sorted, then you can measure how 'far' from shuffled you are by assigning some sort of score to an order, which measures things like unbroken runs of suits/sequences. If you do your job well, then scoring every possible order will give you curve a bit like half a bell, in which the majority of 'random looking' hands will be grouped on one end, with a smaller number of 'badly shuffled' hands grouped down the other end, with 'shop order' right at the end.

What you're asking for if I'm not mistook, is a scoring function which will give you such a curve. I don't believe that a randomness test borrowed directly from cryptography will be exactly right, since you are interested in 'features' in the card order which are specific to playing cards (suits and sequence both).

I think you have to decide how much you are going to weight such features and design you own test - something fairly simple will probably do, such as:

1. Count 1 point for every run of three cards in the same suit, 2 for four cards, 4 for five, 6 for six etc. 2. Count how many groups of three-, four-, five-in-a-row of the same suit occur. Score 5 for the third occurrence and 10 for each further occurrence (detects standard trick-taking with suit-following games, with 3, 4 or 5 players) 3. Count points for sequences of cards in order (any suit) Detects some other games. 4. Score huge points for runs of suit and sequence both. Detects badly shuffled new packs and possibly some games. 5. Score groupings of three or four cards of the same rank: As usual, lots of points for many such occurrences. Detects Rummy etc. etc etc

Bear in mind that if you want an unequivocal answer with 100% confidence, then the first two answers above apply - it can't be done. Any shuffling mechanism which is incapable of producing 'shop order' with *equal likelihood* is broke.

However if you want some indication that a deck is 'probably poorly shuffled after being bought' or 'likely not shuffled at all after a game of Bridge' then I think such a scoring function can give you a fairly high level of confidence.

If you want to know exactly how high, I think you're in for a rough statistical ride from one of the regular posters here :>

...

It's easy to say 'No, you can't do it' in response to a question like this, but bear in mind that a 6-year-old can detect 'lack of shuffling' in a card deck with high degree of confidence, so we should be able to do at least something with a program.

Simon Foster:

Patrick Hamlyn:

Irrelevant. We weren't asked a question *like* that, such as 'Can I write a program that can tell me with a high degree of confidence whether a deck of cards has been shuffled?'. We were asked *that* question, quoted above. To which the answer is no.

You can write a program to test if the distribution is what is to be expected from a random arrangement. We would expect that in a proper shuffle _all_ the spades wouldn't be together. But some of them should be. What is the probability that there will be n consecutive spades? How far does the actual distribution differ from what is expected? You can have confidence that the cards have been shuffled if they pass enough tests for randomness.

If I flipped a coin 1024 times and told you I got 800 H and 224 T, we would suspect an unfair coin. If the counts were 500 and 524, our confidence would be higher, but...

...suppose I told you the sequence was

HTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT...

Doesn't look random. It looks _too_ fair. There should be some clumpiness

HTHTTHTHTHHHTHTHTHTHTHHHTHTTTTHTHTHTHHTHTTTHTHTH...

At one point we got 4 T in a row. Is that within the range we expect? The probability of getting n-in-a-row is (1/2)^n, so for 1024 coin flips we can expect a 10-in-a-row somewhere in the sequence. If the maximum n-in-a-row was 4, we would again suspect that the results are not random but just me banging on the keyboard.

Consider also that the n-in-a-row counts should be a negative binomial distribtion. Twice as many 1-in-a-row as 2-in-a-row, twice as many 2-in-a-row as 3-in-a-row, twice as many 3-in-a-row as 4-in-a-row, etc.

Of course there are non-random sequences that pass all three of the above criteria

HHHHHHHHHHTTTTTTTTTHHHHHHHHHTTTTTTTTHHHHHHHHTTTTTTTTHHH HHHHHTTTTTTTHHHHHHHTTTTTTT...

I have a process whose run time is dependant on the number of consecutive 1s and 0s in a binary number. The run time is predictable when the binary numbers are patterned (such as 10101010 or 1111000011110000). The problem is that many appear to be random sequences.

Like your problem, I need to know when then bit pattern is 'random' in order to apply the correct constant to my run-time equation. If it passes the test for negative binomial distribution, then I consider it random.

For my purposes, it doesn't matter whether they were generated randomly, it only matters that they look like a negative binomial distribution. A negative binomial distribution has the neat property that the mean is the inverse of the probabilty. This means my random sequeneces always have a mean length of 2 bits regardless of whether the sequences are 1000, 2000, 4000, 8000 or 177000 bits long. The run-time equation for random numbers has a constant based on this mean 2-bit sequence. Naturally, for 'small' numbers of 1000 bits, the prediction can have an error of as much as 20%, but it improves with larger numbers (less than 5% for 8000 bits).

So it is possible to make statistics work for you, although I wouldn't actually want to test a deck of cards. I would just hope my random number generator does a good enough job 'shuffling' the deck.

To which people have offered various opinions. I won't add an opinion. But I notice a similarity in this issue and the recent charges that McDonald's 'Monopoly' promotional game was fixed.

According to this morning's paper, 5 of the last 8 big prize money ($500K - $1M US dollars) winners lived within a 30 miles of each other. This was a contest run all over the continental U.S.

Can one tell from this evidence alone that the winning 'tickets' were distributed in a random manner?

Bob H

P.S. The alleged mastermind lives in the same town I do. What are the odds of *that* happening?

Yes, the distribution of winnings demonstrates that the tickets were NOT randomly distributed. Alarms should have gone off the moment they had two winners within 30 miles of each other. Even when fraud is not involved, it is important to make sure the prizes are distributed fairly.

In carnival games of chance, the games are rigged so that the players chance of winning anything valuable is 0. The cheap plastic crap they had out is referred to as 'slum'.

So McDonald's has the games rigged so that no one can win, they pass out 'slum' (french fries and cokes), and their spokesman is a clown. What a PR nightmare!