Given two discrete distribution $p, q$ on some universe $U$, if I know they have a bounded KL divergence, say some number $c$, can I say anything about how much each point in the universe differs in probability?

The statement can be like, for $1\%$ of the probability mass (in terms of $p$), $p(x)/q(x)$, is somewhere between $2^{-c}$ and $2^c$, or at least $2^{-c}$, or at most $2^{c}$. Any conclusion along this line is good. And any constant here can be changed.

  • $\begingroup$ I think you may be interested in the idea of a typical set. $\endgroup$
    – mhdadk
    Mar 23, 2021 at 21:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.