# Entropy of distribution with uniform sub-distribution

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.

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.