Sign in to follow this  
chuck22

determining if cards are random

Recommended Posts

i am going to create a simple simulation of the way i shuffle a deck of cards. i know of one way to shuffle a deck completely. for a deck the size of 52, i could go through each card and swap it with a random card, and do this for 7 iterations (size of deck ~ # if iterations ^ 2). and this should result in a random deck but that isn't my problem. i shuffle a deck by "bridging it" i believe it's called. cut the deck in half, bend up the inner edges of both halves, and weave the two decks together. and then i repeat the process a certain number of times. i am curious to know if this will create a random instance of the deck but i am not sure how to measure whether or not the cards are random. intuitively, i would assume that you would need to know the prior state of the cards for comparison. for example in a 6 card deck: 5, 2, 6, 1, 3, 4 may seem random. but if my shuffling method is to simply cut the deck in the middle, the cards now show: 1, 3, 4, 5, 2, 6. still seemingly random, but compared to the state they were in they are not random. also right off the bat, i would assume that in order for something to be random each card must have an equal chance of being in each position. and thirdly, you couldn't see any recurring patterns. (again, this would require knowing what state the cards were in prior to the shuffle). i think that i'm on the right track, but i don't know if there are any algo's commonly used that would do the trick for me.

Share this post


Link to post
Share on other sites
The easiest way is shuffle your deck of cards is using std::random_shuffle. It works very well, it is very fast, and it is bug-free.

The problem with a riffle shuffle is that the shuffle is not really very good (which is why you must do it several times) and simulating it on a computer is not as easy as just implementing (or using) random_shuffle.

There are several tests for randomness. The most test is a distribution test, but the distribution is fixed in this case. Another test is the chi-square test. If you are interested in random numbers, here is the standard reference, though it is getting old: Knuth, D. 1981. (1st ed. 1969.) The Art of Computer Programming. Volume 2: Seminumerical Algorithms. Addison-Wesley.

Share this post


Link to post
Share on other sites
i am only interested in determining randomness and i am very familiar with both of those tests. they weren't my favorite part of stats class.

i'm looking for something that can compare the current state of the deck of cards to a prior state of a deck of cards. there are a few ways to shuffle cards and certain methods, if not done extensively enough, may favor some card games over others.

consider this example: 5 people are playing 5 card draw poker. generally speaking each player organizes his hand from highest to lowest. cards that are folded are simply stacked on top of each other resulting in every 5th card being a high card. if someone was a really bad shuffler and only shuffled once or twice. those high cards may end up in one person's hand since they were stacked every 5 and there are 5 people playing.

in this example, the cards would seem pretty random because there are a mix of suits and numbers for each hand, but one person is favored over the other which is a result of a shuffle that didn't randomize the deck. this is my question. for examples that are not as simple and easy to understand, what kind of algorithm could detect if a shuffle was a "good" shuffle?

Share this post


Link to post
Share on other sites
Here's one idea:
Store the state of the pack before the shuffle
Shuffle it
For every card, check how far it is in the deck from the card that was adjacent to it before the shuffle.

If the average distance is not very far we could assume the deck may not have been shuffled well (although it could have been well shuffled, and we were unlucky to end up with a deck similar to what we started with).

If thats not explained very well here is an example:

before shuffle: King; Jack; 9 of spades; 4 of hearts; ace;
after shuffle: King; 9 of spades; Jack; 4 of hearts; ace;

King->Jack 1 (the jack is one card further away from the king than it used to be)
King->ace 0 (the ace is the same distance away from the king as it used to be)
9 of spades->Jack 0
9 of spades->4 of hearts 1
Jack->King 1
Jack->9 of spades 0
4 of hearts->9 of spades 1
4 of hearts->ace 0
ace->King 0
ace->4 of hearts 0
Total shuffle rating: 4

This out of a rating of 10 (I think).
Below say 5 we could say it isn't shuffled well.

Share this post


Link to post
Share on other sites
that's a pretty good solution, thanks.

i'm wondering where you got the rating of 10. is that the highest cummilative distance that cards could be from each other for a deck of that size?

Share this post


Link to post
Share on other sites
I think you should use a chi-square test.

First, always start with the cards in order, 1 to 52 or 0 to 51. There's no reason to start with an already shuffled deck; that would just complicate things. Now shuffle the deck. For each card, record how many times that card appears in each position after a shuffle. After each shuffle, reset the deck to be in order and then perform another shuffle and increment the observed values.

Now you have a 52 by 52 table of how frequently each card appeared in each position. You should do at least several hundred shuffles, the more the better, so that the expected frequencies can be approximated with a normal curve. The more samples the closer it will come to a normal curve (central limit theorem). The chi-square test assumes normal distributions.

Now perform the chi-square test. Every cell in the table has an expected value of NumTrials/52. There are 51*51 = 2601 degrees of freedom. Actually with that many degrees of freedom I guess the chi square distribution would be pretty close to a normal curve...you can find more about that in the wikipedia article on the distribution.

Note that you can't really test that the distribution is random, you can just test if it passes this test. It is possible to come up with an algorithm that isn't random when another test is applied but that would still pass this test. If the shuffle fails this test, then it is probably not random. If it passes this test, that doesn't mean it is random, it only means that it was not non-random according to this test.

To really test a shuffling algorithm, you should always perform much more than one trial. Even with a perfect shuffle, there is a chance that the cards will end up close to their starting positions, or something similiar. Statistical tests rely on distributions.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this