序列终止器

Sequence Terminator

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

个人笔记

题目详情

反复掷一枚公平六面骰，形成一个“当前序列”，规则如下：

若掷到偶数（2/4/6），把该点数加入当前序列。
若掷到 3 或 5，则清空当前序列，并且 3/5 不会作为新序列的起始元素（即直接丢弃）。
若掷到 1，则把 1 加入当前序列并立刻结束游戏。

求：游戏结束时序列长度的期望值。

例如掷出序列 34265241：第一次掷到 3 会清空；掷到 5 也会清空；最终序列为 241，长度为 3。

英文原题

A fair $6-$ sided die is rolled repetitively, forming a sequence of values, under the following rules: If any even value is rolled, add it to the current sequence. If a $3$ or $5$ is rolled, discard the entire sequence and don't add the $3$ or $5$ to the start of the new sequence. If a $1$ is rolled, add the $1$ to the current sequence and end the game. Find the expected length of the sequence at the end of the game.

For example if the sequence of rolls is $34265241$ , we would reset to an empty sequence at the first roll, reset to an empty sequence at the $5$ , and our final sequence would be $241$ , which is of length $3$ .

解析

设 $E_\ell$ 为“当前序列已有长度为 $\ell$ ”时，最终结束序列长度的期望。

一次掷骰的转移：

掷到 1（概率 $1/6$ ）：结束，最终长度为 $\ell+1$ 。
掷到 2/4/6（概率 $3/6$ ）：序列长度变为 $\ell+1$ 。
掷到 3/5（概率 $2/6$ ）：清空序列，回到 $\ell=0$ 。

因此对任意 $\ell\ge 0$ ：

E_\ell=\frac{1}{6}(\ell+1)+\frac{3}{6}E_{\ell+1}+\frac{2}{6}E_0.

设解为线性形式 $E_\ell=\alpha\ell+\beta$ ，代入得 $\alpha=\frac{1}{3}$ ，并且 $\beta=2$ （注意 $E_0=\beta$ ）。

所以初始期望为

\boxed{E_0=2}.

英文解析

If $E_\ell$ is set to "The current sequence already has a length of $\ell$ ", the final sequence length is expected.

Transfer of one roll:

Throw to 1 (probability $1/6$ ): Ends with a final length of $\ell+1$ .
Throw to 2/4/6 (probability $3/6$ ): the sequence length changes to $\ell+1$ .
Throw to 3/5 (probability $2/6$ ): Empty the sequence and go back to $\ell=0$ .

So for any $\ell\ge 0$ :

E_\ell=\frac{1}{6}(\ell+1)+\frac{3}{6}E_{\ell+1}+\frac{2}{6}E_0.

Solved as a linear form $E_\ell=\alpha\ell+\beta$ , substituted $\alpha=\frac{1}{3}$ , and $\beta=2$ (note $E_0=\beta$ ).

So the initial expectation is

\boxed{E_0=2}.