Information theory

f (x, z)

is a bijection of

x

for every fixed

z

, then

H (f (X, Z) ∣ Z) = H (X ∣ Z) .

In particular, translating a random variable in a finite group by a value determined by the conditioning variable does not change its conditional entropy.

Fano's inequality

Let

X

take values in an alphabet of size

m

, let

X

be an estimate determined by

Y

, and put

p_{e} = P (X \neq = X)

. Then

H (X ∣ Y) \leq h_{2} (p_{e}) + p_{e} lo g_{2} (m - 1),

where

h_{2}

is the binary entropy function. The error indicator costs at most

h_{2} (p_{e})

bits, and after an error there are at most

m - 1

possible values of

X

Fano's inequality via an error indicator ( $H (X ∣ Y) \leq h (p_{e}) + p_{e} lo g_{2} (∣ J_{X} ∣ - 1)$ )

For a guess

f (Y)

of a finite-alphabet variable

X

, let

Z = 1_{X \neq = f (Y)}

and

p_{e} = P (Z = 1)

. The chain rule for conditional entropy gives

H (X ∣ Y) = H (Z ∣ Y) + H (X ∣ Z, Y)

. The first term is at most the binary entropy

h (p_{e})

. The second is zero when the guess is right and at most

lo g_{2} (∣ J_{X} ∣ - 1)

when it is wrong, proving

H (X ∣ Y) \leq h (p_{e}) + p_{e} lo g_{2} (∣ J_{X} ∣ - 1)

. This needs no optimality assumption on the guess.

List-decoding Fano inequality ( $p_{e} \geq 1 - {I (J; Y) + lo g 2} / lo g (N / B)$ )

If a uniform index

J

has

N

possibilities and every proposed success neighbourhood contains at most

B < N

possibilities, then any estimator has failure probability at least the displayed expression. Condition on its success indicator: conditional entropy is at most

lo g 2 + (1 - p_{e}) lo g B + p_{e} lo g N

. Subtract this from

lo g N

to bound the mutual information and rearrange. A metric Hamming ball gives approximate recovery rather than exact index decoding.

Entropy of a sum of independent finite-group variables

If independent random variables

X, Y

take values in a finite additive group, then

H (X + Y) \geq max {H (X), H (Y)} .

Indeed,

H (X + Y) \geq H (X + Y ∣ Y) = H (X)

, and symmetrically for

Y

. Independence is essential: taking

Y = - X

makes the sum constant.

Entropy submodularity

For discrete random variables

X, Y, Z

H (X, Y) + H (Y, Z) \geq H (Y) + H (X, Y, Z) .

The difference between the left- and right-hand sides is the nonnegative conditional mutual information

I (X; Z ∣ Y)

Compression of an entropy sum

A union-intersection compression can only decrease the sum of information entropies

\sum_{A \in A} H (X_{A})

for a finite-valued random vector

X

. Each elementary step follows from entropy submodularity; iteration proves the assertion with multiset multiplicities. Uniform coordinate multiplicity gives Shearer inequality by compressing to repeated full sets and empty sets.

Shearer's inequality

Let

X = (X_{1}, \dots, X_{n})

be a discrete random vector, and let

S

be a collection of subsets of

[n]

in which every index occurs at least

r

times. Then

rH (X) \leq \sum_{S \in S} H (X_{S}) .

Apply the chain rule for information entropy to each projection

X_{S}

and use conditioning reduces entropy to compare every term with the corresponding conditional entropy in the full chain rule.

Entropy bound for graphs with isolated-vertex-free intersections ( $∣ F ∣ \leq 2^{n (n - 2) /2}$ )

If every pair of graphs in a family on

[n]

has a graph intersection without an isolated vertex, the family has at most

2^{n (n - 2) /2}

members. At each vertex, its possible graph neighbourhoods form an intersecting family, of size at most

2^{n - 2}

. Every edge occurs in two such neighbourhood projections. Shearer inequality bounds twice the full information entropy by the sum of their information entropies.

