7
$\begingroup$

Let $X$ be a random variable taking values in a set $\mathcal{X}$. The distribution of $X$ is not uniform, but there is a subset $A\in\mathcal{X}$ which is "uniform": all events in $A$ occur with equal probability.

Can we relate the entropy of $X$ to the size of the set $A$? Intuitively it seems like we should be able to say the entropy of $X$ is at least $\log |A|$, but I'm not sure how to prove it.

For example, when $A = \mathcal{X}$ the distribution on $X$ is uniform, and the bound holds trivially.

$\endgroup$
8
$\begingroup$

Simply apply the entropy formula: the result drops right out. The idea is that $A$ alone contributes at least $$-|A| \left(\frac{1}{|A|}\right)\log\left(\frac{1}{|A|}\right)=\log|A|$$ to the entropy and any other terms in the entropy formula can only increase it further. Details follow.


First, let's be clear about the language: subsets of $\mathcal{X}$ are not usually considered "events." $X$ is a function from a probability space $(\Omega, \mathfrak{F}, \mathbb{P})$ into $\mathcal X$. The inverse images

$$X^{-1}(a) = \{\omega\in\Omega\mid X(\omega)=a\}$$

are assumed to be measurable subsets of $\Omega$ and as such are (in the conventional sense) events.

For convenience, let $n=|A|$ be its cardinality and let $p$ be the common probability of all the events in question; that is,

$$p = \Pr(X^{-1}(a))$$

for any $a\in A$.

Decompose $\Omega$ into $X^{-1}(A)$ and its complement, $\bar A = \Omega\setminus X^{-1}(A)$. The Axiom of Total Probability, along with the fact that the probability of $\bar A$ is not negative, imply

$$\eqalign{ 1 &= \Pr(\Omega) = \Pr(\bar A_X) + \Pr(X^{-1}(A))\\ &= \Pr(\bar A_X) + \sum_{a\in A} \Pr(X^{-1}(a)) \\ & = \Pr(\bar A_X) + np \ge np. }$$

In case $n$ is infinite, this shows $p$ must be zero and $\log p$ will be undefined. We must therefore assume $n$ is finite. In this case, the preceding calculation shows

$$p \le \frac{1}{n}.$$

In the calculation of the entropy of $X$, there will be terms corresponding to $X^{-1}\left(\mathcal{X}\setminus A\right)$ which contribute non-negative values to the entropy. There remain $n$ terms from $A$. Each of these contributes $-p\log p$ to the entropy (by definition). Because $p \le 1/n$ and $\log$ is a monotonically increasing function (i.e., $\log(p) \le \log(1/n)$), their total of $-np\log p$ has a lower bound

$$-np\log p \ge -n\frac{1}{n}\log\left(\frac{1}{n}\right) = \log n =\log|A|,$$

QED.

$\endgroup$

Your Answer

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

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