An inequality on entropy
Robert J. McEliece, Yu Ning Zhong · 2002
The entropy H(X) of a discrete random variable X of alphabet size m is always non-negative and upper-bounded by log m. In this paper, we present a theorem which gives a non-trivial lower bound for H(X). We show that for any discrete random variable X with range R={x/sub 0/,...,x/sub m-1/}, if p/sub i/=Pr{X=x/sub i/} and p/sub 0//spl ges/p/sub 1//spl ges/...p/sub m-1/, then H(X)/spl ges/(2logm)/(m-1)/spl Sigma//sub i=0//sup m-1/ip/sub i/, with equality iff (i) X is uniformly distributed, i.e., p/sub i/=1/m for all i, or trivially (ii) p/sub 0/=1, and p/sub i/=0 for 1/spl les/i/spl les/m-1.