We want to prove:

This can be rewritten as:

After moving everything to the right hand side and simplifying, we get:

Now if we just prove that q(x,y,s)=pxs(x,s)pys(y,s)ps(s) is a probability distribution, then the left hand side is KL(pxys(x,y,s),q) , and Kullback-Leibler divergence is always nonnegative.

Ok, q is obviously nonnegative, and its integral equals 1:

Q.e.d.

We want to prove:

This can be rewritten as:

After moving everything to the right hand side and simplifying, we get:

Now if we just prove that q(x,y,s)=pxs(x,s)pys(y,s)ps(s) is a probability distribution, then the left hand side is KL(pxys(x,y,s),q) , and Kullback-Leibler divergence is always nonnegative.

Ok, q is obviously nonnegative, and its integral equals 1:

Q.e.d.