Information Theory

Information theory is the mathematical study of the quantification, storage, and communication of information. It was founded by Claude Shannon in 1948.

Entropy

Entropy $H(X)$ measures the uncertainty or surprise associated with a random variable $X$. $H(X) = -\sum_{i} P(x_i) \log_b P(x_i)$ Usually, $b=2$ for bits (Shannon entropy).

import math

def calculate_entropy(probabilities):
  entropy = 0
  for p in probabilities:
      if p > 0:
          entropy -= p * math.log2(p)
  return entropy

# Fair coin
print(f"Fair coin entropy: {calculate_entropy([0.5, 0.5])} bits")

# Biased coin (90% heads)
print(f"Biased coin entropy: {calculate_entropy([0.9, 0.1]):.3f} bits")

# Single certain outcome
print(f"Certain outcome entropy: {calculate_entropy([1.0])} bits")

Mutual Information and Kullback-Leibler Divergence

Kullback-Leibler (KL) Divergence, or relative entropy, measures the “distance” (though not a true metric) between two probability distributions $P$ and $Q$: $D_{KL}(P || Q) = \sum_{x \in \mathcal{X}} P(x) \log_2 \left( \frac{P(x)}{Q(x)} \right)$

It quantifies the information lost when $Q$ is used to approximate $P$.

Mutual Information $I(X; Y)$ measures the reduction in uncertainty of $X$ given the knowledge of $Y$: $I(X; Y) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P(x, y) \log_2 \left( \frac{P(x, y)}{P(x)P(y)} \right)$

It is related to entropy by: $I(X; Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X, Y)$.

import math

def kl_divergence(P, Q):
  # D_KL(P || Q) - Sum P(x) log(P(x)/Q(x))
  res = 0
  for p, q in zip(P, Q):
      if p > 0:
          res += p * math.log2(p / q)
  return res

P = [0.1, 0.9]
Q = [0.5, 0.5]
print(f"KL Divergence D_KL(P || Q): {kl_divergence(P, Q):.3f}")

def mutual_information(joint_prob, p_x, p_y):
  # I(X;Y) = Sum P(x,y) log(P(x,y)/(P(x)P(y)))
  mi = 0
  for x in range(len(p_x)):
      for y in range(len(p_y)):
          pxy = joint_prob[x][y]
          if pxy > 0:
              mi += pxy * math.log2(pxy / (p_x[x] * p_y[y]))
  return mi

# Example: X and Y are highly correlated
px = [0.5, 0.5]
py = [0.5, 0.5]
joint = [[0.45, 0.05], [0.05, 0.45]]
print(f"Mutual Information I(X; Y): {mutual_information(joint, px, py):.3f}")

Source Coding Theorem

Shannon’s Source Coding Theorem establishes that the minimum number of bits needed to represent a source is its entropy. Huffman Coding is a common algorithm to achieve this bound.

Channel Capacity

The Shannon-Hartley Theorem defines the maximum rate $C$ at which information can be transmitted over a noisy channel with bandwidth $B$ and signal-to-noise ratio $S/N$: $C = B \log_2(1 + S/N)$