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: