Turning cards

A medium level probability question asked in Jane Street Interview for Quant Strategist

Suppose you have 20 cards with the values 1 - 10 each appearing twice in a deck. You draw 2 cards at a time uniformly at random from the 20 cards. If they match in value, you remove them from the deck. Otherwise, they are put back into the deck. The game finishes once there are no more cards to draw. Each drawing of two cards is a turn. Find the expected number of turns needed to finish the game.

Try to solve this problem yourself before moving on to the solution below

.
.
.

.

.

.

---

Solution

Let T be the total duration of the game. We are going to generalize this to n pairs of cards. Then

\(T = T_1 + T_2 + \cdots + T_n\)

where T_i is the amount of draws needed to go from i - 1 pairs drawn to i pairs drawn.

By linearity of expectation.

\(\mathbb{E}[T] = \sum_{i=1}^{n} \mathbb{E}[T_i]\)

We need to find E[T_i] now. If i - 1 pairs are already drawn, then there are 2n - 2(i - 1) = 2(n - i + 1) cards left in the deck. For each drawing, fix the first card.

\(\text{P (second matches first) }=\frac{1}{2(n - i + 1) - 1}\)

as there are 2(n - i + 1) - 1 cards left after the first of the pair is drawn, and only 1 of the cards is the same value as first card.

Therefore, as this is independent between trials

\( T_i \sim \text{Geom}\left(\frac{1}{2(n - i + 1) - 1}\right)\)

\( \mathbb{E}[T_i] = 2(n - i + 1) - 1\)

\(\mathbb{E}[T] = \sum_{i=1}^{n} \left(2(n - i + 1) - 1\right) \)

\(\mathbb{E}[T] = \sum_{i=1}^{n} \left(2i - 1\right)\)

E[T] = n^2

In particular, n = 10 here, so the answer is 100.

.

.

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!