= Solution
The chain rule, now separating $X_i$ first, gives
$$
D(Q\Vert P)
=D(Q_{X_i}\Vert P_{X_i})
+D(Q_{X^{(i)}\mid X_i}\Vert P_{X^{(i)}}\mid Q_{X_i}),
$$
where the second term denotes the conditional divergence averaged over $Q_{X_i}$. Summing over $i$ yields
$$
\sum_iD(Q_{X^{(i)}\mid X_i}\Vert P_{X^{(i)}}\mid Q_{X_i})
=nD(Q\Vert P)-\sum_iD(Q_{X_i}\Vert P_{X_i}).
$$
Repeated use of the chain rule and convexity gives the <tensorization lower bound for relative entropy>
$$
\sum_iD(Q_{X_i}\Vert P_{X_i})\leq D(Q\Vert P).
$$
Therefore the preceding sum is at least $(n-1)D(Q\Vert P)$, which is equivalent to the required inequality.
Back to article page
