Search   Memberlist   Usergroups
 Page 1 of 1 [7 Posts]
Author Message
Christopher Night
science forum beginner

Joined: 30 May 2005
Posts: 29

Posted: Fri Jun 02, 2006 7:35 am    Post subject: Shuffling decks of playing cards

Dear alt.math.recreational,

I read on MathWorld that you need 1.5 log_2(N) = log_1.59(N) shuffles to
randomize an N-card deck, and for a standard (52-card) deck, 7 shuffles is
pretty good. So I guess, since 81 < 52 * 1.59, that for a 81-card Set
deck, one extra shuffle should do the trick.

But lots of card games have decks with repeated cards, and this would seem
to reduce the number of necessary shuffles. Uno uses a deck with 4 unique
cards, 48 cards that appear twice, and 2 cards that appear four times, for
a total of 4 + 48 * 2 + 2 * 4 = 108 cards. But it shouldn't require as
many shuffles as a deck with 108 unique cards, should it?

The Great Dalmuti has an 80-card deck with only 13 distinct cards in
quantities 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12. I wouldn't be
surprised if this actually requires fewer than 7 shuffles to randomize.

I generally play Mao with two standard decks shuffled together, so that's
a 104-card deck comprising 52 pairs of identical cards.

So how do I find out how much I need to shuffle these things? It seems
like you could work it out by defining a deck entropy, then determining
how much a single shuffle increases that entropy. Or, a Monte Carlo
algorithm might be able to do it.

Also, how realistic is the so-called riffle shuffle? I separated a Mao
deck into a stack of 52 reds and a stack of 52 blacks and tried to shuffle
them once as best I could. A perfect riffle shuffle would have resulted in
52 separated sets of (a single) red interspersed with 52 sets of (a
single) black, but instead I got 28 and 28. Does that seriously affect the
result? Do I need to be shuffling a standard deck 11 times?

Thanks!
Christopher
jaapsch
science forum beginner

Joined: 06 Jun 2005
Posts: 25

Posted: Fri Jun 02, 2006 1:57 pm    Post subject: Re: Shuffling decks of playing cards

Christopher Night wrote:
 Quote: I read on MathWorld that you need 1.5 log_2(N) = log_1.59(N) shuffles to randomize an N-card deck, and for a standard (52-card) deck, 7 shuffles is pretty good. So I guess, since 81 < 52 * 1.59, that for a 81-card Set deck, one extra shuffle should do the trick.

I have not read the original paper (by Persi Diaconis I believe), but
have heard a few details. You don't say, but it is _riffle_ shuffles.
Other types of shuffle would need different amounts. In particular, the
number of overhand shuffles for a decent mix would need many more I
think.

 Quote: But lots of card games have decks with repeated cards, and this would seem to reduce the number of necessary shuffles. [snip] So how do I find out how much I need to shuffle these things? It seems like you could work it out by defining a deck entropy, then determining how much a single shuffle increases that entropy.

I think a fair shuffle was defined as making all 52! card permutations
equally likely (not actually exactly equal probabilities, but within a
very small range).

I suspect that having duplicate cards will not actually make much
difference, unless you have many identical cards. The shuffle procedure
has to be fair regardless of what order the cards are in at the start,
so if say every card has a single duplicate, you would probably need
the same number of shuffles. If however half the deck consisted of
identical cards, then you might need fewer.
I'm just guessing though.

 Quote: Also, how realistic is the so-called riffle shuffle?

In the paper this was modeled as follows: During a single riffle, the
probability of the next card dropping from the left pile versus the
next card coing from the right pile is directly dependent on the number
of cards left in each pile, i.e. L/(L+R) versus R/(L+R) where L and R
are the number of cards in the piles.

If your shuffles are different (e.g. too much clumping, or too
regular), then you may need more than the recommended number of
shuffles anyway.

J
Lynn Kurtz
science forum Guru

Joined: 02 May 2005
Posts: 603

Posted: Fri Jun 02, 2006 5:57 pm    Post subject: Re: Shuffling decks of playing cards

On Fri, 2 Jun 2006 03:35:58 -0400, Christopher Night
<night@fas.harvard.edu> wrote:

 Quote: Also, how realistic is the so-called riffle shuffle? I separated a Mao deck into a stack of 52 reds and a stack of 52 blacks and tried to shuffle them once as best I could. A perfect riffle shuffle would have resulted in 52 separated sets of (a single) red interspersed with 52 sets of (a single) black, but instead I got 28 and 28. Does that seriously affect the result? Do I need to be shuffling a standard deck 11 times?

