4
$\begingroup$

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.

2 Answers 2

2

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$

  • 1
    @joriki: thanks. fixed.2016-05-13
2

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}$.