返回题库

弹珠游程数

Marble Runs

专题
Algorithmic Programming / 算法编程
难度
L6

题目详情

袋中有 50 个红球和 50 个蓝球，不放回随机抽取直到抽完，并记录颜色序列。

定义“游程（run）”为任意长度的连续同色段。例如 RBBRRRBRRRBBRRRBRR 有 5 个游程。

求游程总数的期望。

英文原题

You repeatedly draw marbles from a bag containing 50 red and 50 blue marbles until there are no more marbles left, recording the order of red and blue marbles drawn. You then count the number of "runs," where a run is defined as any number of consecutive marbles of the same color. For example, RBBRRRBRRRBBRRRBRR contains 5 runs. What is the expected number of runs that you observe?

解析

设总游程数为

R=1+∑i=199Ii,R=1+\sum_{i=1}^{99} I_i,

其中 IiI_i 表示第 ii 与第 i+1i+1 个球颜色不同的指示变量。

于是

E[R]=1+∑i=199E[Ii]=1+99 P(相邻异色).\mathbb{E}[R]=1+\sum_{i=1}^{99}\mathbb{E}[I_i]=1+99\,P(\text{相邻异色}).

随机排列下，任意相邻两位置异色概率为

2⋅50⋅50100⋅99=5099.\frac{2\cdot 50\cdot 50}{100\cdot 99}=\frac{50}{99}.

因此

E[R]=1+99⋅5099=51.\mathbb{E}[R]=1+99\cdot\frac{50}{99}=51.

答案为 51\boxed{51}。

英文解析

Let the total number of strokes be

R=1+∑i=199Ii,R=1+\sum_{i=1}^{99} I_i,

Of these, IiI_i represents the indicator variable that the color of the ball ii differs from that of the ball i+1i+1.

as a result

E[R]=1+∑i=199E[Ii]=1+99 P(adjacent colors differ).\mathbb{E}[R]=1+\sum_{i=1}^{99}\mathbb{E}[I_i]=1+99\,P(\text{adjacent colors differ}).

Randomly arranged, the heterochromatic probability of any two adjacent positions is

2⋅50⋅50100⋅99=5099.\frac{2\cdot 50\cdot 50}{100\cdot 99}=\frac{50}{99}.

Therefore,

E[R]=1+99⋅5099=51.\mathbb{E}[R]=1+99\cdot\frac{50}{99}=51.

The answer is 51\boxed{51}.