I once wrote a little program to simulate a perfect riffle shuffle.
Split the deck evenly and intersperse every other card. If my memory
serves me correctly, after just a few shuffles the deck is back in the
order in which it started. I think the numer of shuffles was 7 but I
could be recalling incorrectly. In any case, perfect shuffles aren't
good.

--Lynn
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Sat Jun 03, 2006 4:30 am    Post subject: Re: Shuffling decks of playing cards

[Mr.] Lynn Kurtz wrote:
 Quote: On Fri, 2 Jun 2006 03:35:58 -0400, Christopher Night night@fas.harvard.edu> wrote: Also, how realistic is the so-called riffle shuffle? I separated a Mao deck into a stack of 52 reds and a stack of 52 blacks and tried to shuffle them once as best I could. A perfect riffle shuffle would have resulted in 52 separated sets of (a single) red interspersed with 52 sets of (a single) black, but instead I got 28 and 28. Does that seriously affect the result? Do I need to be shuffling a standard deck 11 times? I once wrote a little program to simulate a perfect riffle shuffle. Split the deck evenly and intersperse every other card. If my memory serves me correctly, after just a few shuffles the deck is back in the order in which it started. I think the numer of shuffles was 7 but I could be recalling incorrectly. In any case, perfect shuffles aren't good.

I'd heard it was 8. In either case, it's a lot smaller than you'd
expect.

(A few minutes later.) Actually, it _is_ 8. The number of perfect
riffle shuffles needed to return a deck of N cards into its original
order is given by sequence A024222 in the Online Encyclopedia of
Integer Sequences:

http://www.research.att.com/~njas/sequences/A024222
http://www.research.att.com/~njas/sequences/table?a=24222&fmt=4

--- Christopher Heckman
Christopher Night
science forum beginner

Joined: 30 May 2005
Posts: 29

Posted: Mon Jun 05, 2006 9:30 pm    Post subject: Re: Shuffling decks of playing cards

On Fri, 2 Jun 2006, jaapsch wrote:
 Quote: Christopher Night wrote: I read on MathWorld that you need 1.5 log_2(N) = log_1.59(N) shuffles to randomize an N-card deck, and for a standard (52-card) deck, 7 shuffles is pretty good. So I guess, since 81 < 52 * 1.59, that for a 81-card Set deck, one extra shuffle should do the trick. You don't say, but it is _riffle_ shuffles. Other types of shuffle would need different amounts. In particular, the number of overhand shuffles for a decent mix would need many more I think.

True. Since riffle shuffle is the only one I ever use it didn't occur to
me that unqualified "shuffle" could mean anything else. But you're right.
I wonder if anyone's studied shuffling like my 8-year-old cousin, which
involves putting the deck in a few piles on the table then picking it back
up in a different order. :-)

 Quote: But lots of card games have decks with repeated cards, and this would seem to reduce the number of necessary shuffles. [snip] So how do I find out how much I need to shuffle these things? It seems like you could work it out by defining a deck entropy, then determining how much a single shuffle increases that entropy. I think a fair shuffle was defined as making all 52! card permutations equally likely (not actually exactly equal probabilities, but within a very small range).

I wonder what the convergence is like. If it's slow, then the value of
this very small range has a big impact. If we require every permutation's
probability to be no greater than 10% away from 1/52!, how different will
the required shuffle count be from if we required 1% away?

 Quote: I suspect that having duplicate cards will not actually make much difference, unless you have many identical cards. The shuffle procedure has to be fair regardless of what order the cards are in at the start, so if say every card has a single duplicate, you would probably need the same number of shuffles. If however half the deck consisted of identical cards, then you might need fewer. I'm just guessing though.

A standard card deck has 52! = 10^67.9 permutations, whereas a Great
Dalmuti deck has 80!/(12! 11! ... 3! 2! 2!) = 10^74.4 permutations.
However, assuming a perfect cut, there are 52C26 = 10^14.7 possible riffle
shuffles in a standard deck but 80C40 = 10^23.0 possible riffle shuffles
in a Dalmuti deck. For a standard deck, 67.9/14.7 = 4.6 is greater than
a Dalmuti deck's 74.4/23.0 = 3.2. That's why I think shuffling a Dalmuti
deck might be faster. But this doesn't take into account that some
shuffles are much more probable than others, and I'm not even sure if
dividing the logs is the right statistic to look at. It's totally guessing
on my part.

