Applied Mathematics E-Notes, 1(2001), 73-76 \begin{matrix}c \\ ◯ \end{matrix} Available free at mirror sites of http://math2.math.nthu.edu.tw/∼amen/

Optimal Discrete Entropy ^{∗}

Aditya Shastri and Rekha Govil^{†}^{‡}

Received 24 January 2001

Abstract

In this paper we obtain a discrete version of Shannon’s classical theorem that when the probabilities are frequencies the entropy function attains its maximum value when probabilities are as equal as possible.

In this paper we address the following question: When does the entropy function attain its maximum values if the probabilities arise from frequencies? Every probability distribution has some ‘uncertainty’ associated with it. The concept of ‘entropy’ was introduced by Shannon [3] in 1948 to provide a quantitative measure of this uncertainty. According to the maximum-entropy principle formulated by Jaynes [1], it is of considerable interest to maximize entropy among probability distributions, so that the one having the maximum entropy is the ‘most unbiased’, ‘least prejudiced’ or ‘most uniform’. For specific situations where we need to maximize entropies, the readers may consult [2].

Consider a discrete probability distribution where the sample space S consists of a finite number of elements, say S = {a_{1}, a_{2}, ..., a_{k}}, and with each elementary event {a_{i}} we have a probability p_{i} associated with it satisfying the following conditions : (i) p_{1}, ..., p_{k} ≥ 0, and (ii) p_{1} + p_{2} + ... + p_{k} = 1. Shannon in 1948, defined the entropy for this probability distribution as

H(p_{1}, p_{2}, ..., p_{k}) = − ∑_{i=1}^{k} p_{i} log p_{i}.

A special case of the above distribution is of particular interest where all outcomes are equally likely. In that case, it follows that p_{i} = 1/k. It is well known, through a classical theorem of Shannon, that H(p_{1}, p_{2}, ..., p_{k}) attains its maximum value log k when all probabilities are equal to 1/k.

The above result is based on the assumption that variables can assume arbitrary values in the interval (0, 1). There are occasions, however, when this need not be the case. In the most classical example of probability, we have a set A of cardinality N which is partitioned into A_{1} ∪ A_{2} ∪ ... ∪ A_{k} where n_{i} = |A_{i}| for i = 1, 2, ..., k and N = n_{1} + n_{2} + ... + n_{k}. Here A_{1}, ..., A_{k} are interpreted as the partitions of the sample space A and n_{1}, ..., n_{k} are frequencies of occurrences of A_{i}’s. Therefore, the probability p_{i} of an event A_{i} is given by n_{i}/N where N is the total number of outcomes and n_{i} is the number of outcomes favorable to A_{i}. Here, the entropy needs not assume its maximum value log k since the value p_{i} = 1/k may be forbidden for some i.

∗Mathematics Subject Classifications: 94A17

†Department of Computer Science, Banasthali University, P. O. Banasthali Vidyapith - 304 022, India

‡This research was partly carried out while the first author was visiting School of Mathematics, Tata Institute of Fundamental Research, Mumbai, India. Research supported in part by the Mahindra Foundation.

In this note, we will obtain the extreme values of the entropy function in the discrete case where the probabilities may assume only rational values n_{i}/N corresponding to different partitions of the set A into nonempty subsets A_{i}’s. All the notations and terminologies are standard and we presume elementary basic knowledge of probability. One of the fundamental requirements of any entropy function is that it should be a symmetric function of its arguments. That certainly is true for the discrete case as the value of entropy depends only on the sizes of A_{i}’s. Moreover, the following two results are also true.

THEOREM 1. The entropy function H(A_{1}, A_{2}, ..., A_{k}) assumes its maximum value for the partitions for which the sizes of the subsets A_{1}, ..., A_{k} differ by at most 1.

THEOREM 2. The entropy function H(A_{1}, A_{2}, ..., A_{k}) assumes its minimum value for the partitions for which all subsets but exactly one have cardinality 1.

As we have already observed that the entropy for the discrete case depends only on the sizes of A_{i}’s, i.e. it is a symmetric function of its arguments:

H(A_{1}, A_{2}, ..., A_{k}) = H(A_{i_{1}}, A_{i_{2}}, ..., A_{i_{k}})

if (i_{1}, i_{2}, ..., i_{k}) is a permutation of (1, 2, ..., k). Thus, we are led to say that two partitions π_{1} = (A_{1}, A_{2}, ..., A_{k}) and π_{2} = (B_{1}, B_{2}, ..., B_{k}) of a set A into k nonempty subsets are equivalent if the multisets {|A_{i}||1 ≤ i ≤ k} and {|B_{j}||1 ≤ j ≤ k} are identical. The above relation is easily seen to be an equivalence relation, which divides all the partitions into equivalence classes. The entropy function remains constant on each equivalence class.

In what follows we record a simple yet important observation that there is a unique equivalence class with part sizes differing by at most 1 and probabilities p_{i}’s are close to 1/k.

LEMMA 3.1. There exists a unique equivalence class such that every partition π = (A_{1}, A_{2}, ..., A_{k}) of the class satisfies ||A_{i}| − |A_{j}|| ≤ 1 for 1 ≤ i, j ≤ k and ||A_{i}| /N − 1/k| < 1/N for 1 ≤ i ≤ k.

