Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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 ( 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

Here's a thought. I don't know whether I am in an imaginary world and asking too much. Any way, let me propose this. I am writing it as an answer as it is little larger to put it as a comment.

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.