Lesson 8

Let's prove that it, as stated, minimizes the mean square deviation. \[\begin{align*}\operatorname{E}\left[(\alpha - f(\beta))^{2}\right]&=\sum_{a,b}(a-f(b))^{2}\Pr[\alpha=a, \beta=b]=\\&=\sum_{b}\left(\sum_{a}(a-f(b))^{2}\Pr[\alpha=a, \beta=b] \right)=\\&=\sum_{b}\left(\Pr[\beta=b] \cdot \sum_{a}(a-f(b))^{2}\Pr[\alpha=a \mid \beta=b] \right) \ .\end{align*}\] The inner sum for fixed \(b\) is minimized precisely at \[f(b)=\sum_{a}a\Pr[\alpha=a \mid \beta=b]=\operatorname{E}[\alpha \mid \beta=b] \ ,\] because this is the mean square deviation with respect to the measure \(\Pr[\cdot \mid \beta=b]\). Thus, \(\operatorname{E}[\alpha \mid \beta]\) is the best possible prediction of \(\alpha\) when \(\beta\) is known.