Information Theory

Entropy

A measure of the average uncertainty or randomness associated with a random variable. It quantifies the average amount of information needed to specify the outcome of the variable.

Source Coding

The process of representing information from a source using a code, typically aiming for efficient representation (compression) without loss of information.

Channel Capacity

The maximum rate at which information can be transmitted reliably over a communication channel. It is a fundamental property of the channel itself.

Mutual Information

The amount of information that one random variable contains about another. It represents the reduction in uncertainty about one variable due to knowing the other.

Entropy of a Discrete Random Variable

Measures the average information content or uncertainty of X. Measured in bits if log base 2 is used.

H(X) = - Σ_i=1^{n} p(x_i) log₂(p(x_i))

Joint Entropy

Measures the uncertainty of the pair (X,Y).

H(X,Y) = - Σ_i=1^{n} Σ_j=1^{m} p(x_i, y_j) log₂(p(x_i, y_j))

Conditional Entropy

Measures the remaining uncertainty in Y after X is known.

H(Y|X) = H(X,Y) - H(X) = - Σ_i=1^{n} Σ_j=1^{m} p(x_i, y_j) log₂(p(y_j|x_i))

Mutual Information

Measures the amount of information that X provides about Y (and vice versa). It's the reduction in uncertainty.

I(X;Y) = H(Y) - H(Y|X) = H(X) - H(X|Y) = H(X) + H(Y) - H(X,Y)

Channel Capacity (C)

The maximum mutual information achievable between the channel input X and output Y, maximized over all possible input distributions p(x).

C = max_p(x) I(X;Y)