Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Problem: Given a standard deck of $52$ cards, extract 26 of the cards at random in one of the $52 \choose{26}$ possible ways and place them on the top of the deck is the same relative order as they were before being selected. What is the expected number of cards that now occupy the same position in the deck as before?

This nice problem is due to Jim Propp.

share|cite|improve this question

The top card remains if it is selected, probability $\frac {26}{52}$. The second remains if both the top two are selected, probability $\frac {26 \cdot 25}{52 \cdot 51}=\frac {(52-2)!26!}{52!(26-2)!}$ and so on through the first $26$ cards-we have the top $n$ in place with probability $\frac {(52-n)!26!}{52!(26-n)!}$. Counting up from the bottom is the same-card $52-m$ is in place if all the cards from $52-m$ through $52$ were not selected, with probabilty $\frac {(52-m)!26!}{52!(26-m)!}$. So the expected number is $2\sum_{n=1}^{26}\frac {(52-n)!26!}{52!(26-n)!}=\frac {52}{27}\approx 1.926$

share|cite|improve this answer
1  
I'm not sure this is exact, as there is correlation between the cards selected and the cards not selected. – Ross Millikan Oct 30 '12 at 12:57
    
Yes, it's exact; the correlations don't matter because of the linearity of expectation. But you've got an extra factor of $n$; you should just be adding up the indicator variables themselves. The result is $$ 2\sum_{n=1}^{26}\frac{\binom{26}n}{\binom{52}n}= \frac{2\cdot26}{26+1}=\frac{52}{27}\approx1.926\;. $$ – joriki May 13 at 22:39
1  
@joriki: thanks. fixed. – Ross Millikan May 13 at 23:03

In a similar vein as Ross's answer, but with less calculation required: A card remains fixed at the bottom if it lies below all selected cards. Perform the selection by shuffling $26$ selected and $26$ unselected cards. By symmetry, the probability for $1$ unselected card to lie below all $26$ selected cards is $\frac1{27}$. There are $26$ unselected cards, so by linearity of expectation $\frac{26}{27}$ of them are expected to lie below all selected cards. The situation at the top is analogous, so the overall expectation is $\frac{52}{27}$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.