Expected number of cards fixed in a deck after a certain operation

674 Views Asked by At

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.

1

There are 1 best solutions below

7
On

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$