转弯次数

Number of Turns

专题: Probability / 概率
难度: L4
来源: OpenQuant

题目详情

假设你有一副牌，共有 20 张牌，其值范围为 1 - 10。每张牌在牌堆中恰好出现两次。你一次从 20 张牌中均匀随机抽取 2 张牌。如果它们的价值匹配，你可以将它们从牌组中删除。否则，它们会被放回甲板上。一旦没有更多的牌可抽，游戏就结束。每抽两张牌就是一个回合。求完成游戏所需的预期回合数。

Suppose you have a deck of 20 cards with values ranging from 1 - 10. Each card appears in the deck exactly twice. 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.

解析

设 $T$ 为游戏的总持续时间。我们将把它推广到 $n$ 卡对。然后： $T = T_1 + T_2 + ... + T_n$ ，其中 $T_i$ 是从 $i-1$ 对抽取到 $i$ 对抽取所需的抽取数量。通过期望的线性： $E[T] = \sum_{i=1}^n E[T_i]$ 接下来我们需要找到 $E[T_i]$ 。如果已经抽取了 $i-1$ 对，则牌堆中还剩下 $2n - 2(i-1) = 2(n-i+1)$ 卡。对于每张图画，固定第一张卡片。 $P(\text{second matches first}) = \frac{1}{2(n-i+1)-1}$ 因为在抽出第一张牌后还剩下 $2(n-i+1)-1$ 卡，并且只有一张牌与第一张牌的值相同。因此，由于这在试验之间是独立的： $T_i \sim Geom(\frac{1}{2(n-i+1) -1})$ E[T_i] = 2(n-i+1)-1 $E[T] = \sum_{i=1}^{n} (2(n-i+1)-1)$ E[T] = \sum_{i=1}^n(2i-1) $E[T] = n^2$ 由于我们有 10 个可能的卡值（即 $n=10$ ），因此答案是 $100$ 。

Original Explanation

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 + ... + 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:

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

Next we need to find $E[T_i]$ . 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.

P(\text{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 the first card. Therefore, as this is independent between trials:

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

E[T_i] = 2(n-i+1)-1

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

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

E[T] = n^2

Since we have 10 possible card values (i.e $n=10$ ) the answer is $100$ .