关于2022年Putnam竞赛A4题Solution 1中条件期望表达式的推导疑问

我来帮你拆解这个条件期望的推导逻辑，核心是抓住停止时间的递归性和序列的独立性这两个关键点：

首先，当给定$X_1=u$且$u \leq x$时，$1_{X_1 \leq x}=1$，所以我们其实是在计算$E[S \mid X_1=u]$，对应回原式即可。

先回忆$S$的定义：$S = \frac{X_1}{2} + \frac{X_2}{2^2} + \dots + \frac{X_k}{2^k}$，其中$k$是第一个满足$X_{n+1}>X_n$的$n$。当$X_1=u$时，我们分两种情况分析$X_2$：

1. 如果$X_2 > u$：那$k=1$，后面的求和项直接为0，此时$S=\frac{u}{2}$，这就是你已经理解的部分。
2. 如果$X_2 \leq u$：这时候“游戏还没结束”，我们可以把剩下的求和项提取一个$\frac{1}{2}$出来，写成：
   $$\frac{X_2}{2^2} + \frac{X_3}{2^3} + \dots + \frac{X_k}{2^k} = \frac{1}{2} \left( \frac{X_2}{2^1} + \frac{X_3}{2^2} + \dots + \frac{X_k}{2^{k-1}} \right)$$
   注意到，此时剩下的部分相当于从$X_2$开始重新玩一遍原问题的游戏：新的停止时间$k' = k-1$（因为$X_2 \leq u$，原$k$至少是2），新的和就是基于序列$X_2,X_3,\dots$的$S'$。由于序列是独立同分布的，$S'$的分布和原$S$完全一致，但有个前提：新的“第一个变量”$X_2 \leq u$，所以这个$S'$的期望就是$E[S \mid X_1 \leq u]$。

接下来用概率加权合并两种情况：

• $X_2 > u$的概率是$1-u$，对应贡献为$(1-u) \times 0$；
• $X_2 \leq u$的概率是$u$，对应贡献为$u \times E[S \mid X_1 \leq u]$；

把这部分代入到$E[S \mid X_1=u]$的计算里：
$$
\begin{align*}
E[S \mid X_1=u] &= \frac{u}{2} + \frac{1}{2} \times \left[ (1-u) \times 0 + u \times E[S \mid X_1 \leq u] \right] \
&= \frac{u}{2} + \frac{1}{2} \times E[S \cdot 1_{X_1 \leq u}]
\end{align*}
$$
这里最后一步是因为$E[S \cdot 1_{X_1 \leq u}] = P(X_1 \leq u) \times E[S \mid X_1 \leq u] = u \times E[S \mid X_1 \leq u]$，刚好抵消掉前面的$u$，就得到了Solution 1里的表达式。

备注：内容来源于stack exchange，提问作者Calculon