1
$\begingroup$

A deck of 52 cards. Every time you take out the card on the top and insert it back to the deck randomly. What's the expected time you need until the card originally at the bottom comes to the top?

I considered approaching this with a Markov Chain setup, where the states are the number of cards below the bottom card. Originally we have 0, when we see the bottom card we have 51 cards below it. At first there is only 1/51 chance of us adding a card below the bottom card but it grows by 1/51 each time we succeed. However I am not sure how to approach this chain without having to solve a massive simultaneous equation with expected hitting times.

Another extension I considered is this. When you start you remember the top card, it is now special, you shuffle it into the deck. Then every turn you keep taking the top card and shuffling it into the deck, same as before. What is the expected number of turns until you see the original special card again?

$\endgroup$
2
  • $\begingroup$ YOu expect it to take $51$ tries before it moves up $1$ in rank. Then, the probability of the top card being re-inserted below it, is $\frac 2{51}$, so you expect it to take $\frac {51}2$ tries to get it to move up $1$ in rank. And so on. $\endgroup$
    – lulu
    Commented Nov 5, 2023 at 21:08
  • $\begingroup$ Why do you say $\frac1{51}$ rather than $\frac1{52}$? Can you not put the card back on top? $\endgroup$
    – Henry
    Commented Nov 6, 2023 at 2:23

1 Answer 1

1
$\begingroup$

Importantly, note that a card cannot decrease in height. If $\tau_i$ is the hitting time for the card $i^{\text{th}}$ from the top to reach the top, then you want $\mathbb E(\tau_{51})$. Use $\tau_0\equiv 0$ and the recurrence $$\mathbb E(\tau_i)=1+\frac{i}{52}\mathbb E(\tau_{i-1})+\frac{52-i}{52}\mathbb E(\tau_i)$$ to represent the two possibilites on each round. This simplifies to $\mathbb E(\tau_i)=\frac{52}{i}+\mathbb E(\tau_{i-1})$, which can be solved with a summation.

A nice side effect of formalizing this approach is that the follow-up question is simply asking for $\mathbb E(\tau_I\mid I)$, where $I$ is discrete uniform over $\{0,\ldots, 51\}$. More simply, this is $\frac{1}{52}\sum_{i=0}^{51}\mathbb E(\tau_i)$.

$\endgroup$
1
  • $\begingroup$ Thank you very much, this approach does generalize extremely well. $\endgroup$
    – AlexS123
    Commented Nov 6, 2023 at 0:09

You must log in to answer this question.

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