Return to Question

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P),H(Q)$ and $D(P\,\|\,Q)$ denote the entropy and Kullback-Leibler distance respectively.

Is it always true that

$$H(P)+D(P\,\|\,Q) \geq H(Q)?$$

This comes up in the theory of types where it is strongly suggested by some interpretations. However it reduces to

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} P(a)\log(Q(a))$$

which is not the "right" inequality which one usually runs into, namely

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} Q(a)\log(P(a))\qquad (\text{i.e. }D(Q\,\|\,P))\geq 0).$$

Nonetheless it may or may not be true. Have you seen it or can you prove or disprove it?

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P)$, $H(Q)$ denote their entropies and $D(P\,\|\,Q)$ denote their Kullback-Leibler distance.

Is it always true that

$$H(P)+D(P\,\|\,Q) \geq H(Q)?$$

This comes up in the theory of types where it is strongly suggested by some interpretations. However it reduces to

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} P(a)\log(Q(a))$$

which is not the "right" inequality which one usually runs into, namely

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} Q(a)\log(P(a))\qquad (\text{i.e. }D(Q\,\|\,P))\geq 0).$$

Nonetheless it may or may not be true. Have you seen it or can you prove or disprove it?

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P),H(Q)$ denote the entropy and Kullback-Leibler distance respectively.

Is it always true that

$$H(P)+D(P\,\|\,Q) \geq H(Q)?$$

This comes up in the theory of types where it is strongly suggested by some interpretations. However it reduces to

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} P(a)\log(Q(a))$$

which is not the "right" inequality which one usually runs into, namely

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} Q(a)\log(P(a))\qquad (\text{i.e. }D(Q\,\|\,P))\geq 0).$$

Nonetheless it may or may not be true. Have you seen it or can you prove or disprove it?

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P),H(Q)$ and $D(P\,\|\,Q)$ denote the entropy and Kullback-Leibler distance respectively.

Is it always true that

$$H(P)+D(P\,\|\,Q) \geq H(Q)?$$

This comes up in the theory of types where it is strongly suggested by some interpretations. However it reduces to

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} P(a)\log(Q(a))$$

which is not the "right" inequality which one usually runs into, namely

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} Q(a)\log(P(a))\qquad (\text{i.e. }D(Q\,\|\,P))\geq 0).$$

Nonetheless it may or may not be true. Have you seen it or can you prove or disprove it?

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P),H(Q)$ denote the entropy and Kullback-Leibler distance respectively.

Is it always true that

$$H(P)+D(P||Q) \geq H(Q)?$$

This comes up in the theory of types where it is strongly suggested by some interpretations. However it reduces to

$$\sum_{a\in A} Q(a)log(Q(a)) \geq \sum_{a\in A} P(a)log(Q(a))$$

which is not the "right" inequality which one usually runs into, namely

$$\sum_{a\in A} Q(a)log(Q(a)) \geq \sum_{a\in A} Q(a)log(P(a))\qquad (\text{i.e. }D(Q||P))\geq 0).$$

Nonetheless it may or may not be true. Have you seen it or can you prove or disprove it?

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P),H(Q)$ denote the entropy and Kullback-Leibler distance respectively.

Is it always true that

$$H(P)+D(P\,\|\,Q) \geq H(Q)?$$

This comes up in the theory of types where it is strongly suggested by some interpretations. However it reduces to

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} P(a)\log(Q(a))$$

which is not the "right" inequality which one usually runs into, namely

$$\sum_{a\in A} Q(a)\log(Q(a)) \geq \sum_{a\in A} Q(a)\log(P(a))\qquad (\text{i.e. }D(Q\,\|\,P))\geq 0).$$

Nonetheless it may or may not be true. Have you seen it or can you prove or disprove it?