题目

前几天做作业，做到这么一个题：

现在有一个 6 面的公平骰子，每一面标号为 1 到 6，我们一直投这个骰子，直到出现 6 就停。Conditioned on 投出来的数都是偶数，期望要投多少次？

看完题后的第一想法，既然每一次都只能是偶数，也就是只能出现 $\{2,4,6\}$，且出现 6 就停，那么答案就是 $3$ 咯。

后来我和我室友 @lsx bibi 的时候，他说答案不是 3……心里一惊，咋就不是 3 了呢？

大力算

……既然双方不能达成共识，那我们就大力算吧。首先我们考虑最原始的做法，即直接按照定义算。令概率空间 $U$ 为 $[6]^*$ 所有无限长的字母表为 $[6]$ 的字符创。令 $\mathcal{E}$ 表示第一个 6 出现之前都是偶数这个事件，有

$$\Pr[\mathcal{E}] = \frac{1}{6} \times \left (1 + \frac{1}{3} + \left( \frac{1}{3}\right)^2 + \cdots \right) = \frac{1}{4}.$$

令 $f(x)$ 为字符串 $x$ 中第一个 6 出现的位置，直接代入定义有：

$$\mathbb{E}_X[f(X) | \mathcal{E}] = \frac{1}{\Pr[\mathcal{E}]} \int_{x \in \mathcal{E}} \Pr[X = x] f(x) \mathrm{d} x = 4 \times \frac{1}{6} \times \sum_{i=1} \left( \frac{1}{3} \right)^{i-1} i = \frac{3}{2}.$$

……还真不是 $3$ 啊，有点违背我直觉。

新游戏

更加有趣的是，如果这不是一个 6 面的骰子呢？我们把游戏改为：投一个 $n \geq 6$ 面的骰子，出现 6 停止。Conditioned on 之前投出来的都是 $\{2, 4, 6\}$ 中的数，期望要投多少次呢？

这个新问题是很好算的，直接根据上面计算照喵画虎照葫芦画瓢 画蛇添足 重新算一下就好了。得到的答案居然是一个和 $n$ 相关的数：$\frac{n}{n - 2}$.

思考一下，为啥会是这么一个数？

新解释

其实上面这个数给了我们很强的启发了：

$$\frac{n}{n - 2} = \frac{1}{1 - \frac{2}{n}} = 1 + \frac{2}{n} + \left( \frac{2}{n} \right)^2 + \cdots$$

这个数描述的：我们每一步有 $\frac{2}{n}$ 的概率停止，停止时的期望步数。如何证明这个新的期望和我们游戏期望步数一样呢？

进一步观察发现：在这个游戏中，$6$ 和所有非 $2$ 非 $4$ 的数是等价的。即，Conditioned on 之前投出来的数都是 $\{2, 4\}$ 中的数，出现 6 停下的期望步数和出现 5 停下的期望步数应该是一样的。那么，在 $U$ 内随机一个 $x$，如果出现任何一个非 $2$ 非 $4$ 的数都停下来，则这个时候任何非 $2$ 非 $4$ 的数出现的概率是相等的。定义随机变量 $Y$ 为 $X$ 第一个出现非 $2$ 非 $4$ 的位置，我们有

$$\mathbb{E}_X[f(X) | \mathcal{E}] = \frac{\mathbb{E}_X[f(X) \mathbb{I}[X \in \mathcal{E}]]}{\Pr[\mathcal{E}]} = \frac{1}{\Pr[\mathcal{E}]} \mathbb{E}_Y[\mathbb{E}_X[f(X) \mathbb{I}[X \in \mathcal{E}] |Y]].$$

注意到 conditioned on $Y$，$f(X) = Y$ 且 $\mathbb{I}[X \in \mathcal{E}]$ 和 $Y$ 是独立的，故

$$\mathbb{E}_X[f(X) | \mathcal{E}] = \frac{1}{\Pr[\mathcal{E}]} \mathbb{E}_Y[Y \Pr[X \in \mathcal{E} | Y]] = \mathbb{E}_Y[Y \Pr[X \in \mathcal{E}]] = \mathbb{E}_Y[Y] = \frac{n}{n - 2}.$$

---

更新

这文章发了很久了，之前我的学弟 yml 跟我说我算错了，后来我好像又在哪里看到一篇 blog ，算了一通也和我不是一个数。我就不明白了，为啥我两种方法都算错了？？？当时还码了个代码算的，怎么还是错了？？？

我重新大力算了一遍：令 $p = \frac{n/2 - 1}{n}$，则

$$\sum_{i = 1} \frac{1}{n} p^{i-1} = \frac{1}{n(1 - p)},$$

又有

$$\sum_{i=1} \frac{1}{n} p^{i-1} i = \frac{1}{n(1-p)^2},$$

故答案即为 $\frac{1}{1 - p} = \frac{2n}{n + 2}$.

……好像确实是我算错了。我来看看我到底是怎么算错了！看了看我的新解释，突然发现我这次题目看错了 23333 这个新游戏是 conditioned on 之前投出来的数都是 $\{2, 4, 6\}$ 而不是之前投出来的数都是偶数。然后我又码了个小代码，发现确实是这样的：如果 conditioned on 偶数，那么答案是 $\frac{2n}{n+2}$；如果 conditioned on $\{2, 4, 6\}$，那么答案是 $\frac{n}{n-2}$。