# Empirical distribution vs. the true one: How fast $KL( \hat{P}_n || Q)$ converges to $KL( P || Q)$?

Let $X_1,X_2,\dots$ be i.i.d. samples drawn from a discrete space $\mathcal{X}$ according to probability distribution $P$, and denote the resulting empirical distribution based on n samples by $\hat{P}_n$. Also let $Q$ be an arbitrary distribution. It is clear that (KL-divergence)

$KL( \hat{P}_n || Q) \stackrel{n\rightarrow \infty}{\longrightarrow} KL(P || Q)$,

but I am wondering if there exist any known quantitative rate of convergence for it. I mean if it can be shown that

$\Pr\Big[ | KL( \hat{P}_n || Q) - KL(P || Q) | \geq \delta\Big] \leq f(\delta, n, |\mathcal{X}|)$,

and what is the best expression for the RHS if there is any.

Thanks a lot!

-
Just to clarify: You're asking for a uniform bound in $P$ and $Q$? – cardinal Dec 6 '12 at 3:42
@cardinal: Yes. In fact I want to know how many samples should I take to guarantee a maximum gap for the KL-divergence. Note that $n$ can be much larger that $|\mathcal{X}|$, i.e. $\hat{P}_n$ closely follow the true $P$. – Sam Dec 6 '12 at 8:42
I am wondering whether (or how) $D(\hat{P_n}\|P)\to 0$ is different from $D(\hat{P_n}\|Q)\to D(P\|Q)$. – Ashok Dec 8 '12 at 6:06
@Ashok: The KL-divergence is not a true metric (en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence). In particular, the triangle inequality does NOT hold, and $D(\hat{P}_n\| Q)−D(P \| Q)$ can be larger than $D(\hat{P}_n \| P)$. Hence, even if $D(\hat{P}_n\| P)\rightarrow 0$ implies $D(\hat{P}_n \| Q)\rightarrow D(P\| Q)$ (does it?), the convergence rate of the former does not guarantee the convergence rate for the latter. – Sam Dec 10 '12 at 0:28
@Sam: Yes,yes, you are right. I know KL-divergence is not a metric. But I just wanted to know the difference between $D(\hat{P}_n\| P)\rightarrow 0$ and $D(\hat{P_n}\|Q)\to D(P\|Q)$. I am also very interested in your question. – Ashok Dec 10 '12 at 5:26

Suppose, for every fixed $Q$, we can find a linear family $\Pi$ of prob. distributions consisting of all empirical measures $\hat{P_n}$ and $P$, and such that $P$ is the $I$-projection of $Q$ on $\Pi$, then the Pythagorean property $$D(\hat{P_n}\| Q)=D(\hat{P_n}\|P)+D(P \| Q)$$ holds and hence the convergence rate of $D(\hat{P}_n\| Q)\to D(P \| Q)$ is same as that of $D(\hat{P}_n\| P)\to 0$.