> [!theorem] > > Let $X$ be a [[Random Variable|random variable]] with [[Probability Distribution|probability distribution]] $\list{p}{n}$, its [[Entropy|entropy]] is bounded by: > $ > H(X) \le H_b(p_1) + (1 - p_1)\log(n - 1) > $ > Where $H_b(p_1)$ is the binary entropy of a [[Bernoulli Random Variable|Bernoulli distribution]] with $p = p_1$. > > *Proof*. Let $Y$ be a random variable with probability distribution $\list{q}{n - 1}$, where each $q_j = \frac{p_{j + 1}}{1 - p_1}$. > $ > \begin{align*} > H(X) &= -\sum_{j = 1}^{n}p_j\log_2(p_j) \\ > &= -p_1\log_2(p_1) - \sum_{j = 1}^{n}p_{j + 1}\log_2(p_{j + 1}) \\ > &= -p_1\log_2(p_1) - \sum_{j = 1}^{n}(1 - p_1)\frac{p_{j + 1}}{1 - p_1}\log_2(p_{j + 1}) \\ > &= -p_1\log_2(p_1) - (1 - p_1)\sum_{j = 1}^{n}\frac{p_{j + 1}}{1 - p_1}\paren{\log_2\paren{\frac{p_{j + 1}}{1 - p_1}} + \log_2(1 - p_1)} \\ > &= -p_1\log_2(p_1) - (1 - p_1)\log_2(1 - p_1) - (1-p_1)\sum_{j = 1}^{n}\frac{p_{j + 1}}{1 - p_1}\log_2(p_{j + 1}) \\ > &= H_b(p_1) + (1 - p_1)H(Y) > \end{align*} > $ > > Since the [[Uniform Distribution|uniform distribution]] satisfies the [[Principle of Maximum Entropy|principle of maximum entropy]], any other distribution must have equal or less entropy, meaning that > $ > \begin{align*} > H(Y) &\le H_{n - 1} = \log_2(n - 1) \\ > H(X) &\le H_b(p_1) + (1 - p_1)\log_2(n - 1) > \end{align*} > $