Deep Mindの理論研究家であるTor Lattimoreが最近出した本Bandit Algorithmを輪読しています．ここではその練習問題の解答を上げていこうと思います．間違っているかもしれないので参考程度にお願いします．ミスがあったら，教えてくれると助かります．
今回はExercise 20.5．です．
本文中のLemma 20.3を証明せよという問いですが，ただの確率過程の問題と捉えて解けます．
Lemma 20.3は以下のような命題です．
hを\mathrm{R}^d上の確率測度とする．\bar{M}_t = \int_{\mathrm{R}^d}M_t(x)dh(x)が\mathrm{F}-adaptedで非負なスーパーマルチンゲールであり，\bar{M}_0 = 1であることを証明せよ．
ここで，M_t(x) = \exp(\langle x, S_t \rangle - \frac12 \|x\|_{V_t}^2)です．今回はS_tが具体的になんなのかということは必要なくM_t(x)がF-adaptedで，非負なスーパーマルチンゲールであることだけ使います．
証明
\bar{M}_t(x)が非負であることは，M_t(x)が非負であることから従います．
次に\bar{M}_tが\mathcal{F}_t-可測であることを示します．これはKallenbergのFoundation of Modern ProbabilityのLemma 1.26を使います．主張は，
二つの可測空間(S, \mathcal{S})，(T, \mathcal{T})があり，可測関数f: S \times T \rightarrow \mathrm{R}_+とS上の\sigma-有限な測度\muが存在するとします．このときf(s,t)は任意のt \in Tにおいて\mathcal{S}-可測であり，関数\mu f(\cdot, t)は\mathcal{T}-可測である．
fをM_tと思い，\mu fを\int M_t(x) h(x) = \bar{M}_tと思えば，\bar{M}_t(x)は\mathcal{F}_t-可測であることがわかります．
最後にスーパーマルチンゲールであることを証明します．つまり，確率１で
\mathrm{E}\big[\bar{M}_t|\mathcal{F}_{t-1}\big] \leq \bar{M}_{t-1}
を示したいです．
背理法を使います．
\Pr(\mathrm{E}\big[\bar{M}_t|\mathcal{F}_{t-1}\big] - \bar{M}_{t-1} > 0) > 0
を仮定します．
すると，ある正の整数\varepsilon > 0が存在して，
A = \{\omega : \mathrm{E}[\bar{M}_t|\mathcal{F}_{t-1}](\omega) - \bar{M}_{t-1}](\omega) > \varepsilon\} \in \mathcal{F}_{t-1}
で，\Pr(A) > 0となる事象Aが存在する．
すると，A \in \mathcal{F}_{t-1}と条件付き期待値の定義から
0 < \int_A (\mathrm{E}[\bar{M}_t | \mathcal{F}_{t-1}] - \bar{M}_{t-1})d\mathrm{P} = \int_A (\bar{M}_t - \bar{M}_{t-1})d\mathrm{P}
次に\bar{M}_tの定義から，
\int_A (\bar{M}_t - \bar{M}_{t-1})d\mathrm{P} = \int_A \int_{\mathrm{R}^d}(M_t(x) - M_{t-1}(x))dh(x)d\mathrm{P}
Fubini-Tonelliの定理より，積分順序を交換しても良く，
\int_{\mathrm{R}^d}\int_A (M_t(x) - M_{t-1}(x))dh(x)d\mathrm{P} = \int_A \int_{\mathrm{R}^d}(M_t(x) - M_{t-1}(x)))d\mathrm{P}dh(x)
最後にM_tのスーパーマルチンゲール性を使えば，
\int_A \int_{\mathrm{R}^d}(M_t(x) - M_{t-1}(x)))d\mathrm{P}dh(x) \leq 0
よって，0 < 0となり矛盾．
Discussion