Monday, December 31, 2012

Worked Examples for Conditional Expectation

Introduction

Brzezniak (2000) is a great book because it approaches conditional expectation through a sequence of exercises, which is what we are trying to do here. The main difference is that Brzezniak takes a more abstract measure-theoretic approach to the same problems. Note that you do need to grasp the measure-theoretic to move into more advanced areas in stochastic processes, but for what we have covered so far, working the same problems in his text using our methods is illuminating. It always helps to have more than one way to solve any problem. I urge you to get a copy of his book or at least look at some pages on Google Books. I have numbered the examples corresponding to the book.

Examples

This is Example 2.1 from Brzezniak:

Three coins, 10p, 20p and 50p are tossed. The values of those coins that land heads up are added to work out the total amount. What is the expected total amount given that two coins have landed heads up?

In this case we have we want to compute $\mathbb{E}(\xi|\eta)$ where

$$ \xi = 10 X_{10} + 20 X_{20} +50 X_{50} $$

where $X_i \in { 0,1} $. This represents the sum total value of the heads-up coins. The $\eta$ represents the fact that only two of the three coins are heads-up. Note

$$\eta = X_{10} X_{20} (1-X_{50})+ (1-X_{10}) X_{20} X_{50}+ X_{10} (1-X_{20}) X_{50} $$

is a function that is only non-zero when two of the three coins is heads. Each triple term catches each of these three possibilities. For example, the first term is when the 10p and 20p are heads up and the 50p is heads down.

To compute the conditional expectation, we want to find a function $h$ of $\eta$ that minimizes the MSE

$$ \sum_{X\in{0,1}^3} \frac{1}{8} (\xi - h( \eta ))^2 $$

where the sum is taken over all possible triples of outcomes for $ {X_{10} , X_{20} ,X_{50}}$ and the $\frac{1}{8} = \frac{1}{2^3} $ since each coin has a $\frac{1}{2}$ chance of coming up heads.

Now, the question boils down to what function $h(\eta)$ should we try? Note that $\eta \in {0,1}$ so $h$ takes on only two values. Thus, we only have to try $h(\eta)=\alpha \eta$ and find $\alpha$. Writing this out gives,

$$ \sum_{X\in{0,1}^3} \frac{1}{8} (\xi - \alpha( \eta ))^2 $$

which boils down to solving for $\alpha$,

$$\langle \xi , \eta \rangle = \alpha \langle \eta,\eta \rangle$$

where

$$ \langle \xi , \eta \rangle =\sum_{X\in{0,1}^3} \frac{1}{8} (\xi \eta ) $$

This is tedious and a perfect job for sympy.

In [11]:
import sympy as S

eta = S.Symbol('eta')
xi = S.Symbol('xi')
X10 = S.Symbol('X10')
X20 = S.Symbol('X20')
X50 = S.Symbol('X50')

eta = X10 * X20 *(1-X50 )+ X10 * (1-X20) *(X50 )+ (1-X10) * X20 *(X50 )
xi = 10*X10 +20* X20+ 50*X50 

num=S.summation(xi*eta,(X10,0,1),(X20,0,1),(X50,0,1))
den=S.summation(eta*eta,(X10,0,1),(X20,0,1),(X50,0,1))
alpha=num/den
print alpha
160/3

This means that

$$ \mathbb{E}(\xi|\eta) = \frac{160}{3} \eta $$

which we can check with a quick simulation

In [12]:
import numpy as np
from numpy import array

x=np.random.randint(0,2,(3,5000))
print (160/3.,np.dot(x[:,x.sum(axis=0)==2].T,array([10,20,50])).mean())
(53.333333333333336, 53.177920685959272)

Example

This is example 2.2:

Three coins, 10p, 20p and 50p are tossed as before. What is the conditional expectation of the total amount shown by the three coins given the total amount shown by the 10p and 20p coins only?

For this problem,

$$\eta = 30 X_{10} X_{20} + 20 (1-X_{10}) X_{20} + 10 X_{10} (1-X_{20}) $$

which takes on three values (10,20,30) and only considers the 10p and 20p coins. Here, we'll look for affine functions, $h(\eta) = a \eta + b $.

In [13]:
from sympy.abc import a,b

eta = X10 * X20 * 30 + X10 * (1-X20) *(10 )+ (1-X10) * X20 *(20 )
h = a*eta + b