Conditional mutual information ( $I (X; Y ∣ Z)$ )

Conditional mutual information is the average information shared by

X

and

Y

after

Z

is known:

I (X; Y ∣ Z) = H (X ∣ Z) - H (X ∣ Y, Z) \geq 0.

Chain rule for mutual information

The information supplied by two observations decomposes as

I (X; Y_{1}, Y_{2}) = I (X; Y_{1}) + I (X; Y_{2} ∣ Y_{1}) .

Data processing inequality for mutual information

X \to Y \to Z

is a Markov chain, then

I (X; Z) \leq I (X; Y), I (X; Z) \leq I (Y; Z) .

Thus deterministic or randomized processing cannot increase the information shared with an unprocessed variable.

Conditional data-processing inequality

X \to Y \to Z

is a Markov chain conditionally on

W

, then

I (X; Z ∣ W) \leq I (X; Y ∣ W) .

It follows by applying ordinary data processing inside every conditional distribution and averaging over

W

Incremental information in a twofold binary repetition code

Send a uniform bit twice through independent binary symmetric channels of crossover probability

p

. The first received bit supplies

1 - h_{2} (p)

bits. Since the received bits disagree with probability

2 p (1 - p)

, the additional information in the second bit is

h_{2} (2 p (1 - p)) - h_{2} (p) .

Entropic Ruzsa distance ( $d_{R} (X, Y)$ )

For finitely supported random variables

X, Y

in a finite additive group, let

X^{'}, Y^{'}

be independent variables with their respective marginal distributions. The entropic Ruzsa distance is

d_{R} (X, Y) = H (X^{'} - Y^{'}) - \frac{1}{2} H (X^{'}) - \frac{1}{2} H (Y^{'}) .

It is symmetric and nonnegative, but can have

d_{R} (X, X) > 0

Conditional entropic Ruzsa distance ( $d_{R} (X ∣ U; Y ∣ V)$ )

For finitely supported random variables, the conditional entropic Ruzsa distance is

d_{R} (X ∣ U; Y ∣ V) = \sum_{u, v} P (U = u) P (V = v) d_{R} (X ∣ U = u, Y ∣ V = v) .

Thus the two conditioning values are sampled independently. If only one variable is conditioned, write

d_{R} (X ∣ U; Y)

Simultaneous conditional entropic Ruzsa distance ( $d_{R} (X; Y ∥ U)$ )

The simultaneous conditional distance samples one value of the conditioning variable for both arguments:

d_{R} (X; Y ∥ U) = \sum_{u} P (U = u) d_{R} (X ∣ U = u, Y ∣ U = u) .

It differs in general from

d_{R} (X ∣ U; Y ∣ U)

, which uses two independently sampled conditioning values.

Conditioned entropic Ruzsa distance of a summand

U, V, X

are independent random variables in

F_{2}^{n}

, then

d_{R} (U ∣ U + V; X) \leq \frac{1}{2} (d_{R} (U; X) + d_{R} (V; X) + d_{R} (U; V)) .

Indeed, conditioning reduces entropy and independence give

d_{R} (U ∣ U + V; X) \leq H (U + X) - \frac{1}{2} H (U) - \frac{1}{2} H (V) + \frac{1}{2} H (U + V) - \frac{1}{2} H (X) .

F_{2}^{n}

V = U + (U + V)

, so conditional entropy under a deterministic change of variables shows that the left-hand side is unchanged when

U

and

V

are exchanged. Averaging the displayed bound with its exchanged version gives the result.

Entropic Ruzsa triangle inequality

The entropic Ruzsa distance satisfies

d_{R} (X, Z) \leq d_{R} (X, Y) + d_{R} (Y, Z) .

For independent representatives this is equivalent to

H (X - Z) + H (Y) \leq H (X - Y) + H (Y - Z) .

Entropic Ruzsa sum-difference inequality

