Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Shuffling a Deck of Cards


Best Answer BMAD, 13 June 2013 - 12:01 AM

Spoiler for the answer is...
Go to the full post


  • Please log in to reply
18 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1664 posts
  • Gender:Female

Posted 27 May 2013 - 07:14 PM

How many random shuffles does it take to randomize a deck of cards?


  • 0

#2 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 521 posts

Posted 27 May 2013 - 08:41 PM

i guess it depends on your definition of random. my guess would be 1.


  • 0

#3 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1664 posts
  • Gender:Female

Posted 27 May 2013 - 09:01 PM

i guess it depends on your definition of random. my guess would be 1.

Assume the 52 card deck is in order at the beginning.  1,2,3,4,5,6,7,8,9,10,... how many shuffles would it take to truly break the order up


  • 0

#4 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 27 May 2013 - 11:07 PM

What's a "random shuffle"?  If it's the same as a random permutation, then phil1882 must be correct.  So, it's not that.  Please define "random shuffle".


  • 0

#5 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1664 posts
  • Gender:Female

Posted 27 May 2013 - 11:27 PM

I am referring to "riffle shuffles".  The random riffle shuffle is modeled by cutting the deck binomially and dropping cards one-by-one from either half of the deck with probability proportional to the current sizes of the deck halves.

 

How many shuffles must be done, to where every possible card configuration is possible?


  • 0

#6 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 82 posts

Posted 28 May 2013 - 01:32 PM

I am referring to "riffle shuffles".  The random riffle shuffle is modeled by cutting the deck binomially and dropping cards one-by-one from either half of the deck with probability proportional to the current sizes of the deck halves.

 

How many shuffles must be done, to where every possible card configuration is possible?

 

Minimum, maximum, or expected number of riffle shuffles? I assume the minimum and expected number are of the greatest interest. As it is possible to preserve the starting order through a riffle shuffle as described (the trivial shuffle), there is no defined maximum. The minimum is also not so useful, as each shuffle can add entropy to the order from 0 to some maximum value per shuffle.

 

As an estimate, it would be interesting to run a simulation to see how many shuffles, on average, are required to move the top card to the bottom of the deck, or the bottom card to the top. This is not directly related to the question, but might be one of the harder cases, and might therefore estimate the order of magnitude needed for the OP.

 

Analytic analysis is beyond me at the moment, even if I had the time.


  • 0

#7 kingofpain

kingofpain

    Advanced Member

  • Members
  • PipPipPip
  • 354 posts
  • Gender:Male

Posted 28 May 2013 - 02:58 PM

My view on this - and I am not inclined to calculate the probability myself - is that when the probability of finding the bottom card in the pile at the top of the pile is exactly 1/52, that is when we can consider the pack to be truly random. The easiest way I can see is to calculate the expected 'position increase' for a single card per shuffle (I feel this would be different for each card depending on its position) and find a summation until the bottom card has a 1/52 chance of rising to the top. I hope there is a more elegant solution.


  • 0

#8 kingofpain

kingofpain

    Advanced Member

  • Members
  • PipPipPip
  • 354 posts
  • Gender:Male

Posted 28 May 2013 - 03:04 PM

Spoiler for I will answer a different question to the my interpretation above:

Cheers!


  • 0

#9 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1664 posts
  • Gender:Female

Posted 28 May 2013 - 03:32 PM

Spoiler for I will answer a different question to the my interpretation above:


For a ripple shuffle, it would take more than two shuffles to gurantee a random situation (every possible orientation of cards) is possible
Cheers!


  • 0

#10 kingofpain

kingofpain

    Advanced Member

  • Members
  • PipPipPip
  • 354 posts
  • Gender:Male

Posted 28 May 2013 - 07:06 PM

Spoiler for buy that cry tea rear...

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users