J=S.summation((xi - h)**2 * S.Rational(1,8),(X10,0,1),(X20,0,1),(X50,0,1))

sol=S.solve( [S.diff(J,a), S.diff(J,b)],(a,b) )
print sol
{b: 25, a: 1}

This means that

$$ \mathbb{E}(\xi|\eta) = 25+ \eta $$

since $\eta$ takes on only four values, ${0,10,20,30}$, we can write this out as

$$ \mathbb{E}(\xi|\eta=0) = 25 $$ $$ \mathbb{E}(\xi|\eta=10) = 35 $$ $$ \mathbb{E}(\xi|\eta=20) = 45 $$ $$ \mathbb{E}(\xi|\eta=30) = 55 $$

The following is a quick simulation to demonstrate this.

In [14]:
x=np.random.randint(0,2,(3,5000))  # random samples for 3 coins tossed
eta=np.dot(x[:2,:].T,array([10,20])) # sum of 10p and 20p

print np.dot(x[:,eta==0].T,array([10,20,50])).mean() # E(xi|eta=0)
print np.dot(x[:,eta==10].T,array([10,20,50])).mean()# E(xi|eta=10)
print np.dot(x[:,eta==20].T,array([10,20,50])).mean()# E(xi|eta=20)
print np.dot(x[:,eta==30].T,array([10,20,50])).mean()# E(xi|eta=30)
26.4120922832
34.5614035088
45.8196721311
55.3743104807

Example

This is Example 2.3

Note that "Lebesgue measure" on $[0,1]$ just means uniformly distributed on that interval. Also, note the the Piecewise object in sympy is not complete at this point in its development, so we'll have to work around that in the following.

In [15]:
x=S.Symbol('x')
c=S.Symbol('c')

xi = 2*x**2

eta=S.Piecewise( (1, 0 < x< S.Rational(1,3)), 
                 (2, S.Rational(1,3) < x< S.Rational(2,3)),
                 (0, S.Rational(2,3) < x < 1))

h = a + b*eta + c*eta**2 
J=S.integrate((xi - h)**2 ,(x,0,1))

sol=S.solve( [S.diff(J,a), 
              S.diff(J,b),
              S.diff(J,c),
              ],
              (a,b,c) )
print sol

print S.piecewise_fold(h.subs(sol))
{c: 8/9, b: -20/9, a: 38/27}
Piecewise((2/27, x < 1/3), (14/27, x < 2/3), (38/27, x < 1))

Thus, collecting this result gives:

$$ \mathbb{E}(\xi|\eta) = \frac{38}{27} - \frac{20}{9}\eta + \frac{8}{9} \eta^2$$

which can be re-written as a piecewise function as

$$\mathbb{E}(\xi|\eta) =\begin{cases} \frac{2}{27} & \text{for}\: 0 < x < \frac{1}{3} \\ \frac{14}{27} & \text{for}\: \frac{1}{3} < x < \frac{2}{3} \\ \frac{38}{27} & \text{for}\: \frac{2}{3}<x < 1 \end{cases} $$

The following is a quick simulation to demonstrate this.

In [16]:
x = np.random.rand(1000)
f,ax= subplots()
ax.hist(2*x**2,bins=array([0,1/3.,2/3.,1])**2*2,normed=True,alpha=.5)
ax.vlines([2/27.,14/27.,38/27.],0,ax.get_ylim()[1],linestyles='--')
ax.set_xlabel(r'$2 x^2$',fontsize=18);

This plot shows the intervals that correspond to the respective domains of $\eta$ with the vertical dotted lines showing the $\mathbb{E}(\xi|\eta) $ for that piece.

Example

This is Example 2.4

In [17]:
x,a=S.symbols('x,a')

xi = 2*x**2

half = S.Rational(1,2)

eta_0=S.Piecewise( (2,    0 <= x < half), 
                   (0, half <= x <= 1),
                 )

eta_1=S.Piecewise( (0,         x < half),
                   (x, half <= x <= 1),
                )


v=S.var('b:3') # coefficients for quadratic function of eta

h = a*eta_0 + (eta_1**np.arange(len(v))*v).sum()

J=S.integrate((xi - h)**2 ,(x,0,1))
sol=S.solve([J.diff(i) for i in v+(a,)],v+(a,))
hsol = h.subs(sol)

