牌堆游程期望

牌堆中的 run

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

Consider a standard deck with 52 cards; 26 red and 26 black. A run is a maximum contiguous block of cards of the same color. For example, $(R, B, R, B, \ldots , R, B)$ has 52 runs; while $(R, R, \ldots , R, B, B, \ldots , B)$ has 2 runs. What is the expected number of runs in a shuffled deck of cards?

解析

令 $F_j$ 表示第 $j$ 张牌是否为一个新游程的开始（ $F_1\equiv 1$ ；对 $j\ge 2$ ，当且仅当颜色与前一张不同）。

游程数 $N=\sum_{j=1}^{52}F_j$ ，因此

\mathbb{E}[N]=1+\sum_{j=2}^{52}\mathbb{P}(C_j\ne C_{j-1}).

对 $j\ge 2$ ：

\mathbb{P}(C_j\ne C_{j-1})=2\cdot \frac{26}{52}\cdot\frac{26}{51}=\frac{26}{51}.

所以

\boxed{\mathbb{E}[N]=1+51\cdot\frac{26}{51}=27}.