For finitely supported random variables,

d_{R} (X, - Y) \leq 3 d_{R} (X, Y) .

Equivalently, independent

X, Y

satisfy

H (X + Y) + H (X) + H (Y) \leq 3 H (X - Y) .

Entropic Balog-Szemerédi-Gowers theorem

For finitely supported random variables

A, B

in an abelian group,

d_{R} (A; B ∥ A + B) \leq 3 I (A; B) + 2 H (A + B) - H (A) - H (B) .

To prove it, take two conditionally independent copies

(A_{1}, B_{1})

and

(A_{2}, B_{2})

(A, B)

given

A + B

. Since

A_{1} + B_{1} = A_{2} + B_{2}

, entropy submodularity gives

H (A_{1} - B_{2}) \leq H (A_{1} - B_{2}, A_{1}) + H (A_{1} - B_{2}, B_{1}) - H (A_{1} - B_{2}, A_{1}, B_{1}) .

The first two terms are at most

H (A) + H (B)

. The last joint entropy is

2 H (A, B) - H (A + B) .

(3)

Consequently

H (A_{1} - B_{2}) \leq H (A + B) + 2 I (A; B)

. Subtracting

H (A ∣ A + B) = H (B ∣ A + B) = H (A) + H (B) - I (A; B) - H (A + B)

(4)

from this bound proves the theorem.

C-relevant pair of random variables

A pair

(U, V)

C

-relevant to

(X, Y)

when

d_{R} (U; X) + d_{R} (V; Y) \leq C d_{R} (X; Y) .

Relevance of independent self-sums

(U, V)

C

-relevant to

(X, Y)

and

U_{1}, U_{2}, V_{1}, V_{2}

are mutually independent copies, then

(U_{1} + U_{2}, V_{1} + V_{2})

2 C

-relevant to

(X, Y)

. The entropy submodularity for three independent sums implies

d_{R} (U_{1} + U_{2}; X) \leq \frac{1}{2} (2 d_{R} (U; X) + d_{R} (U; U)),

and similarly for

V

. The Entropic Ruzsa triangle inequality bounds

d_{R} (U; U) \leq 2 d_{R} (U; X), d_{R} (V; V) \leq 2 d_{R} (V; Y),

which proves the claim after addition.

Entropy submodularity for three independent sums

For independent finitely supported random variables

X, Y, Z

in a finite additive group,

H (X + Y + Z) + H (Y) \leq H (X + Y) + H (Y + Z) .

This is the data processing inequality for mutual information applied to the Markov chain

X \to X + Y \to X + Y + Z

Entropy submodularity for sums

For independent

