1
$\begingroup$

Suppose you have a deck of 52 playing cards, fully shuffled, one of which is the King of Hearts. You perform this procedure: 1. Put the top three cards of the deck into a second pile. If there aren't three cards, put the rest of the deck into the pile. 2. If the King of Hearts in the second pile, shuffle the pile and the deck together.

What is the expected position of the King of Hearts in the deck after repeating this process an arbitrarily large number of times? What's the general approach to this problem with N cards in the deck and M cards revealed every time through?

(This actually came up as the result of a Magic: the Gathering scenario, but I assume that playing cards are more familiar.)

Improve this question
$\endgroup$
2
  • $\begingroup$ Why isn't the position of the KH completely uniform (among all the places it can currently be)? eg if the pile has 12 cards and the deck has 40 cards, and we know that the KH is in the deck not in the pile, then it is equally likely to be in any of the 40 possible positions. In fact, all 40! orderings of the deck are equally likely at this point -- we haven't revealed any information about their order since we last shuffled. If not, then I must be missing something. Does "shuffle the pile and the deck together" mean something other than "do a perfect shuffle of all the cards"? $\endgroup$
    – James Martin
    Commented Aug 16, 2010 at 9:06
  • $\begingroup$ Whether it's perfectly uniform depends on what you mean by shuffle. If you assume a shuffle mixes everything uniformly, then the question is meaningless. I'm assuming one idealized riffle shuffle in my estimate (see the answer below). $\endgroup$
    – Peter Shor
    Commented Aug 21, 2010 at 1:48

2 Answers 2

Reset to default
1
$\begingroup$

(This should probably be a comment, but I don't have that ability)

Just in case this isn't closed as 'too localized', it seems that you need a little bit more information here to turn this 'into math', but one can start somewhere. Lets say you start with the deck 'fully shuffled' (by which I mean all 52! orders equally likely). Bayes rule tells you that if you haven't seen the king yet, its expected distance from the top of the first pile is half the size of the first pile (and it is uniform in that first pile). This of course doesn't depend on m or n. Is this really the question you meant to ask? (EDIT: this is the same as James' comment above)

For the representation theory mention above: are you referring to e.g. the results on convergence to stationarity for random-transposition walks on $S_{n}$, or something entirely different that is e.g. useful even if the above process involves perfect shuffles? I'm sorry for the sidetrack, but always interested in hearing about other pieces of algebra that show up unexpectedly in probability.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Since the deck is being revealed three cards at a time, it makes the methods I'm familiar with less useful. (I edited the question to reflect that the deck begins fully shuffled.) $\endgroup$
    – Asher
    Commented Aug 16, 2010 at 6:00
1
$\begingroup$

Let me see if I understand the procedure. We have two piles, which I will call the deck and the pile. If KH is not in the pile, we pull three cards off the top of the deck and put them in the pile. If KH is in the pile, we riffle shuffle the deck and the pile together. I will assume the mathematically idealized riffle shuffle where the order of cards within the deck and the pile do not change, but all possible ways of shuffling them together with this constraint are equally likely.

Here's a heuristic answer to your question, assuming that I've understood the procedure right.

When we pull the cards off by threes, if the King of Hearts is the $k$th card down, we get roughly an average of $k+1$ cards in the second pile, assuming $k$ varies over a range which is substantially more than 3. The KH will be one of the top three cards in the pile when the pile and the rest of the deck are shuffled. It should be roughly equally likely to be any of the top three. Suppose that when they are shuffled, the expected number of cards in the pile is $P$, and in the deck is $52-P$. If you assume a riffle shuffle, and that there are exactly $P$ cards in the pile, then the expected number of cards above the King of Hearts after the shuffle is $2\frac{52-P}{P+1}+1$ (one card from the pile and $2\frac{52-P}{P+1}$ cards from the deck). We have the heuristic equation $$ P-1 =k = 2\frac{52-P}{P+1}+1$$ or $P \approx 9.8$.

One reason it's not exactly correct is that we can't average over $P$ if it's in the denominator. Another reason is that $k$ is probably too small to be equally likely to be one of the three residues mod 3. It shouldn't be hard to write a program to simulate this, if you want a more exact answer.

UPDATE: improved estimate slightly

Improve this answer
$\endgroup$
1
  • $\begingroup$ I looked up the rules for shuffling in Magic the Gathering tournaments, and it looks like the rules say 3 riffle shuffles (actually, they say at least three, but there are also time constraints, so I expect people end up doing exactly three). With these rules, if the KH starts in the middle of the deck, it's going to end up near the top, and if it starts near the top, it'll end up in a random place. A mathematical model for this might actually end up being an interesting dynamical system. $\endgroup$
    – Peter Shor
    Commented Aug 21, 2010 at 18:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .