Given a random variable $X$ distributed under some computable distribution $P$ we have,

$$0 \le E[K(X)] - H(P) \le K(P)$$

Where $H(P)$ is the entropy of $P$. I tried using Hoeffding concentration bounds, but they aren't very helpful here. Are there similar bounds for $E[(K(X)-H(P))^2]$? In general, is there any way to get information about the distribution shape of $K(X)$ or is that uncomputable?

  • $\begingroup$ How do you define $K(X)$ for a random variable $X$? $\endgroup$ – Aryeh Kontorovich Nov 7 '18 at 19:34
  • $\begingroup$ @AryehKontorovich I linked a reference in the question, the expectation is supposed to be taken with a finite sum. You sum over the sample space of X multiplying by probability. It's mostly suggestive. $\endgroup$ – Zachary W. Robertson Nov 7 '18 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.