-Christopher
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Jun 07, 2006 11:39 pm    Post subject: Re: Shuffling decks of playing cards

Christopher Night wrote:
 Quote: Dear alt.math.recreational, I read on MathWorld that you need 1.5 log_2(N) = log_1.59(N) shuffles to randomize an N-card deck, and for a standard (52-card) deck, 7 shuffles is pretty good. So I guess, since 81 < 52 * 1.59, that for a 81-card Set deck, one extra shuffle should do the trick. But lots of card games have decks with repeated cards, and this would seem to reduce the number of necessary shuffles. Uno uses a deck with 4 unique cards, 48 cards that appear twice, and 2 cards that appear four times, for a total of 4 + 48 * 2 + 2 * 4 = 108 cards. But it shouldn't require as many shuffles as a deck with 108 unique cards, should it? The Great Dalmuti has an 80-card deck with only 13 distinct cards in quantities 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12. I wouldn't be surprised if this actually requires fewer than 7 shuffles to randomize. I generally play Mao with two standard decks shuffled together, so that's a 104-card deck comprising 52 pairs of identical cards. So how do I find out how much I need to shuffle these things? It seems like you could work it out by defining a deck entropy, then determining how much a single shuffle increases that entropy. Or, a Monte Carlo algorithm might be able to do it.

You may want to check out the paper at
http://xxx.lanl.gov/abs/math.PR/0606031 :

There is a lot of theory in it, but they should at least point you in
the right direction. Section 7, for instance, focuses on the Blackjack
version.

--- Christopher Heckman
Old Earl
science forum beginner

Joined: 13 Feb 2005
Posts: 8

Posted: Sun Jun 11, 2006 3:43 pm    Post subject: Re: Shuffling decks of playing cards

Proginoskes wrote:
 Quote: [Mr.] Lynn Kurtz wrote: On Fri, 2 Jun 2006 03:35:58 -0400, Christopher Night night@fas.harvard.edu> wrote: Also, how realistic is the so-called riffle shuffle? I separated a Mao deck into a stack of 52 reds and a stack of 52 blacks and tried to shuffle them once as best I could. A perfect riffle shuffle would have resulted in 52 separated sets of (a single) red interspersed with 52 sets of (a single) black, but instead I got 28 and 28. Does that seriously affect the result? Do I need to be shuffling a standard deck 11 times? I once wrote a little program to simulate a perfect riffle shuffle. Split the deck evenly and intersperse every other card. If my memory serves me correctly, after just a few shuffles the deck is back in the order in which it started. I think the numer of shuffles was 7 but I could be recalling incorrectly. In any case, perfect shuffles aren't good. I'd heard it was 8. In either case, it's a lot smaller than you'd expect. (A few minutes later.) Actually, it _is_ 8. The number of perfect riffle shuffles needed to return a deck of N cards into its original order is given by sequence A024222 in the Online Encyclopedia of Integer Sequences: http://www.research.att.com/~njas/sequences/A024222 http://www.research.att.com/~njas/sequences/table?a=24222&fmt=4 --- Christopher Heckman

I found a curious result when I attempted to check out the 8 perfect
shuffle result.
Assume we split the deck into two sections, the left hand side from the
top of the deck, and the right hand side from the bottom. If I shuffle
the cards so that the top card from the left hand stack ends up on top
of the merged deck, it takes 8 shuffles to restore the deck to the
preshuffle order. However, if I shuffle the cards so that the top card
from the right hand stack is on top, it takes 52 shuffles to restore
order!

Old Earl

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [7 Posts]
 The time now is Tue Mar 26, 2019 2:57 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Probability: Ace of Spades from a pack of cards WhytheQ Math 4 Wed Jul 12, 2006 11:13 am Optimal Strategy for playing the Stockmarket; Crossover t... a_plutonium@hotmail.com Math 0 Sat May 13, 2006 6:30 am Prof Piano Man, remember part of being a musician is stu... FBI? Don't bother me, it' Relativity 0 Thu May 04, 2006 3:25 am Playing StockMarket with VonNeumann Optimal Strategy Game... a_plutonium@hotmail.com Math 2 Wed Mar 22, 2006 7:47 pm playing the StockMarket VonNeumann gametheory with Crosso... a_plutonium@hotmail.com Math 0 Tue Mar 07, 2006 7:30 pm