From: wft@math.canterbury.ac.nz (Bill Taylor) Newsgroups: sci.math Subject: Re: Shuffling Cards: How often do do it GOOD?? (well,that is) Date: 26 Nov 1995 03:36:04 GMT zare@cco.caltech.edu (Douglas J. Zare) writes: Very nice little artyicle, Douglas! Thanks. Here's a re-post of one of mine. |> Persi Diaconnis (sp?) is a pioneer in this area and has written some |> popular expositions recently that should be easy to find. The paper to see is without doubt "Trailing the Dovetail Shuffle to Its Lair", by Dave Bayer & Persi Diaconis, Annals App. Prob, Vol 2 # 2, May 1992, p 294. There they give copious theory, and Monte Carlo results on up to 100,000 sample n-riffles, finding (on one test) that 10 (without cut) or 9 (with cut) are needed to remove detectable non-randomization. Author Persi Diaconis (who sounds more like a star or a constellation than a person!) is without doubt the top authority in this area, and in fact comes from a gambling background, I understand. If it weren't for this last fact I'd challenge him to a riffle-&-test competition; but he'd be sure to win any card-handling contest! The thing is, my own desk-top hand (not computer) simulations suggest that 5 riffles is sufficient to remove easily detectable non-randomness. Looking closely at the above paper, one sees that their riffling model has two parts, a binomial distribution for how the pack is separated into 2 sections, and simple conditional choice-probabilities for determining which section's bottom card is dropped into the shuffled pile. The second part seems fair enough, but my desk-top hand simulations suggest to me that the first part of the model is seriously defective. Their model is to split the pack into sections of X & 52-X, with X as Binomial(52, 0.5). However this gives a standard deviation of sqrt(13) = 3.6, which is very noticably too high for careful cutting, though probably reasonable for card games in the heat of the moment. But; if you cut carefully, you can get noticably closer to 26,26 more often than the above Binomial; and this leads to definitely fewer than 7 being needed; as I say, 5 is my figure. It's still faintly but clearly detectable that 4 riffles are not enough, even with the most careful cutting; and easy to show that 3 can't possibly be enough; (see their section on "rising sequences"). So in summary - 9 riffles for computer simulations, 7 riffles for day-to-day card games, 5 riffles for very careful cutting. Bill Taylor wft@math.canterbury.ac.nz ------------------------------------------------------------------------------- ============================================================================== From: Benjamin.J.Tilly@dartmouth.edu (Benjamin J. Tilly) Newsgroups: sci.math Subject: Re: Card Shuffling/Persi Diaconis Date: 17 Feb 1995 06:22:06 GMT In article <3i0r52$sni@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes: > The paper to see is without doubt "Trailing the Dovetail Shuffle to Its Lair", > by Dave Bayer & Persi Diaconis, Annals App. Prob, Vol 2 # 2, May 1992, p 294. > > Here is an old post I wrote about this. > > ---------------------- > > |> I once read that if one shuffles a deck of cards 7 times it will > |> be completly randomized. Also, there was a proof of this. What > |> i'm looking for is a reference to this proof (for a paper). > > There isn't really any watertight definition of "completely randomized", of > course, but for most practical purposes 7 is held to be the correct lower > bound on the number of safe riffle shuffles. However, if sufficiently sensitive > tests are done on sufficiently many sample runs, then it may need to be more, > before no bias can be detected. > The number of sample runs to see a strong bias need not be that long. I do not remember some of the details, but here goes what I remember from a talk by Peter Doyle on the topic. Take a new deck and throw out the jokers. Shuffle 7 times. Now go through the deck and when you see an ace put it down, then as you go through the deck lay down cards of the same suit as you run across them in order. (ie if you see the ace of spades then the next spade you lay down is the two, then the three, and so on.) When you reach the bottom of the deck turn it over and continue. (Make sure that you keep the order the same instead of reversing it.) Keep on and record how many times you had to go through to finish each suit. Now the trick here is that a fresh deck has two suits ordered from smallest to largest, and two ordered from largest to smallest. After 7 shuffles there is still a significant difference, with the result that two of the suits consistently differ. In the talk they handed out about 20 fresh decks to the audience, and the vast majority of them had the two suits that they said would finish first finish before the other two suits. There was basically no real comparison. > The paper to see is without doubt "Trailing the Dovetail Shuffle to Its Lair", > by Dave Bayer & Persi Diaconis, Annals App. Prob, Vol 2 # 2, May 1992, p 294. > > There they give copious theory, and Monte Carlo results on up to 100,000 sample > n-riffles, finding (on one test) that 10 (without cut) or 9 (with cut) are > needed to remove detectable non-randomization. Author Persi Diaconis (who > sounds more like a star or a constellation than a person!) is without doubt the > top authority in this area, and in fact comes from a tough gambling background, > I understand. If it weren't for this last fact I'd challenge him to a > riffle-&-test competition; but he'd be sure to win any card-handling contest! > Detectable IN HIS MEASURE. It can be questioned whether his measure is really what you want, and the test that I just described clearly shows a strong bias. [...] > So in summary - 9 riffles for computer simulations, > 7 riffles for day-to-day card games, > 5 riffles for very careful cutting. When you consider that the sorts of patterns that are detected in the above test are things that matter for ordinary card games, you can argue that the above guidelines were not really proven. But then again for a game it generally does not matter so shuffle however many or few times you want. Ben Tilly