FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Recreational
Shuffling decks of playing cards
Post new topic   Reply to topic Page 1 of 1 [7 Posts] View previous topic :: View next topic
Author Message
Christopher Night
science forum beginner


Joined: 30 May 2005
Posts: 29

PostPosted: Fri Jun 02, 2006 7:35 am    Post subject: Shuffling decks of playing cards Reply with 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.

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
Back to top
jaapsch
science forum beginner


Joined: 06 Jun 2005
Posts: 25

PostPosted: Fri Jun 02, 2006 1:57 pm    Post subject: Re: Shuffling decks of playing cards Reply with quote

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
Back to top
Lynn Kurtz
science forum Guru


Joined: 02 May 2005
Posts: 603

PostPosted: Fri Jun 02, 2006 5:57 pm    Post subject: Re: Shuffling decks of playing cards Reply with quote

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
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sat Jun 03, 2006 4:30 am    Post subject: Re: Shuffling decks of playing cards Reply with quote

[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
Back to top
Christopher Night
science forum beginner


Joined: 30 May 2005
Posts: 29

PostPosted: Mon Jun 05, 2006 9:30 pm    Post subject: Re: Shuffling decks of playing cards Reply with quote

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
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Wed Jun 07, 2006 11:39 pm    Post subject: Re: Shuffling decks of playing cards Reply with quote

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
Back to top
Old Earl
science forum beginner


Joined: 13 Feb 2005
Posts: 8

PostPosted: Sun Jun 11, 2006 3:43 pm    Post subject: Re: Shuffling decks of playing cards Reply with quote

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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [7 Posts] View previous topic :: View next topic
The time now is Tue Sep 19, 2017 10:22 pm | All times are GMT
Forum index » Science and Technology » Math » Recreational
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Probability: Ace of Spades from a pack of cards WhytheQ Math 4 Wed Jul 12, 2006 11:13 am
No new posts Optimal Strategy for playing the Stockmarket; Crossover t... a_plutonium@hotmail.com Math 0 Sat May 13, 2006 6:30 am
No new posts 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
No new posts Playing StockMarket with VonNeumann Optimal Strategy Game... a_plutonium@hotmail.com Math 2 Wed Mar 22, 2006 7:47 pm
No new posts playing the StockMarket VonNeumann gametheory with Crosso... a_plutonium@hotmail.com Math 0 Tue Mar 07, 2006 7:30 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0458s ][ Queries: 16 (0.0219s) ][ GZIP on - Debug on ]