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 Ncard deck, and for a standard (52card) deck, 7 shuffles is
pretty good. So I guess, since 81 < 52 * 1.59, that for a 81card 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 80card 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 104card 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 socalled 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 

Back to top 


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 Ncard deck, and for a standard (52card) deck, 7 shuffles is
pretty good. So I guess, since 81 < 52 * 1.59, that for a 81card 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 socalled 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 

Back to top 


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 socalled 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 

Back to top 


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 socalled 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 

Back to top 


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 Ncard deck, and for a standard (52card) deck, 7
shuffles is pretty good. So I guess, since 81 < 52 * 1.59, that for a
81card 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 8yearold 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 

Back to top 


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 Ncard deck, and for a standard (52card) deck, 7 shuffles is
pretty good. So I guess, since 81 < 52 * 1.59, that for a 81card 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 80card 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 104card 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 

Back to top 


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 socalled 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 

Back to top 


Google


Back to top 



The time now is Fri Nov 17, 2017 5:22 pm  All times are GMT

