Shuffling a Deck of Cards

[BMAD]

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

[phil1882]

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

[BMAD]

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

[superprismatic]

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".

[BMAD]

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?

[Quantum.Mechanic]

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.

[kingofpain]

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.

[kingofpain]

If random implies that there is a non-zero probability of finding any given card at the top of the pile (or at any position), then the answer would be that this takes minimum of 2 shuffles. The first shuffle would be where the bottom card ends up in position 27. and the second shuffle where it gets shuffled in to the deck last. With 2 shuffles, I posit that there is a non-zero possibility for any card to have any position. In other words, after 2 shuffles you cannot guarantee that a given position will not be a given card.

Cheers!

[BMAD]

If random implies that there is a non-zero probability of finding any given card at the top of the pile (or at any position), then the answer would be that this takes minimum of 2 shuffles. The first shuffle would be where the bottom card ends up in position 27. and the second shuffle where it gets shuffled in to the deck last. With 2 shuffles, I posit that there is a non-zero possibility for any card to have any position. In other words, after 2 shuffles you cannot guarantee that a given position will not be a given card.

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

Cheers!

[kingofpain]

if by truly random, you mean every configuration possible, then I would say the answer is 52 log 2 riffle shuffles (which gives me 6? this would be kinda like merge sort in reverse).

[phil1882]

instead of 52 cards, let's try 10.

for 10 cards, if you break them in half and then perform the ripple shuffle,

the top card could be anywhere from the top of the deck to the half way point (the 5th card.)

however, ending at the half way point would be the worst case senario, as when you cut to shuffle again, the middle card is on top again.

my guess then would be 3. once to get the top card close to the mid point, another to get it a good distance toward the bottom, and then a third to finish the possible transition.

[kingofpain]

Will take 2 shuffles. One to bring it to position 5. The second to bring it to the bottom. Not sure why you need the third shuffle...?

phil1882, on 28 May 2013 - 11:37 PM, said:

instead of 52 cards, let's try 10.
for 10 cards, if you break them in half and then perform the ripple shuffle,
the top card could be anywhere from the top of the deck to the half way point (the 5th card.)
however, ending at the half way point would be the worst case senario, as when you cut to shuffle again, the middle card is on top again.

my guess then would be 3. once to get the top card close to the mid point, another to get it a good distance toward the bottom, and then a third to finish the possible transition.

[Prime]

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?

I came to know that shuffle by the name “perfect shuffle.” Of course, you should start dropping the cards from the top half, so that the top card does not end up in the same position after the shuffle.

I wouldn't call that shuffle “random.” For a deck of 52, it takes 26 perfect shuffles to put it in exact reverse order and 52 shuffles total to return the deck to its original state.

For the powers of 2, the number of perfect shuffles required to return a deck into its original state is logarithm base 2.

E.g., a popular Russian game Proferans (“preference”) is played with a deck of 32 cards. Thus it takes only 5 perfect shuffles to return it to the starting order. I've met some gamblers who spent years practicing (while serving their jail sentences) to be able to make that shuffle every time.

In your favorite spreadsheet application, fill column “A” with numbers 1 through 52. Fill 52 cells in column “B” with formulas: =A27, =A1, =A28, =A2,... and so on. Select column “B” and drag it over the next 51 columns. You got all 52 permutations of perfect shuffles for a deck of 52 cards. If you know the starting order and the number of shuffles, you can tell the exact sequence of cards. What randomness is in that?

Conversely, I've read somewhere that you need at least 7 riffle shuffles to randomize the deck.

[kingofpain]

perfect shuffle is when the cards are dropped perfectly alternately. riffle shuffle is where the probability of dropping the next card depends on the size of the remaining undropped deck on that size.

[BMAD]

if by truly random, you mean every configuration possible, then I would say the answer is 52 log 2 riffle shuffles (which gives me 6? this would be kinda like merge sort in reverse).

on the right track

[Xavier]

on this subject: check

for a discussion by Persi Diaconis, Professor of Statistics at Stanford. I guess it's a spoiler so do not click if you do not want the answer!

Also if you are intrested, check the discussion on a backgammon site: http://www.bgonline.org/forums/webbbs_config.pl?frames;read=142087

[bonanova]

Wolfram suggests seven gets you very close. Theoretically, (3/2) ln 52.

Once you require a "perfect" shuffle, the only randomness is the choice of in-shuffle or out-shuffle (where top and bottom cards never move.) Every card moves to a known position, and all you do is calculate whether a particular permutation of the first 52 integers is random.

I'm interested to think what happens when the shuffle itself is random -- anything from "perfect riffle" to cutting the deck at a random card, thus interleaving any number of cards from 1 to 51. A single shuffle could then put the bottom card on top, or vv. You could assign a distribution of probabilities governing what happens, but that is all.

[superprismatic]

If a deck of 52 cards is cut exactly in half (top half and bottom half),

then the top half can be partitioned into T segments (keeping the order

of the cards) and, similarly, the bottom half can be partitioned into B

segments. If T=B then there are two ways to interleave these partitions

of cards -- dropping segments of cards alternately from T and B, beginning

with T (the first way) or beginning with B (the second way). If T=B+1,

then there is only one way to interleave the segments -- one must begin

with T. If T+1=B, one must begin with B. Any other relationship between

T and B make them impossible to interleave. We can count the number of

partitions of 26 in all possible arrangements, they are:

#partitions of 26; #of ways to make partitions of this number respecting order

1 1

2 25

3 300

4 2300

5 12650

6 53130

7 177100

8 480700

9 1081575

10 2042975

11 3268760

12 4457400

13 5200300

14 5200300

15 4457400

16 3268760

17 2042975

18 1081575

19 480700

20 177100

21 53130

22 12650

23 2300

24 300

25 25

26 1

We can now count all possible T,B pairs where T and B are at most one

apart. This gives us a grand total of 374,369,872,911,804 possible

riffle shuffles of 52 cards. Considering that 52! is the enormous

80658175170943878571660636856403766975289505440883277824000000000000,

I can't see how to show that there is some number, N, of riffle shuffles

such that one can always produce any particular permutation of the 52!

by applying at most N riffle shuffles to the identity permutation.

[BMAD]

It takes just seven shuffles.

the long drawn out explanation is here http://stevereads.com/papers_to_read/trailing_the_dovetail_shuffle_to_its_lair.pdf