Shuffling a lot of cards

[CaptainEd]

The card game Hand and Foot requires one more deck than the number of players. Assume four people are playing, thus there are five decks of 54 cards each (2 jokers and 4 each of A,2,3,4,5,6,7,8,9,10,J,Q,K).

The result of a round of play is a discard pile that is EXTREMELY non-random, with many contiguous strings of identically denominated cards. So, after a round of play, all players shuffle the cards.

In fact, shuffling takes place in rounds. In one round, everybody shuffles a bunch of cards (in the example above, about 65 cards per player) several times, and then finally passes half the cards to the person at the right.

Let's not worry about how many times they have to shuffle in order to "randomize" their bunch of cards. My question is:

How many ROUNDS of shuffling does it take to randomize the cards, if we assume that they are able to randomize the cards in their bunch?

Subsidiary question: what fraction of cards should be passed? That is, is it optimal to pass half the cards, or is there a better fraction.

I don't have an answer to this question. I do know that we get tired of shuffling...

[EventHorizon]

I'll venture an initial guess for a good number of rounds to be twice the number of players, and I base this guess on absolutely nothing. Though players+1 seems like a good guess too.

Just curious, when would you call the decks randomized? It seems you could get to the state where every situation could occur, but they wouldn't all have the same probability of occurring (and it may be impossible to reach uniformly random regardless of the number of rounds).

That said, I'm thinking something like either 1/e or 1-(1/e) will be the optimal proportion of cards to pass (or maybe something like 1-(1/(e^p)) where p is the number of players).

Could the optimal proportion of cards change for each round? Like it is best to pass 1/2 the first time, then 1/3 etc.

Actually, it's hard to see a better proportion than 1/2 for 2 players as it maximizes the entropy. I'll think about this further...

Great Post

[Guest]

it seems to me that the best way would be to randomize with the passing phase. each player gets an initial set of cards, then deals them out to all other players including himself in a random fashion, such that he gives each player roughly the same number of cards. have all players do this simultaneously for maximum randomness. one round of this should be all that's required.

[CaptainEd]

EventHorizon, certainly more than a little flaw in the OP--what do I mean by randomized?

In this game, color and suit don't matter, only denomination. So randomization should result in a uniform distribution of each denomination in the deck. I realize this is still rather vague, sorry, but it's a clue.

Phillip1882, since my question focused on the concern about mixing the cards from one person with those of the next, I like your suggestion very much--your proposal separates contiguous cards across all the players immediately, in one (or each) passing round.

As an aside, for those who aren't familiar with Hand and Foot, the need to separate the cards is manifest in several of the pre-play activities. For one thing, after all players shuffled and passed, etc., ALL players deal, and they each deal two hands (of 13 cards). Then they pass them to their left and right neighbors (in two-hand, they pass one hand and keep the other).. Then the remaining undealt cards are put into two draw piles, and each person's turn starts by drawing one card from each draw pile.

I'm liking your discussions, folks, keep those cards and letters coming...

[Guest]

EventHorizon, certainly more than a little flaw in the OP--what do I mean by randomized?

In this game, color and suit don't matter, only denomination. So randomization should result in a uniform distribution of each denomination in the deck. I realize this is still rather vague, sorry, but it's a clue.

Phillip1882, since my question focused on the concern about mixing the cards from one person with those of the next, I like your suggestion very much--your proposal separates contiguous cards across all the players immediately, in one (or each) passing round.

As an aside, for those who aren't familiar with Hand and Foot, the need to separate the cards is manifest in several of the pre-play activities. For one thing, after all players shuffled and passed, etc., ALL players deal, and they each deal two hands (of 13 cards). Then they pass them to their left and right neighbors (in two-hand, they pass one hand and keep the other).. Then the remaining undealt cards are put into two draw piles, and each person's turn starts by drawing one card from each draw pile.

I'm liking your discussions, folks, keep those cards and letters coming...

With the concept of extreme non-random, then one shuffler could start with all cards of a particular denomination, say all 20 Aces. For a full randomization, he should reduce that number to 5 Aces by the end of the shuffling. I have not yet started calculating but seems that altering number passed each time will reduce the total number of passes required. With 5 aces needing to migrate to to fourth player, I see no way it can be accomplished in one round.

