假设
是取值在)
上的随机变量，对于一个实数)
，令其二进制展开为
，其中
对每个
。
这里，二进制展开是唯一的，因为我们规定不存在
使得对所有的
都有
。对每个
令
，
即
的最初
位展开。如上定义随机过程_%7B%7Bs%7D%5Cin%5Cmathbb%7BN%7D%7D)
，即逐渐读取Y的二进制展开。注意到
当
（点点收敛）。对一个严格增函数![g:[-1,1]\to\mathbb{R}](https://math.jianshu.com/math?formula=g%3A%5B-1%2C1%5D%5Cto%5Cmathbb%7BR%7D)
，定义随机过程_%7B%7Bs%7D%5Cin%5Cmathbb%7BN%7D%7D%3A%3D(g(Y_s))_%7B%7Bs%7D%5Cin%5Cmathbb%7BN%7D%7D)
。假设_%7B%7Bs%7D%5Cin%5Cmathbb%7BN%7D%7D)
是一个关于其自然
代数族的鞅。
证明存在常数
和
使得
![\mathbb{E}[{(X_s-g(Y))}^2]≤{Cr}^s](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B%7B(X_s-g(Y))%7D%5E2%5D%E2%89%A4%7BCr%7D%5Es)
对所有的
。
(数值0.9并非最优。)
提示：你可以尝试证明并使用以下结果：假设
并且正实数
满足
对于
；
对于
。
则存在使得
。
证：
设_%7Bs%20%5Cgeq%200%7D)
是一个鞅，且)
是在
之后的可测函数。我们目标是证明![\mathbb{E}[(X_s - g(Y))^2] \to 0](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20g(Y))%5E2%5D%20%5Cto%200)
当
。
1: 误差平方的期望推导
首先，我们利用鞅的性质，考虑以下期望：
![\mathbb{E}[(X_s - g(Y))^2] = \mathbb{E}[(X_s - X_{s+1})^2] + \mathbb{E}[(X_{s+1} - g(Y))^2] + 2\mathbb{E}[(X_s - X_{s+1})(X_{s+1} - g(Y))]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20g(Y))%5E2%5D%20%3D%20%5Cmathbb%7BE%7D%5B(X_s%20-%20X_%7Bs%2B1%7D)%5E2%5D%20%2B%20%5Cmathbb%7BE%7D%5B(X_%7Bs%2B1%7D%20-%20g(Y))%5E2%5D%20%2B%202%5Cmathbb%7BE%7D%5B(X_s%20-%20X_%7Bs%2B1%7D)(X_%7Bs%2B1%7D%20-%20g(Y))%5D)
由于
是鞅且是在之后的可测函数，故有：
![\mathbb{E}[(X_s - X_{s+1})(X_{s+1} - g(Y))] = 0](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20X_%7Bs%2B1%7D)(X_%7Bs%2B1%7D%20-%20g(Y))%5D%20%3D%200)
因此，我们可以简化为：
![\mathbb{E}[(X_s - g(Y))^2] = \mathbb{E}[(X_s - X_{s+1})^2] + \mathbb{E}[(X_{s+1} - g(Y))^2]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20g(Y))%5E2%5D%20%3D%20%5Cmathbb%7BE%7D%5B(X_s%20-%20X_%7Bs%2B1%7D)%5E2%5D%20%2B%20%5Cmathbb%7BE%7D%5B(X_%7Bs%2B1%7D%20-%20g(Y))%5E2%5D)
2: 利用提示不等式的条件
我们设定：
我们希望证明
。由于)
是鞅，利用 Doob 的鞅收敛定理，可以得到![\mathbb{E}[X_s^2]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BX_s%5E2%5D)
是有界的，记![K = \sup_s \mathbb{E}[X_s^2] < \infty](https://math.jianshu.com/math?formula=K%20%3D%20%5Csup_s%20%5Cmathbb%7BE%7D%5BX_s%5E2%5D%20%3C%20%5Cinfty)
。
3: 收敛性及常数
的确定
结合之前的结果，我们得到：
![\mathbb{E}[(X_s - g(Y))^2] \leq \mathbb{E}[(X_s - X_{s+1})^2] + \max\{b_s, a_s\}](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20g(Y))%5E2%5D%20%5Cleq%20%5Cmathbb%7BE%7D%5B(X_s%20-%20X_%7Bs%2B1%7D)%5E2%5D%20%2B%20%5Cmax%5C%7Bb_s%2C%20a_s%5C%7D)
由于是鞅，可以找到一个常数使得对于所有，
![\mathbb{E}[(X_s - X_{s+1})^2] \leq C](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20X_%7Bs%2B1%7D)%5E2%5D%20%5Cleq%20C)
因此，有：
![\mathbb{E}[(X_s - g(Y))^2] \leq C + \max\{b_s, a_s\}](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20g(Y))%5E2%5D%20%5Cleq%20C%20%2B%20%5Cmax%5C%7Bb_s%2C%20a_s%5C%7D)
综上，由于
和
都是有界的，且![\mathbb{E}[(X_s - g(Y))^2]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B(X_s%20-%20g(Y))%5E2%5D)
的上界是有限的，因此随着，我们可以得出：
这就证明了。