The proof is elementary and is thus omitted.

The proof of our theorem 1 is reminiscent of the proof of Sperner’s classical theorem that the number of subsets of an n-set such that no subset is contained in another can be at most C_{⌈n/2⌉}^{n}. For if there are sets of small (large) size they can be replaced by sets of size one larger (smaller) without violating the condition and the theorem follows. We shall also show that if the partition has two sets having sizes differing by at least 2, one can then remove one element from the larger set and include it in the smaller set resulting in a net increase in the entropy. It will then follow that the optimum is attained over the equivalence class defined in Lemma 3.1 which remains fixed with respect to the operation just described.

We now turn to the proof of Theorem 1. The cases k = 1 and k = N are trivial. When k = 1, H_{max}(A) = H_{min}(A) = 0. When k = N, all probabilities are equal to 1/N leading to an optimal value H_{max}(A_{1}, A_{2}, ...A_{N}) = H_{min}(A_{1}, A_{2}, ..., A_{N}) = log_{2} N, where all A_{i}’s are singletons, as in the classical case. Furthermore, the case k = N − 1 can also be disposed of at once by observing that there is only one part of size 2 and all the remaining parts are singletons implying

H_{max}(A_{1}, A_{2}, ..., A_{N−1}) = H_{min}(A_{1}, A_{2}, ..., A_{N−1}) = log_{2} N − \frac{2}{N} .

Therefore, in what follows we shall assume 2 ≤ k ≤ N − 2. Let π = (A_{1}, A_{2}, ..., A_{k}) be a partition, 2 ≤ k ≤ N − 2, having two sets say A_{i} and A_{j}, i ≠ j, such that |A_{i}| − |A_{j}| ≥ 2. If a ∈ A_{i} then define a new partition π′ = (A′_{1}, A′_{2}, ..., A′_{k}), where A′_{m} = A_{m} for m ≠ i, j, A′_{i} = A_{i} − {a} and A′_{j} = A_{j} ∪ {a}. It follows that

H(π′) − H(π) = − (p_{i} − \frac{1}{N} ) log_{2} (p_{i} − \frac{1}{N} )

− (p_{j} + \frac{1}{N} ) log_{2} (p_{j} + \frac{1}{N} ) + p_{i} log_{2} p_{i} + p_{j} log_{2} p_{j}

= \frac{1}{N} (log_{2} (p_{i} − \frac{1}{N} ) − log_{2} (p_{j} + \frac{1}{N} )) + p_{i} log_{2} p_{i}
−p_{i} log_{2} (p_{i} − \frac{1}{N} ) + p_{j} log_{2} p_{j} − p_{j} log_{2} (p_{j} + \frac{1}{N} ) . (1)

Since |A_{i}| − |A_{j}| ≥ 2 and p_{i} − p_{j} ≥ 2/N, hence p_{i} − 1/N ≥ p_{j} + 1/N. Therefore, the first term in (1) is non-negative and we have

H(π′) − H(π) ≥ p_{i} log_{2} p_{i} − p_{i} log_{2} (p_{i} − \frac{1}{N} ) + p_{j} log_{2} p_{j} − p_{j} log_{2} (p_{j} + \frac{1}{N} ) .

Simplifying and using Np_{i} = |A_{i}| and Np_{j} = |A_{j}|, we get

H(π′) − H(π) ≥ p_{i} (log_{2} \frac{|A_{i}|}{|A_{i}| − 1}) + p_{j} (log_{2} \frac{|A_{j}|}{|A_{j}| + 1}) .  (2)

Observe that log_{2} x ≥ 1 if x ≥ 1, and |A_{j}|/(|A_{j}|+1) ≥ 1/2 which implies log_{2} |A_{j}|/(|A_{j}|+ 1) ≥ −1. Putting these values in (2) we obtain

H(π′) − H(π) ≥ p_{i} − p_{j}

and the theorem follows.

As for the proof of Theorem 2, one can define a local operation on any given partition by moving an element from the smaller set into a bigger set. This operation does not increase the entropy; and thereby deduce that the entropy is minimized when all but one set have cardinality 1.

As an immediate corollary, the extreme values of the entropy, where a n-set is partitioned into k subsets, is given by

H_{max} = −\frac{1}{N} \{r(m + 1) log_{2} \frac{m + 1}{N} + (k − r) log_{2} \frac{m}{N} \} ,

and

H_{min} = −\frac{1}{N} \{(k − 1) log_{2} \frac{1}{N} + (N − k + 1) log_{2} (1 − \frac{k − 1}{N})\} ,

where N = mk + r for 0 ≤ r < k.

Theorem 1 and Theorem 2 are discrete analogues of Shannon’s classical theorem that the entropy is maximized when all probabilities are equal. Note that Theorem 1 and Theorem 2 do not follow from Shannon’s theorem. It would be interesting to look for more cases where the probability variation is somewhat restricted and compute the corresponding extreme values of the entropy functions.

References

[1] E. T. Jaynes, Information Theory and Statistical Mechanics, Physical Reviews 106(1957), 620-630.

[2] J. N. Kapur, Maximum Entropy Models in Science and Engineering, Wiley Eastern Limited, New Delhi, 1987.

[3] C. E. Shannon, A Mathematical Theory of Communication, Bell System Tech. J. 27(1948), 379-423, 623-659.