U, V, V^{'}

with

V

and

V^{'}

identically distributed,

H (V + V^{'}) + H (U) \leq H (U + V) + H (U + V^{'}) .

This additive form of entropy submodularity follows from data processing and invariance of conditional entropy under translations.

Binary hypothesis testing in information theory

For two probability mass functions

P, Q

, a decision region

B_{n}

accepts

P^{\otimes n}

. Its two error probabilities are

P^{\otimes n} (B_{n}^{c})

and

Q^{\otimes n} (B_{n})

Type I and type II errors

For a null hypothesis

H_{0}

, a Type I error rejects

H_{0}

when it is true, while a Type II error accepts

H_{0}

when the alternative is true. If a test accepts

H_{0}

on an event

A

, their conditional probabilities are

α = P_{0} (A^{c})

and

β = P_{1} (A)

Chernoff information

The Chernoff information between

P

and

Q

C (P, Q) = - min_{0 \leq s \leq 1} lo g \sum_{x} P (x)^{s} Q (x)^{1 - s} .

It is the optimal exponential error rate for Bayesian testing of two independent identically distributed simple hypotheses.

Stein's lemma (information theory)

For distinct probability distributions

P, Q

, the best exponential decay rate of the type-II error

Q^{\otimes n} (B_{n})

among tests whose type-I error

P^{\otimes n} (B_{n}^{c})

stays below any fixed number in

(0, 1)

D (P ∥ Q)

Neyman-Pearson decision region

The Neyman-Pearson lemma says that an optimal region accepting

P

has the likelihood-ratio form

B_{n} = {x_{1}^{n} : \frac{P ^{\otimes n} ( x _{1}^{n} )}{Q ^{\otimes n} ( x _{1}^{n} )} \geq t},

with possible randomization on the boundary.

Total correlation

The total correlation of a random vector is

TC (X_{1}, \dots, X_{n}) = \sum_{i} H (X_{i}) - H (X_{1}, \dots, X_{n}) = D (P_{X_{1}, \dots, X_{n}} ∥ ⨂_{i} P_{X_{i}}) .

It is nonnegative and vanishes exactly when the coordinates are independent.

Type (information theory)

The type, or empirical distribution, of a finite string records the relative frequency of each symbol.

Type class

The type class

T (P)

is the set of all strings of a fixed length whose type is

P

. Every string in one type class has the same probability under any independent identically distributed source law.

Sanov theorem

Sanov's theorem is the large deviation principle for empirical distributions of independent identically distributed observations. On a finite alphabet with sampling law

Q

, its rate function is

D_{e} (R ∥ Q)

Rate-distortion function ( $R (d)$ )

For source

X

and distortion function

d (x, y)

, the rate-distortion function is

R (D) = in f_{P_{Y ∣ X} : E d (X, Y) \leq D} I (X; Y) .

Hamming distortion

Hamming distortion is

d (x, y) = 1_{{x \neq = y}}

, so its expected distortion is the symbol-error probability.

Weakly symmetric channel capacity

If every row of an

m

-output channel matrix is a permutation of every other row and all column sums agree, the uniform input achieves a uniform output and

C = lo g_{2} m - H (one row) .

Binary symmetric channel capacity

A binary symmetric channel with crossover probability

p

has capacity

C = 1 - h_{2} (p)

bits per channel use.

Ternary symmetric channel capacity

For diagonal transition probability

1 - 2 α

and each off-diagonal probability

α

C = lo g_{2} 3 + (1 - 2 α) lo g_{2} (1 - 2 α) + 2 α lo g_{2} α,

with

0 lo g 0 = 0

Information entropy ( $H (X)$ )

For a discrete random variable with probabilities

p_{i}

, its Shannon information entropy is

H = - \sum_{i} p_{i} lo g p_{i} .

Entropy bound with one prescribed probability ( $H \leq h (t) + (1 - t) lo g_{2} (k - 1)$ )

If one probability in a

k

-point distribution equals

t

, normalize the remaining

k - 1

probabilities to

q

. Then

H = h (t) + (1 - t) H (q) \leq h (t) + (1 - t) lo g_{2} (k - 1)

. Equality for

t < 1

means that the remaining probabilities are equal. This combines the binary entropy of the distinguished event with the largest residual Shannon entropy.

Epsilon-sufficient set ( $Pr (X \in S) \geq 1 - ϵ$ )

For a finite-valued random variable, an epsilon-sufficient set

S

retains probability at least

1 - ϵ

. This notion is about covering probability mass and is unrelated to a sufficient statistic. For an IID random variable source, any such set of words with fixed

ϵ < 1

requires exponentially many words at a rate approaching the Shannon entropy.

Minimum size of a sufficient set for an IID source ( $∣ S_{n} ∣ \geq \frac{1 - ϵ}{2} 2^{n (H - δ)}$ )

For finite-alphabet independent and identically distributed random variables, fixed

0 \leq ϵ < 1

and

δ > 0

, every epsilon-sufficient set

S_{n}

of length-

n

words satisfies

∣ S_{n} ∣ \geq (1 - ϵ) 2^{n (H - δ)} /2

for sufficiently large

n

. Intersect

S_{n}

with a typical set whose excluded mass is at most

(1 - ϵ) /2

. The intersection retains that much probability and each word has probability at most

2^{- n (H - δ)}

Differential entropy ( $h (q) = - \int q (x) lo g q (x) d x$ )

The differential entropy of a probability density function is

- E_{q} [lo g q (X)]

when this expected value is defined. Unlike discrete information entropy, it can be negative and depends on the coordinates and reference measure. It is the entropy term in the evidence lower bound for continuous variational inference.

Min-entropy ( $H_{\infty} (X)$ )

For a discrete random variable with largest point probability

p_{m a x}

, its min-entropy is

H_{\infty} (X) = - lo g p_{m a x} .

Information entropy dominates min-entropy

For a discrete random variable,

H (X) \geq H_{\infty} (X)

. Indeed, every point probability satisfies

p_{x} \leq p_{m a x}

, so averaging

- lo g p_{x} \geq - lo g p_{m a x}

proves the inequality.

Chain rule for information entropy

For discrete random variables,

H (X, Y) = H (X) + H (Y ∣ X) .

Iterating gives

H (X_{1}, \dots, X_{n}) = \sum_{i} H (X_{i} ∣ X_{1}, \dots, X_{i - 1})

Subadditivity of information entropy

The chain rule for information entropy and conditioning reduces entropy give

H (X, Y) \leq H (X) + H (Y),

with equality exactly when

X

and

Y

are independent.

Concavity of information entropy

For probability mass functions

P_{1}, \dots, P_{m}

and convex weights

α_{i}

, information entropy satisfies

H (\sum_{i} α_{i} P_{i}) \geq \sum_{i} α_{i} H (P_{i}) .

This follows from the concavity of

- t lo g t

Maximum entropy distribution on a finite set

Among probability distributions on a finite set of

m

elements, the uniform distribution uniquely maximizes information entropy, attaining

lo g m

Maximum entropy on a finite alphabet ( $H (X) \leq lo g_{2} m$ )

An information entropy on at most

m

outcomes is at most

lo g_{2} m

, with equality for the uniform distribution on all

m

outcomes. For the uniform reference

u

, the Kullback-Leibler divergence is

D (p ∥ u) = lo g_{2} m - H (p) \geq 0

, proving the bound.

Maximum entropy distribution on the nonnegative integers

Among distributions on

{0, 1, 2, \dots}

with fixed expected value

μ

, the geometric distribution with success probability

1/ (1 + μ)

uniquely maximizes information entropy. Its entropy is

(1 + μ) h_{2} (\frac{1}{1 + μ}) .

One-to-one source code

A one-to-one source code is an injective function from source symbols to finite codewords. Unlike a prefix code, it need not permit instantaneous decoding of concatenated codewords.

Optimal one-to-one binary code

Order source symbols by decreasing probability and assign the

i

th symbol a binary word of length

⌊ lo g_{2} i ⌋

. This minimizes expected length among one-to-one binary codes because the available shortest words are assigned to the most probable symbols.

Huffman coding

Huffman's algorithm repeatedly combines the

D

least weights for a

D

-ary prefix code and yields an optimal expected length.

Huffman sibling property

Some optimal prefix tree places the two least probable symbols as sibling leaves of maximum depth, which is the inductive basis of Huffman's algorithm.

Optimal prefix code

An optimal prefix code minimizes probability-weighted codeword length among all prefix codes for the source.

Expected codeword length ( $L (c)$ )

For a source symbol

X

and a code

c

, the expected codeword length is

L (c) = E [∣ c (X) ∣] = \sum_{x} P (X = x) ∣ c (x) ∣.

Probability monotonicity of optimal prefix-code lengths

If symbols of probabilities

p_{i} > p_{j}

have codeword lengths

l_{i}

and

l_{j}

in an optimal prefix code, then

l_{i} \leq l_{j}

. Otherwise, exchanging their codewords preserves the prefix property and changes the expected length by

(p_{i} - p_{j}) (l_{j} - l_{i}) < 0,

contradicting optimality.

Deepest sibling property of an optimal prefix code

Every optimal binary prefix code has two codewords of maximal length that differ only in their final bit. Indeed, choose a deepest leaf in the prefix tree. If its sibling were not a codeword, maximality of the depth would make that sibling subtree empty, so the chosen word could be shortened by deleting its final bit. This would preserve prefix-freeness and reduce expected length.

Nonunique optimal prefix code

Distinct tree shapes can have the same minimum expected length, particularly when Huffman merges have ties.

Huffman codeword length bounds

For a largest binary-symbol probability

p_{1}

p_{1} < 1/3

prevents a length-one word, while

p_{1} > 2/5

forces one in a Huffman tree.

r

if there are block encoders with at most

2^{n r}

outputs and corresponding decoders whose probability of reconstructing the first

n

source symbols incorrectly tends to zero as

n \to \infty

Information rate under fixed-length blocking

For a source

(X_{n})

and fixed positive integer

N

, form the block source

Y_{i} = (X_{(i - 1) N + 1}, \dots, X_{i N})

. Whenever the original information rate

h

exists, the blocked source has information rate

N h

, because

\frac{1}{m} H (Y_{1}, \dots, Y_{m}) = N \frac{1}{m N} H (X_{1}, \dots, X_{m N}) .

Asymptotic equipartition property

For a stationary source, typical long blocks have probability approximately

2^{- n H}

; equivalently normalized self-information converges to the entropy rate.

Typical set ( $T_{ε}^{(n)}$ )

For an IID source, the epsilon-typical set consists of words

u^{n}

satisfying

∣ - (1/ n) lo g p (u^{n}) - H (U) ∣ \leq ε

. Its probability tends to one, and its cardinality is at most

2^{n (H (U) + ε)}

Weakly typical sequence

For an IID random variable source with probability mass function

p

, a word

x^{n}

is weakly typical when

∣ - (1/ n) lo g_{2} p (x^{n}) - H (X) ∣ \leq ε

. It has probability on the scale

2^{- n H (X)}

. The weak law of large numbers makes the typical set probable, but does not make every word in it representative: for a uniform source every possible word is weakly typical.

Typical-set cardinality bounds

For a typical set of probability at least

1 - δ

(1 - δ) 2^{n (H - ε)} \leq ∣ T_{ε}^{(n)} ∣ \leq 2^{n (H + ε)} .

The upper bound sums the lower probability bound for each word; the lower bound sums the upper probability bound and uses the set's total probability. These bounds turn the asymptotic equipartition property into exponential estimates of source-coding dimension.

Strongly typical sequence

For a finite-alphabet IID random variable source, a strongly typical word has empirical symbol frequencies within the chosen tolerance of every

p (x)

, and contains no zero-probability symbols. Unlike a weakly typical sequence, this definition controls the individual symbol counts. Both definitions give sets whose probability tends to one for fixed positive tolerance.

Shannon noiseless coding theorem

For binary prefix codes, the optimal expected length

L

obeys

H (X) \leq L < H (X) + 1

Code-distribution correspondence

Lengths of a binary prefix code satisfy

K = \sum_{x} 2^{- L (x)} \leq 1

and therefore define the probability mass function

R (x) = 2^{- L (x)} / K

. Conversely, a mass function gives ideal lengths

- lo g_{2} R (x)

and integer prefix lengths after rounding.

Fixed-rate source-coding error exponent

For an IID finite-alphabet source

Q

encoded at rate

R > H (Q)

, the optimal block error probability has exponential rate

min_{P : H (P) \geq R} D (P ∥ Q) .

Unicity distance

Unicity distance is the ciphertext length at which key equivocation reaches zero and the key becomes uniquely determined under the source model.

Key equivocation

Key equivocation is the conditional entropy

H (K ∣ C^{n})

remaining about a key after observing

n

ciphertext symbols.

Source redundancy in cryptanalysis