Question

Let \(n \in N\) and \(p_{1}, \ldots, p_{n} \in R_{>0}\) such that \(\Sigma_{1 \leq i \leq n} p_{i}=1\). (i) Prove that \(H\left(p_{1}, \ldots, p_{n}\right) \geq 0\), with equality if and only if \(n=1\). (ii) Prove that \(H\left(p_{1} \ldots, p_{n}\right) \leq \log n\), with equality if and only if \(p_{1}=\cdots=p_{n}=1 / n\). Hint: Use In \(x \leq x-1\) for all positive \(x \in R\), with equality if and only if \(x=1\), and apply this to the expression \(\Sigma_{1 \leq i \leq n} p_{i} \ln \left(1 / p_{i} n\right) / \ln 2\). (Recall that \(\log _{=} \log _{2}\) and \(\left.\ln =\log _{e^{e}}\right)\)

Short answer

(i) Entropy \(H(p_1,...,p_n)\) is always \(\geq 0\), equals 0 when \(n=1\). (ii) \(H(p_1,...,p_n)\leq \log n\), equals \(\log n\) when \(p_i = 1/n\).

Step-by-step solution

Understanding the Problem

The problem involves the Shannon entropy function \(H(p_1, p_2, ..., p_n)\), which is defined as \(-\sum_{i=1}^n p_i \log(p_i)\). We're asked to prove properties of this function under certain conditions.

Proving Non-negativity of Entropy

Since \( p_i > 0 \) for all \( i \), \( \log(p_i) \) is well-defined (negative or zero when \( 0 < p_i \leq 1 \)). Therefore, \( -p_i \log(p_i) \geq 0 \) for each \( p_i \). Summing over all \( i \), we get \( H(p_1, ..., p_n) = -\sum_{i=1}^n p_i \log(p_i) \geq 0 \). This is zero only if there is exactly one probability and it equals 1, which is the case when \( n = 1 \).

Using AM-GM Inequality for Equality Condition

For the equality condition \( n = 1 \), you have only one \( p_i = 1 \). Therefore, \( H(p_1) = -1 \cdot \log(1) = 0 \), confirming equality is possible.

Proving Upper Bound of Entropy

To prove \( H(p_1, ..., p_n) \leq \log n \), consider using a convexity argument. Since \( x \log x \) is a convex function, by Jensen's inequality, we have \( -\sum_{i=1}^{n} p_i \log(p_i) \leq \log(n) \sum_{i=1}^{n} p_i = \log(n) \).

Condition for Equality in Upper Bound

Using the hint given, apply the inequality \( \ln x \leq x - 1 \) to show that \( \sum_{i=1}^n p_i \ln(1/(p_i n)) \leq 0 \), giving equality when all \( p_i = 1/n \). This is checked by substituting \( p_i = 1/n \) into the entropy formula: \( -n \cdot (1/n) \log(1/n) = \log n \).

Conclusion

Based on the calculations, \( H(p_1, ..., p_n) \) satisfies the bounds required and the conditions for equality match those outlined in the problem statement.

Key concepts

Non-negativity of Entropy

Shannon entropy is fundamentally non-negative. This means it can never fall below zero. Entropy, symbolized by \(H(p_1, p_2, ..., p_n)\), measures the unpredictability or disorder within a set of probabilities \(p_i\).
Understanding why entropy is non-negative starts with the fact that each term \(-p_i \log(p_i)\) for probability \(p_i\) is non-negative whenever \(0 < p_i \leq 1\). When you consider this for all terms \(i\) in \(H(p_1, ..., p_n) = -\sum_{i=1}^n p_i \log(p_i)\), the result is a sum that can’t go below zero.
This holds true because the most ordered state, with certainty and no surprise (as in \(n=1\) where all probability is allocated to a single outcome), produces an entropy of zero. However, any other distribution increases disorder, resulting in positive entropy.

Entropy Equality Conditions

Entropy achieves equality at zero uniquely when \(n=1\). Here, the probability distribution is perfectly uniform; that is, there’s no uncertainty since one sole outcome is assured. For any other configuration of probabilities, there is a certain degree of uncertainty, hence \(H(p_1, ..., p_n) > 0\).
Conversely, for the upper bound \(H(p_1, ..., p_n) = \log n\), equality is achieved when all probabilities are equal \(p_1 = p_2 = \cdots = p_n = 1/n\). This setup represents a state of maximum disorder or complete unpredictability because each event is equally likely. Such a uniform distribution distributes maximum entropy, reaching the upper threshold of \(\log n\).

Entropy Upper Bound

Entropy has an upper limit represented mathematically by \(\log n\). This limit signifies the theoretical peak of disorder in a probability system.
When each \(p_i\) is equal, meaning \(p_1 = p_2 = \cdots = p_n = 1/n\), the complexity or surprise is entirely maximized, using the maximum possible space to distribute outcomes. In these cases, calculating entropy involves the formula \(-n \cdot \frac{1}{n} \log(\frac{1}{n})\), which simplifies to \(\log n\).
Thus, entropy can never exceed this value because this would require more than maximum disorder, an impossibility within the defined constraints. This scenario aligns with complete unpredictability in probability distribution.

Convexity and Jensen's Inequality

Convexity is a pivotal mathematical concept, especially when examining functions and their behaviors like that of the entropy function. A function is convex if a line segment joining any two points on its graph does not lie below the graph itself.
Jensen's Inequality comes into play as a powerful tool in proving such properties for convex functions. Specifically, it states that the function value at the weighted average is less than or equal to the weighted average of function values.
This concept supports the idea that given \(x \log x\) is convex, we can leverage Jensen's inequality to establish the upper bound of entropy:

• It implies \(-\sum_{i=1}^n p_i \log(p_i) \leq \log(n)\sum_{i=1}^n p_i = \log(n)\).
• The equality holds (as per entropy equality conditions) when \(p_i = \frac{1}{n}\) for all \(i\), meaning entropy reaches \(\log n\).

This beautifully ties back to how entropy measures disorder: more uniform distribution achieves convexity's equality, a fundamental insight from Jensen's Inequality.