f=S.lambdify(x,hsol,'numpy')
print S.piecewise_fold(h.subs(sol))

t = np.linspace(0,1,51,endpoint=False)

fig,ax = subplots()

ax.plot(t, 2*t**2,label=r'$\xi=2 x^2$')
ax.plot(t,[f(i) for i in t],'-x',label=r'$\mathbb{E}(\xi|\eta)$')
ax.plot(t,map(S.lambdify(x,eta_0+eta_1),t),label=r'$\eta(x)$')
ax.set_ylim(ymax = 2.3)
ax.grid()
ax.legend(loc=0);
#ax.plot(t,map(S.lambdify(x,eta),t))
Piecewise((1/6, x < 1/2), (2*x**2, x <= 1))
Out[17]:
<matplotlib.legend.Legend at 0x4b2b910>

The figure shows the $\mathbb{E}(\xi|\eta)$ against $\xi$ and $\eta$. Note that $\xi= \mathbb{E}(\xi|\eta)= 2 x^2$ when $x\in[0,\frac{1}{2}]$ . Assembling the solution gives,

$$\mathbb{E}(\xi|\eta) =\begin{cases} \frac{1}{6} & \text{for}\: 0 \le x < \frac{1}{2} \ 2 x^2 & \text{for}\: \frac{1}{2} < x \le 1 \end{cases}$$

This example warrants more a more detailed explanation since $\eta$ is more complicated. The first question is why did we choose $h(\eta)$ as a quadratic function? Since $\xi$ is a squared function of $x$ and since $x$ is part of $\eta$, we chose a quadratic function so that $h(\eta)$ would contain a $x^2$ in the domain where $\eta=x$. The motivation is that we are asking for a function $h(x)$ that most closely approximates $2x^2$. Well, obviously, the exact function is $h(x)=2 x^2$! Thus, we want $h(x)=2 x^2$ over the domain where $\eta=x$, which is $x\in[\frac{1}{2},1]$ and that is exactly what we have.

We could have used our inner product by considering two separate functions,

$\eta_1 (x) = 2$

where $x\in [0,\frac{1}{2}]$ and

$$\eta_2 (x) = x$$

where $x\in [\frac{1}{2},1]$. Thus, at the point of projection, we have

$$ \mathbb{E}((2 x^2 - 2 c) \cdot 2) = 0$$

which leads to

$$\int_0^{\frac{1}{2}} 2 x^2 \cdot 2 dx = \int_0^{\frac{1}{2}} c 2 \cdot 2 dx $$

and a solution for $c$,

$$ c = \frac{1}{12} $$

Assembling the solution for $x\in[0,\frac{1}{2}]$ gives

$$ \mathbb{E}(\xi|\eta) = \frac{2}{12}$$

We can do the same thing for the other piece, $\eta_2$,

$$ \mathbb{E}((2 x^2 - c x^2) \cdot x) = 0$$

which, by inspection, gives $c=2$. Thus, for $x\in[\frac{1}{2},1]$ , we have

$$ \mathbb{E}(\xi|\eta)= 2 x^2$$

which is what we had before.

Example

This is Exercise 2.6

In [18]:
x,a=S.symbols('x,a')

xi = 2*x**2
eta = 1 - abs(2*x-1)

half = S.Rational(1,2)

eta=S.Piecewise(   (1+(2*x-1),    0 <= x < half), 
                   (1-(2*x-1), half <= x < 1),
                 )

v=S.var('b:3') # assume h is quadratic in eta

h = (eta**np.arange(len(v))*v).sum()

J=S.integrate((xi - h)**2 ,(x,0,1))
sol=S.solve([J.diff(i) for i in v],v)
hsol = h.subs(sol)

print S.piecewise_fold(h.subs(sol))

t = np.linspace(0,1,51,endpoint=False)

fig,ax = subplots()
fig.set_size_inches(5,5)

ax.plot(t, 2*t**2,label=r'$\xi=2 x^2$')
ax.plot(t,[hsol.subs(x,i) for i in t],'-x',label=r'$\mathbb{E}(\xi|\eta)$')
ax.plot(t,map(S.lambdify(x,eta),t),label=r'$\eta(x)$')
ax.legend(loc=0)
ax.grid()
Piecewise((2*x**2 - 2*x + 1, x < 1/2), (2*x + (-2*x + 2)**2/2 - 1, x < 1))

