Expected position of a card in a deck after repeating a procedure - MathOverflow

Expected position of a card in a deck after repeating a procedure

2010-08-16T05:36:16Z

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

Answer by Dan Brumleve for Expected position of a card in a deck after repeating a procedure

2010-08-16T05:43:30Z

Asymptotically the distribution of the location of the King of Hearts is uniform. For a small number of iterations I guess this is a representation theory question?

Answer by little_probabilist for Expected position of a card in a deck after repeating a procedure

2010-08-16T05:52:00Z

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

Answer by Peter Shor for Expected position of a card in a deck after repeating a procedure

2010-08-20T23:25:00Z

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