Randomization with an imperfect shuffle

[Bozeman]

A few random questions:

Is there are good measure of how random a reordering of the deck is?

I typically make 5-10 "mistakes" vs. a perfect riffle shuffle, that is, instead of being 2121212121, my deck would be something like 2121221211 = 2 "mistakes". How many of these somewhat imperfect riffle shuffles is necessary to well randomize the deck?

How does this number depend on # of mistakes made?

What assumptions were used in the standard 7 shuffle result?

Does smooshing the cards help? How much?

Is there a better way to shuffle?

How do autoshufflers do it?

Craig

[Mike Haven]

and why does it matter if you have a "good" shuffle as long as no one has any more knowledge of the next card than anyone else?

[lunchmeat]

[ QUOTE ]
and why does it matter if you have a "good" shuffle as long as no one has any more knowledge of the next card than anyone else?

[/ QUOTE ]

It's useful because if you're able to track which card ends up at the bottom of the deck after the shuffle, and the deck is cut perfectly in half (which happens more often than you'd probably expect) you know what the turn card is in a 10 handed hold 'em game.

[Mike Haven]

agreed

i show this very instance in my demonstrations for cheat detection

but my question was "... as long as no one has any more knowledge of the next card than anyone else ..."

in some of our home games, some of our shufflers have plates for hands, and their shuffles are little more than half a dozen deck-cuts

we all have exactly the same opportunity to track cards if we want to

if there are others doing so, it doesn't seem to do them much good

as long as the shuffler is not taking unfair advantage, i see no problem with any sort of shuffle

[pzhon]

[ QUOTE ]
A few random questions:

Is there are good measure of how random a reordering of the deck is?


[/ QUOTE ]

The typical measure used is the L1 norm between the uniform distribution and the actual distribution. This is the maximum absolute distortion of the probability of a collection of events, 2 Max_X |Prob_actual(X) - Prob_uniform(X)|.

I don't think this is a good measure. The reason is that in practice, we don't use a priori probabilities, but rather conditional probabilities based on the information we see. A better measure would indicate the maximum or average distortion of conditional probabilities over a set of reasonable, observable conditions. For example, given that you see your own cards are 9h 8h, what is the conditional probability that the flop will give you a flush? This conditional probability is very relevant to Hold'em, but the probabilities involved are small because it is very unlikely to have any particular hand. So, it could be that the conditional probability would be far off without the L1 norm detecting this properly. It is conceivable that shuffles that would leave no usable information in poker would be too weak for bridge, and vice versa.

[ QUOTE ]

I typically make 5-10 "mistakes" vs. a perfect riffle shuffle, that is, instead of being 2121212121, my deck would be something like 2121221211 = 2 "mistakes". How many of these somewhat imperfect riffle shuffles is necessary to well randomize the deck?


[/ QUOTE ]

I don't know, although I think it can be analyzed, and may have been. You want to see a lot of possible "mistakes." One rough bound you can use is to count the number of possible shuffles you make. That to the nth power must be greater than the total number of orderings of the deck in order to have a hope of obtaining a good shuffle by the L1 norm.

There are about 2^52 ~ 4.5 x 10^15 riffle shuffles and 52! ~ 8.1 x 10^67 orderings of the deck, so by this argument you need at least 5 riffle shuffles to hope to randomize the deck by the L1 measure. That's not too far off of 7. If you make 5 mistakes, perhaps you only have 2 x 10^6 possible shuffles, in which case you need to shuffle at least 11 times.

[ QUOTE ]

What assumptions were used in the standard 7 shuffle result?


[/ QUOTE ]

I believe that in the original, uniformly random riffle shuffles were performed. The two halves of the deck do not have to be the same size, and every pattern of interleaving two pieces is equally likely. The random riffle shuffle is the inverse of dealing randomly into two piles, then stacking the first pile onto the second pile. There are other results based on different methods of shuffling.

One statement of the 7 shuffles result is that the inflection point of the L1 distance from random is at 7 shuffles. Additional shuffles do make the deck more random, but there are declining returns.

With real shuffles, you may still see clear patterns after 7 shuffles. It is better to shuffle more.


[/ QUOTE ]

[Bozeman]

Thanks.

It seems to me that among riffle shuffles with equal size piles with a fixed # of "mistakes", there should an optimum #: a perfect shuffle will never randomize the deck, and a shuffle entirely of mistakes doesn't rearrange the deck at all (or is just a cut). Is this number ~ 1/2 the deck size?

Craig

[pzhon]

[ QUOTE ]
It seems to me that among riffle shuffles with equal size piles with a fixed # of "mistakes", there should an optimum #: a perfect shuffle will never randomize the deck, and a shuffle entirely of mistakes doesn't rearrange the deck at all (or is just a cut). Is this number ~ 1/2 the deck size?


[/ QUOTE ]

I believe a random riffle shuffle has a roughly binomial distribution of "mistakes." My guess is that this is better than choosing a particular number of mistakes to make, but the difference between the random mistakes and making 26 mistakes every time may be small.

[M.B.E.]

I don't know if it's what you're looking for, but you may find this link interesting:

http://triumvir.org/rng/#tests