[Guest]

okay went ahead a wrote a program to explore this problem further.

got that with giving player half, it takes roughly 3.37 rounds for a good distribution.

surprisingly, keeping 1/2.718 seems to increase the number of rounds necessary to a solid 4.

with my method, i got a good distribution roughly 63% of the time.

Edited January 7, 2012 by phillip1882

[Guest]

From phillip1882's analysis, 3.37 rounds is 13 passes. I set up a spreadsheet to run different scenarios. Five decks of 54 cards each would be 67.5 cards each (for ease of formulas, I accepted the concept of a half card here). I ran the distribution of passing different numbers of cards and found that the best distribution after 13 passes was by passing 34 cards (here I did not use fractional cards) which was only slight improvement over 33 cards passed each time. I ran several variations and did get slight improvement by doing variations on number passed per round but have not found any with sufficient improvement to reduce the number of passes to 12 and achieve the same threshold of distribution.

[CaptainEd]

with my method, i got a good distribution roughly 63% of the time.

Let me make sure I understand your method. Here's my paraphrase:

divide the deck into n slabs, one per player.

each player deals his/her slab into 4 piles (by "deals", I assume you mean deals a card to each pile in turn, until all the cards are gone) [i realize you suggested dealing somewhat randomly, but I doubt that is necessary--dealing individual cards to different piles sounds powerful in separating the same-denomination runs]

each player distributes the piles to the 4 players (including self)

Then each player shuffles the cards in the 4 piles they now have.

And that's it.

Or do we do this more than once?

If doing this merely once does a good job, you're going to have a lot of friends at our house!

[CaptainEd]

From phillip1882's analysis, 3.37 rounds is 13 passes.

I fear that my sloppy use of language has done some damage.

By a "round" of shuffling, I meant that all players shuffle a while, then they all pass a fraction of their deck to the next player, simultaneously. So, I would think of 3.37 rounds as being 3.37 times when they all pass.

[Guest]

your correct on both points captain ed. your description is spot on (minus the random deal), and as i said, this seems to give a good distribution (each player having roughly the the same number of each card value +/- 10%) 63% of the time. (i only tested it with the case of 4 people, but i doubt that percentage will vary by much.)

so you may want to do 2 rounds of this to be sure. with the standard shuffle and pass, i got an average of 3.37 rounds. and if you think about it that makes sense. after shuffling, each player will have roughly half his cards and half the cards the opponent gave him mixed together, so after giving up half, he'll roughly have 1/4 his cards and 1/4 the cards from his opponent. (plus the new half of course.)

so my estimate for a general formula will be that you need to mix and pass roughly (number of players) -1

Edited January 7, 2012 by phillip1882

[Guest]

I fear that my sloppy use of language has done some damage.

By a "round" of shuffling, I meant that all players shuffle a while, then they all pass a fraction of their deck to the next player, simultaneously. So, I would think of 3.37 rounds as being 3.37 times when they all pass.

But the problem here is the worse case scenario. If 1 player starts with 20 aces, the expected distribution after 4 passes gives a range between 2.5 aces to 7.5 aces when passing 34 each time. If the aim is purely to shuffle the cards, then why not pass right, left and across the table? i.e. Visually divide all cards into four approxiamately equal piles. Everybody shuffles (minimum of 3 times), then each person, visually divides their pile into four approxiamately equal stacks and passes three to the other three palyers, shuffle (a minimum of 3 times). Then they should be randomized. My grandmothers method for shuffling two decks for canasta was to skatter cards across the table face down, then swirl them around and rake them in. Surprisingly fast and effective.

[CaptainEd]

The spectre of 20 aces in sequence is definitely a worst case scenario. I think your answer is similar to phillip1882's, namely to divide the cards among all the players. I'll bet you folks are right. Phillip goes a bit further, by actually dealing (ie. separating) the cards to the piles, and I think that addresses your worst case scenario.

I like the answers I've got. I'm going to advise dealing piles for all players. Not so clear how many rounds are necessary. If someone has some empirical or theoretical evidence telling how many rounds, I'd love to know it.

But I already have benefited a lot from your help.

Thank you all!