The figure shows that the $\mathbb{E}(\xi|\eta)$ is continuous over the entire domain. The code above solves for the conditional expectation using optimization assuming that $h$ is a quadratic function of $\eta$, but we can also do it by using the inner product. Thus,

$$ \mathbb{E}\left((2 x^2 - h(\eta_1(x)) )\eta_1(x)\right)= \int_0^{\frac{1}{2}} (2 x^2 - h(\eta_1(x)) )\eta_1(x) dx = 0$$

where $\eta_1 = 2x $ for $x\in [0,\frac{1}{2}]$. We can re-write this in terms of $\eta_1$ as

$$ \int_0^1 \left(\frac{\eta_1^2}{2}-h(\eta_1)\right)\eta_1 d\eta_1$$

and the solution jumps right out as $h(\eta_1)=\frac{\eta_1^2}{2}$. Note that $\eta_1\in[0,1]$. Doing the same thing for the other piece,

$$ \eta_2 = 2 - 2 x, \hspace{1em} \forall x\in[\frac{1}{2},1]$$

gives,

$$ \int_0^1 \left(\frac{(2-\eta_2)^2}{2}-h(\eta_2)\right)\eta_2 d\eta_2$$

and again, the optimal $h(\eta_2)$ jumps right out as

$$ h(\eta_2) = \frac{(2-\eta_2)^2}{2} , \hspace{1em} \forall \eta_2\in[0,1]$$

and since $\eta_2$ and $\eta_2$ represent the same variable over the same domain we can just add these up to get the full solution:

$$ h(\eta) = \frac{1}{2} \left( 2 - 2 \eta + \eta^2\right) $$

and then back-substituting each piece for $x$ produces the same solution as sympy.

Example

This is Exercise 2.14

In [19]:
x,a=S.symbols('x,a')
half = S.Rational(1,2)

xi = 2*x**2
eta=S.Piecewise(   (2*x,    0 <= x < half), 
                   ((2*x-1), half <= x ),
                 )

v=S.var('b:3')

h = (eta**np.arange(len(v))*v).sum()

J=S.integrate((xi - h)**2 ,(x,0,1))
sol=S.solve([J.diff(i) for i in v],v)
hsol = h.subs(sol)

print S.piecewise_fold(h.subs(sol))

t = np.linspace(0,1,51,endpoint=False)

fig,ax = subplots()
fig.set_size_inches(5,5)

ax.plot(t, 2*t**2,label=r'$\xi=2 x^2$')
ax.plot(t,[hsol.subs(x,i) for i in t],'-x',label=r'$\mathbb{E}(\xi|\eta)$')
ax.plot(t,map(S.lambdify(x,eta),t),label=r'$\eta(x)$')
ax.legend(loc=0)
ax.grid()
Piecewise((2*x**2 + x + 1/4, x < 1/2), (x + (2*x - 1)**2/2 - 1/4, 1/2 <= x))

As before, using the inner product for this problem, gives:

$$ \int_0^1 \left(\frac{\eta_1^2}{2}-h(\eta_1)\right)\eta_1 d\eta_1=0$$

