红黑连段数

Colored Runs of Cards

专题: Probability / 概率
难度: L6
来源: Brainstellar

题目详情

一副标准扑克牌有 26 张黑牌（B）和 26 张红牌（R）。把洗牌后的序列按颜色分块，连续同色的一段称为一个 run（连段）。

例如序列 RRRRBBBRBRB（只写颜色）共有 6 个 run：RRRR、BBB、R、B、R、B。

问：随机洗牌后，run 的期望数量是多少？

提示：期望的线性性。

There are 26 black(B) and 26 red(R) cards in a standard deck. A run is number of blocks of consecutive cards of the same color. For example, a sequence RRRRBBBRBRB of only 11 cards has 6 runs; namely, RRRR, BBB, R, B, R, B. Find the expected number of runs in a shuffled deck of cards.

Hint

Linearity of expectation

解析

答案是 27。

把 run 数写成指示变量之和：第 1 张一定开启一个 run，之后每当相邻两张颜色不同，就会多出一个 run。

因此

E[\text{runs}]=1+\sum_{i=2}^{52}P(X_i\ne X_{i-1}).

对任意相邻位置，颜色不同的概率为 $\frac{26}{51}$ ，于是

E=1+51\cdot\frac{26}{51}=27.

Original Explanation

Solution

We form the answer for general deck of 2n cards, with n red cards and n black cards. Consider any sequence X1,X2..X2n (of R & B). Now define Y1 = 1; Yi = 1 if Xi and X(i-1) are of different colors Yi = 0 otherwise.

We want to find E[Y1 + ..+ Y2n], using linearity of expectation, = E(Y1) +...+E(Yn). Now note that, E[Y1] = 1 and E[Yi] = E[Yj] for the rest (by symmetry)

Also E[Yi] = E(Y2) = P(X2 is diff from X1) = (number of ways first two are RB or BR) / (Total number of orientations) = 2 * [ (2n-2)choose(n-1) ] / [ 2n choose n ] = n/(2n-1)

Ans = 1+(2n-1) * E[Y_i] = n+1

This is 27 for deck of 52 cards.