Skip to main content
edited tags
Link
Iosif Pinelis
  • 127.9k
  • 8
  • 107
  • 229
Source Link
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Entropy and total variation distance

Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ and $Q$) be at most $\epsilon$. What is a standard, easily provable bound on the difference between the entropies of $X$ and $Y$?

(It is easy to see that such a bound must depend not only on $\epsilon$ but also on $N$.)