and the solution jumps right out as $$h(\eta_1)=\frac{\eta_1^2}{2} , \hspace{1em} \forall \eta_1\in[0,1$$

where $\eta_1(x)=2x$. Doing the same thing for $\eta_2=2x-1$ gives,

$$ \int_0^1 \left(\frac{(1+\eta_2)^2}{2}-h(\eta_2)\right)\eta_1 d\eta_2=0$$

with

$$h(\eta_2)=\frac{(1+\eta_2)^2}{2} , \hspace{1em} \forall \eta_2\in[0,1]$$

and then adding these up as before gives the full solution:

$$ h(\eta)= \frac{1}{2} +\eta + \eta^2$$

Back-substituting each piece for $x$ produces the same solution as sympy.

In [20]:
xs = np.random.rand(100)
print np.mean([(2*i**2-hsol.subs(x,i))**2 for i in xs])
print S.integrate((2*x**2-hsol)**2,(x,0,1)).evalf()
0.266422848567040
0.270833333333333

Summary

We worked out some of the great examples in Brzezniak's book using our methods as a way to show multiple ways to solve the same problem. In particular, comparing Brzezniak's more measure-theoretic methods to our less abstract techniques is a great way to get a handle on those concepts which you will need for more advanced study in stochastic process.

As usual, the corresponding IPython Notebook notebook for this post is available for download here

Comments and corrections welcome!

References

  • Brzezniak, Zdzislaw, and Tomasz Zastawniak. Basic stochastic processes: a course through exercises. Springer, 2000.

Tuesday, December 11, 2012

Conditional Expectation as Projection

Introduction

In these pages, I have tried to distill and illustrate the keys concepts needed in statistical signal processing, and in this section, we will cover the most fundamental statistical result that underpins statistical signal processing. The last sections on conditional expectation and projection are prerequisites for what follows. Please review those before continuing.

Inner Product for Random Variables

From our previous work on projection for vectors in $\mathbb{R}^n$, we have a good geometric grasp on how projection is related to minimum mean squared error (MMSE). It turns out by one abstract step, we can carry all of our geometric interpretations to the space of random variables.

For example, we previously noted that at the point of projection, we had

$$ ( \mathbf{y} - \mathbf{v}_{opt} )^T \mathbf{v} = 0$$

which by noting the inner product slightly more abstractly as $\langle\mathbf{x},\mathbf{y} \rangle = \mathbf{x}^T \mathbf{y}$, we can express as

$$\langle \mathbf{y} - \mathbf{v}_{opt},\mathbf{v} \rangle = 0 $$

and, in fact, by defining the inner product for the random variables $X$ and $Y$ as

$$ \langle X,Y \rangle = \mathbb{E}(X Y)$$

we remarkably have the same relationship:

$$\langle X-h_{opt}(Y),Y \rangle = 0 $$

which holds not for vectors in $\mathbb{R}^n$, but for random variables $X$ and $Y$ and functions of those random variables. Exactly why this is true is technical, but it turns out that one can build up the entire theory of probability this way (see Nelson,1987), by using the expectation as an inner product.

Furthermore, by abstracting out the inner product concept, we have drawn a clean line between MMSE optimization problems, geometry, and random variables. That's a lot of mileage to get a out of an abstraction and it is key to everything we pursue in statistical signal processing because now we can shift between these interpretations to address real problems. Soon, we'll see how to do this with some examples, but first we will collect one staggering result that flows naturally from this abstraction.

Conditional Expectation as Projection

Previously, we noted that the conditional expectation is the minimum mean squared error (MMSE) solution to the following problem:

$$ \min_h \int_{\mathbb{R}} (x - h(y) )^2 dx $$

with the minimizing $h_{opt}(Y) $ as

$$ h_{opt}(Y) = \mathbb{E}(X|Y) $$

which is another way of saying that among all possible functions $h(Y)$, the one that minimizes the MSE is $ \mathbb{E}(X|Y)$ (see appendix for a quick proof). From our discussion on projection, we noted that these MMSE solutions can be thought of as projections onto a subspace that characterizes $Y$. For example, we previously noted that at the point of projection, we have

$$\langle X-h_{opt}(Y),Y \rangle = 0 $$

but since we know that the MMSE solution

$$ h_{opt}(Y) = \mathbb{E}(X|Y) $$

we have by direct substitution,

$$ \mathbb{E}( X-\mathbb{E}(X|Y), Y) = 0$$

That last step seems pretty innocuous, but it is the step that ties MMSE to conditional expectation to the inner project abstraction, and in so doing, reveals the conditional expectation to be a projection operator for random variables. Before we develop this further, let's grab some quick dividends:

From the previous equation, by linearity of the expectation, we may obtain,

$$ \mathbb{E}(X Y) = \mathbb{E}(Y \mathbb{E}(X|Y))$$

which we could have found by using the formal definition of conditional expectation,

\begin{equation} \mathbb{E}(X|Y) = \int_{\mathbb{R}^2} x \frac{f_{X,Y}(x,y)}{f_Y(y)} dx dy \end{equation}

and direct integration,

$$ \mathbb{E}(Y \mathbb{E}(X|Y))= \int_{\mathbb{R}} y \int_{\mathbb{R}} x \frac{f_{X,Y}(x,y)}{f_Y(y)} f_Y(y) dx dy =\int_{\mathbb{R}^2} x y f_{X,Y}(x,y) dx dy =\mathbb{E}( X Y) $$

which is good to know, but not very geometrically intuitive. And this lack of geometric intuition makes it hard to apply these concepts and keep track of these relationships.

We can keep pursuing this analogy and obtain the length of the error term as

$$ \langle X-h_{opt}(Y),X-h_{opt}(Y) \rangle = \langle X,X \rangle - \langle h_{opt}(Y),h_{opt}(Y) \rangle $$

and then by substituting all the notation we obtain

\begin{equation} \mathbb{E}(X- \mathbb{E}(X|Y))^2 = \mathbb{E}(X)^2 - \mathbb{E}(\mathbb{E}(X|Y) )^2
\end{equation}

which would be tough to compute by direct integration.

We recognize that $\mathbb{E}(X|Y)$ is in fact a projection operator. Recall previously that we noted that the projection operator is idempotent, which means that once we project something onto a subspace, further projections essentially do nothing. Well, in the space of random variables, $\mathbb{E}(X|\cdot$) is the idempotent projection as we can show by noting that

$$ h_{opt} = \mathbb{E}(X|Y)$$

is purely a function of $Y$, so that

$$ \mathbb{E}(h_{opt}(Y)|Y) = h_{opt}(Y) $$

since $Y$ is fixed and this is the statement of idempotency. Thus, conditional expectation is the corresponding projection operator in this space of random variables. With this happy fact, we can continue to carry over our geometric interpretations of projections for vectors ($\mathbf{v}$) into random variables ( $X$ ).

Now that we have just stuffed our toolbox, let's consider some example conditional expectations obtained by using brute force to find the optimal MMSE function $h_{opt}$ as well as by using the definition of the conditional expectation.

Example

Suppose we have a random variable, $X$, then what constant is closest to $X$ in the mean-squared-sense (MSE)? In other words, which $c$ minimizes the following:

$$ J = \mathbb{E}( X - c )^2 $$

we can work this out as

$$ \mathbb{E}( X - c )^2 = \mathbb{E}(c^2 - 2 c X + X^2) = c^2-2 c \mathbb{E}(X) + \mathbb{E}(X^2) $$

and then take the first derivative with respect to $c$ and solve:

$$ c_{opt}=\mathbb{E}(X) $$

Remember that $X$ can take on all kinds of values, but this says that the closest number to $X$ in the MSE sense is $\mathbb{E}(X)$.

Coming at this same problem using our inner product, we know that at the point of projection

$$ \mathbb{E}((X-c_{opt}) 1) = 0$$

where the $1$ represents the space of constants (i.e. $c \cdot 1 $) we are projecting on. This, by linearity of the expectation, gives

$$ c_{opt}=\mathbb{E}(X) $$

Because $\mathbb{E}(X|Y)$ is the projection operator, with $Y=\Omega$ (the entire underlying probability space), we have, using the definintion of conditional expectation:

$$ \mathbb{E}(X|Y=\Omega) = \mathbb{E}(X) $$

Thus, we just worked the same problem three ways (optimization, inner product, projection).

Example

Let's consider the following example with probability density $f_{X,Y}= x + y $ where $(x,y) \in [0,1]^2$ and compute the conditional expectation straight from the definition:

$$ \mathbb{ E}(X|Y) = \int_0^1 x \frac{f_{X,Y}(x,y)}{f_Y(y)} dx= \int_0^1 x \frac{x+y}{y+1/2} dx =\frac{3 y + 2}{6 y + 3} $$

That was pretty easy because the density function was so simple. Now, let's do it the hard way by going directly for the MMSE solution $h(Y)$. Then,

$$ \min_h \int_0^1\int_0^1 (x - h(y) )^2 f_{X,Y}(x,y)dx dy = \min_h \int_0^1 y h^2 {\left (y \right )} - y h{\left (y \right )} + \frac{1}{3} y + \frac{1}{2} h^{2}{\left (y \right )} - \frac{2}{3} h{\left (y \right )} + \frac{1}{4} dy $$

Now we have to find a function $h$ that is going to minimize this. Solving for a function, as opposed to solving for a number, is generally very, very hard, but because we are integrating over a finite interval, we can use the Euler-Lagrange method from variational calculus to take the derivative of the integrand with respect to the function $h(y)$ and set it to zero. Euler-Lagrange methods will be the topic of a later section, but for now we just want the result, namely,

$$ 2 y h{\left (y \right )} - y + h{\left (y \right )} - \frac{2}{3} =0 $$

Solving this gives

$$ h_{opt}(y)= \frac{3 y + 2}{6 y + 3} $$

Finally, we can try solving this using our inner product as

$$ \mathbb{E}( (X - h(Y)) Y ) = 0$$

Writing this out gives,

$$ \int_0^1 \int_0^1 (x-h(y))(x+y) dx dy = \int_0^1 \frac{y\,\left(2 + 3\,y - 3\,\left( 1 + 2\,y \right) \,h(y)\right) }{6} dy = 0$$

and if this is zero everywhere, then the integrand must be zero,

$$ 2 y + 3 y^2 - 3 y h(y) - 6 y^2 h(y)=0 $$

and solving this for $h(y)$ gives the same solution:

$$ h_{opt}(y)= \frac{3 y + 2}{6 y + 3} $$

Thus, doing it by the definition, optimization, or inner product gives us the same answer; but, in general, no method is necessarily easier because they both involve potentially difficult or impossible integration, optimization, or functional equation solving. The point is that now that we have a deep toolbox, we can pick and choose which tools we want to apply for different problems.

Before we leave this example, let's use sympy to verify the length of the error function we found earlier:

\begin{equation} \mathbb{E}(X- \mathbb{E}(X|Y))^2 = \mathbb{E}(X)^2 - \mathbb{E}(\mathbb{E}(X|Y) )^2
\end{equation}

that is based on the Pythagorean theorem.

In [1]:
from sympy.abc import y,x
from sympy import integrate, simplify

fxy = x + y                 # joint density
fy = integrate(fxy,(x,0,1)) # marginal density
fx = integrate(fxy,(y,0,1)) # marginal density

h = (3*y+2)/(6*y+3) # conditional expectation
LHS=integrate((x - h)**2 *fxy, (x,0,1),(y,0,1)) # from the definition
RHS=integrate( (x)**2 *fx, (x,0,1)) - integrate( (h)**2 *fy, (y,0,1)) # using Pythagorean theorem
print simplify(LHS-RHS)==0
True

Summary

In this section, we have pulled together all the projection and least-squares optimization ideas from the previous posts to draw a clean line between our geometric notions of projection from vectors in $\mathbb{R}^n$ to general random variables. This resulted in the remarkable realization that the conditional expectation is in fact a projection operator for random variables. The key idea is that because we have these relationships, we can approach difficult problems in multiple ways, depending on which way is more intuitive or tractable in a particular situation. In these pages, we will again and again come back to these intuitions because they form the backbone of statistical signal processing.

In the next section, we will have a lot of fun with these ideas working out some examples that are usually solved using more general tools from measure theory.

Note that the book by Mikosch (1998) has some excellent sections covering much of this material in more detail. Mikosch has a very geometric view of the material as well.

Appendix

Proof of MMSE of Conditional expectation by Optimization

$$ \min_h \int_\mathbb{R^2} | X - h(Y) |^2 f_{x,y}(X,Y) dx dy $$

$$ \min_h \int_\mathbb{R^2} | X |^2 f_{x,y}(X,Y) dx dy + \int_\mathbb{R^2} | h(Y) |^2 f_{x,y}(X,Y) dx dy - \int_\mathbb{R^2} 2 X h(Y) f_{x,y}(X,Y) dx dy $$

Now, we want to maximize the following:

$$ \max_h \int_\mathbb{R^2} X h(Y) f_{x,y}(X,Y) dx dy $$

Breaking up the integral using the definition of conditional expectation

$$ \max_h \int_\mathbb{R} \left(\int_\mathbb{R} X f_{x|y}(X|Y) dx \right)h(Y) f_Y(Y) dy $$

$$ \max_h \int_\mathbb{R} \mathbb{E}(X|Y) h(Y)f_Y(Y) dy $$

From properties of the Cauchy-Schwarz inequality, we know that the maximum happens when $h_{opt}(Y) = \mathbb{E}(X|Y)$, so we have found the optimal $h(Y)$ function as :

$$ h_{opt}(Y) = \mathbb{E}(X|Y)$$

which shows that the optimal function is the conditional expectation.

References

This post was created using the nbconvert utility from the source IPython Notebook which is available for download from the main github site for this blog.

Bibliography

  • Nelson, Edward. Radically Elementary Probability Theory.(AM-117). Vol. 117. Princeton University Press, 1987.

  • Mikosch, Thomas. Elementary stochastic calculus with finance in view. Vol. 6. World Scientific Publishing Company Incorporated, 1998.