Mutual information

The mutual information between discrete random variables is

I (X; Y) = H (Y) - H (Y ∣ X) = H (X) + H (Y) - H (X, Y) .

Table of contents

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

If

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

If

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) .

 Ancestors (5)

 Incoming links (21)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Mutual information by

Wikipedia Bot  1

Mutual information is a fundamental concept in information theory that measures the degree of dependence or association between two random variables. It quantifies the amount of information obtained about one random variable through the other. In essence, mutual information captures how much knowing one of the variables reduces uncertainty about the other.

 Read the full article

  See all articles in the same topic Create my own version