Shannon Entropy

Shannon Entropy

Shannon entropy measures the average uncertainty in a probability distribution. Given a discrete random variable $X$ with probability mass function $p(x)$:

$H(X) = -\sum_{x} p(x) \log_2 p(x) \quad \text{bits}$

(Terms where $p(x) = 0$ are defined as $0 \cdot \log_2 0 = 0$ by convention.)

Key Properties

Uniform Entropy

For a uniform distribution over $n$ equally likely outcomes:

$H_{\text{uniform}}(n) = \log_2 n$

This is the maximum possible entropy for any distribution over $n$ outcomes — uniform distributions are the most uncertain.

Example

For a fair coin ($p = 0.5$ each): $H = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1$ bit.

For a biased coin ($p = 0.9$, $1-p = 0.1$): $H \approx 0.469$ bits (less uncertainty).

import math

def shannon_entropy(probs):
    return sum(-p * math.log2(p) for p in probs if p > 0)

print(shannon_entropy([0.5, 0.5]))  # 1.0
print(shannon_entropy([0.25]*4))    # 2.0

Your Task

Implement:

• shannon_entropy(probs) — $H(X)$ for a list of probabilities (skip zeros)
• uniform_entropy(n) — $\log_2 n$
• max_entropy_dist(n) — returns $[1/n, 1/n, \ldots]$ (list of $n$ equal probs)