# Information Entropy

Created:
2023-07-22

Updated:
2023-09-02

Entropy is the basic measure to quantify the information yielded by some source.

The measure has been mostly introduced and studied by Shannon (~1948) as part of
the broader area of **information theory**, which represents the foundation of
modern correction, compression and cryptographic codes.

## Introduction

**Entropy**. Given a random variable `X`

, the entropy of `X`

is the measure
of uncertainty on the result of `X`

.

Entropy is closely related to **information content**, and in fact, they are
often used interchangeably. For a data source, the higher is its entropy the
more information a particular message extraction contains in general.

The entropy of a data source also implicitly defines how much we can
**compress** the yielded information. In practice, in this context, entropy can
be seen as the inverse of **redundancy**.

## Random Variable Information

If `X`

is a data source that yields symbols of an alphabet and `x ∈ X`

is a
particular instance of `X`

(aka an event), we can model `X`

as a random variable
by assigning a probability value to each event `x ∈ X`

such that `Pr(x) ∈ [0, 1]`

and `∑ₓ Pr(X = x) = 1`

.

From now on, for conciseness we are going to alias `Pr(X = x)`

with `p(x)`

.

When analyzing the entropy of a data source `X`

its probability distribution is
assumed to be known.

We want to quantify the information gained from the observation of a particular
instance `x`

of the variable `X`

.

When a particular instance `x`

is observed, if `p(x)`

is small then the
information gain associated with the event for an observer is high. In contrast,
if `p(x)`

is high then the event doesn’t provide a lot of new information
because the event was already expected to happen.

The **information** gained by observing the event `x`

is thus some kind of
inverse of `p(x)`

, in particular it is defined as the logarithm in base `2`

of
the inverse:

```
I(x) = log₂(1/p(x))
```

The `log₂`

is used because we are reasoning in terms of bits of information.

For example:

```
p(x) = 1/2 → I(x) = 1 (one bit of information, i.e. true/false)
p(x) = 1/8 → I(x) = 3
```

The logarithm has some nice properties we rely on, we want that the information
provided by two independent events `x`

and `y`

to be equal to the sum of the
two information:

```
I(x,y) = log₂(1/p(x,y)) = (the events are independent, thus..)
= log₂(1/(p(x)p(y))) = (for the log properties..)
= log₂(1/p(x)) + log₂(1/p(y))
= I(x) + I(y)
```

## Entropy

The entropy of a data source modeled as a random variable `X`

is defined as the
**expected value** of the information `I`

defined as `x ∈ X`

varies:

```
H(X) = E[I(x)] = ∑ₓ p(x)·log₂(1/p(x)) for x ∈ X with p(x) ≠ 0
```

Given that the more an event is unlikely and the more information its observation yields, entropy can be equivalently defined as the measure of the average uncertainty associated to an event of a random variable (data source).

The entropy grows with the number of possible events.

The closer `X`

is to the **uniform distribution** the greater is the entropy,
and if all the elements have the same probability of being observed, then
this is the situation where on average we are mostly surprised to observe one
specific event.

The opposite case is when the probability is concentrated on a smaller set of
elements. The surprise factor associated with high probable events is low and
thus the overall `H(x)`

value is lowered.

**Proposition**

`H(X) = 0`

iff`X`

deterministically yields one single element.`H(X) = log₂(|X|)`

iff`X`

has a uniform distribution.

*Proof* (one way only)

If `X`

deterministically yields the element `k`

then `p(k) = 1`

:

```
H(X) = p(k)·log₂(1/p(k)) = log₂1 = 0
```

If `X`

is uniform then `p(x) = 1/|X|`

for every `x`

:

```
H(X) = ∑ₓ 1/|X|·log₂(|X|) = |X|·1/|X|·log₂(|X|)
```

**Proposition**. For any random variable `X`

```
0 ≤ H(X) ≤ log₂(|X|)
```

*Proof*

The left-hand trivially follows the entropy definition.

The right-hand side intuitively follows the fact that we have max entropy when
`X`

has a uniform distribution. For a formal proof we need to resort to the
Jensen’s inequality:

```
E[f(Y)] ≤ f(E[Y]). Setting Y = 1/p(X):
→ E[log₂(1/p(X))] = H(X) ≤ log₂(E[1/p(X)]) = log₂(|X|)
```

Which follows from `E[1/p(X)] = ∑ₓ p(x)·1/p(x) = ∑ₓ 1 = |X|`

∎

Example. `X`

is the result of throwing a `6`

faces die.

Fair die: `p(x) = 1/6`

```
H(X) = -[p(1)·log₂(p(1)) + ... + p(6)·log₂(p(6))]
= -[1/6·log₂(1/6) + ... + 1/6·log₂(1/6)]
= -6·1/6·log₂(1/6) = log₂6 ≈ 2.58
```

Unfair die: `p(5) = 1`

and `p(i≠5) = 0`

```
H(X) = -p(5)·log₂(p(5)) = -1·log₂1 = 0
```

Biased die: `p(1) = 1/2`

and `p(x) = 1/10 ∀x ≠ 1`

```
H(X) = -[p(1)·log₂(p(1)) + p(2)·log₂(p(2)) + ... + p(6)·log₂(p(6))]
= -[1/2·log₂(1/2) + 5/10·log₂(1/10)]
= 1/2 + 1/2·log₂10 = (1 + log₂10)/2 ≈ 2.16
```

Note that `2^(2.58) ≈ 6`

are the total number of possible events `|X|`

.

Thus, the max entropy corresponds to the power of two that gives back the number of possible outcomes in a uniform distribution.

## Joint Entropy

Given two random variables `X`

and `Y`

, the couple `(X,Y)`

is still random
variable. Follows that we can compute `H(X,Y)`

.

The values of `(X,Y)`

are distributed according to the joint probability
distribution `p(X,Y)`

:

```
H(X,Y) = -∑ₓᵧ p(x,y)·log₂(p(x,y))
```

(Remember, for a joint probability distribution `∑ₓᵧ p(x,y) = 1`

)

## Conditional Entropy

The intuitive meaning of `H(X|Y)`

is the average residual uncertainty for `X`

after that an event of `Y`

has been observed.

Let `X`

and `Y`

be two random variables. The conditional probability of `X`

given `Y`

is written as `p(X|Y)`

and is defined as the probability of an event
of `X`

to happen after that an event of `Y`

has been observed.

The conditional probability is still a probability distribution, but typically
defined on a smaller set of elements with respect to `X`

.

Computing the conditional entropy is just a matter of using conditional
probabilities for the single events of `X`

given the event `Y = y`

:

```
H(X|Y=y) = -∑ₓ p(x|y)·log₂(p(x|y))
```

(Remember, for a conditional probability distribution `∑ₓ p(x|y) = 1`

)

We now define the expected entropy of `X`

after the observation a generic event
`y ∈ Y`

:

```
H(X|Y) = ∑ᵧ p(y)·H(X|y)
= ∑ᵧ [p(y) · -∑ₓ p(x|y)·log₂(p(x|y))]
= -∑ₓᵧ p(x,y)·log₂(p(x|y))
```

Equivalently

```
H(X|Y) = -E[log₂(p(X|Y))] = E[I(x|y)]
```

Example:

`X = {1,..,6}`

outcome of a fair die roll;`Y = 0`

if the outcome is even and`Y = 1`

if is odd.

Given the event `Y = 0`

, then the new probability distribution for `X`

is:

```
p(X=2|Y=0) = p(X=4|Y=0) = p(X=6|Y=0) = 1/3
p(X=1|Y=0) = p(X=3|Y=0) = p(X=5|Y=0) = 0
H(X|Y=0) = -3·1/3·log₂(1/3) = log₂3 ≈ 1.58
```

The same value is obtained for `Y = 1`

.

Thus, as expected, in the fair die roll removing half of the possibilities reduces the entropy by one bit.

```
H(X|Y=0) = H(X|Y=1) ≈ log₂3
→ H(X|Y) = 1/2·H(X|Y=0) + 1/2·H(X|Y=1) ≈ log₂3 = 1.58
```

For a biased die where `p(X=1) = 1/2`

and `p(X=k) = 1/10`

, `∀k ≠ 1`

```
H(X) = 1/2·log₂2 + 5·1/10·log₂10 ≈ 2.16
```

We set `Y=0`

iff `X=1`

and `Y=1`

otherwise. The events are equally probable.

```
p(X=1|Y=0) = 1 and p(X≠1|Y=0) = 0
p(X=1,Y=0) = p(Y=0)·p(X=1|Y=0) = 1/2·1 = 1/2
→ H(X|Y=0) = p(X=1,Y=0)·log₂(1/p(X=1|Y=0)) = 1/2·log₂1 = 0
```

In this case knowing that the outcome of `Y`

completely determine `X`

.

```
p(X=1|Y=1) = 0 and p(X=k|Y=1) = 1/5, ∀ k ≠ 1
p(X=k,Y=1) = p(Y=1)·p(X=k|Y=1) = 1/2·1/5 = 1/10
→ H(X|Y=1) = ∑ₖ p(X=k,Y=1)·log₂(1/p(X=k|Y=1)) = 5·1/10·log₂5 1/2·log₂5 ≈ 1.16
```

In this case knowing that the outcome is `>1`

reduces the entropy by one bit.

Reducing the entropy of one bit doesn’t imply the removal of half of the
possible outcomes. Instead, it signifies the elimination of one or more possible
events whose combined probabilities equal `1/2`

.

### Chain Rule

```
H(X,Y) = H(Y) + H(X|Y)
```

Proof.

```
H(X,Y) = -∑ₓᵧ p(x,y)·log₂p(x,y)
= -∑ₓᵧ p(x,y)·log₂(p(y)·p(x|y))
= -∑ₓᵧ p(x,y)·[log₂p(y) + log₂p(x|y)]
= -∑ₓᵧ [p(x,y)·log₂p(y) + p(x,y)·log₂p(x|y)]
= -∑ₓᵧ p(x,y)·log₂p(y) + -∑ₓᵧ p(x,y)·log₂p(x|y)
= -∑ᵧ p(y)·log₂p(y) + -∑ₓᵧ p(x,y)·log₂p(x|y)
= H(Y) + H(X|Y)
```

∎

Note that since `p(X,Y) = p(Y,X)`

then `H(X,Y) = H(Y,X)`

.

Example for the die roll with `Y = 0`

iff `X`

is even and `Y = 1`

otherwise:

```
H(X,Y) = H(X) + H(Y|X) = log₂6 + 0 = log₂6
H(Y,X) = H(Y) + H(X|Y) = log₂2 + log₂3 = log₂6
```

Follows that, when possible, it is always convenient to compute the conditional probability that has a zero value.

**Corollary**. When `Y`

is a function of `X`

(`X`

completely determines `Y`

)
then `H(X,Y) = H(X)`

.

Proof: `H(X,Y) = H(X) + H(Y|X) = H(X) + 0 = H(X)`

**Proposition**. `H(X,Y) ≤ H(X) + H(Y)`

.

Easily proven because `H(Y|X) ≤ H(Y)`

and `H(X|Y) ≤ H(X)`

. We have the equality
only when `X`

and `Y`

are independent.

```
H(X,Y) = H(X) + H(Y|X) ≤ H(X) + H(Y)
```

All these properties can be generalized to arbitrary sized tuples.

## Mutual Information

**Definition**. The quantity `I(X;Y) = H(X) - H(X|Y) `

is known as **mutual
information** between `X`

and `Y`

and represents how many bits of information
relative to `X`

the observation of `Y`

yields. Obviously `0 ≤ I(X;Y) ≤ H(X)`

.

`I(X;Y) = 0`

when the two events are independent (`H(X|Y) = H(X)`

).`I(X;Y) = H(X)`

when the observation of`Y`

completely determines the value of`X`

(`H(X|Y) = 0`

)

**Proposition**. `I(X;Y) = I(Y;X)`

*Proof*. For the chain rule:

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

∎

Example for the die roll with `Y = 0`

if `X`

is even and `Y = 1`

otherwise:

```
I(X;Y) = H(X) - H(X|Y) = log₂6 - log₂3 = 1
I(Y;X) = H(Y) - H(Y|X) = log₂2 - 0 = log₂2 = 1
```

In the second case note that observing `X`

gives full information about `Y`

.

## Residual Possibilities Bound

Given `|Xᵧ| = |{x: p(x|y) > 0}|`

the number of events of `X`

that are possible
after the observation of the event `Y = y`

.

We are interested in the expected value of `|Xᵧ|`

after the observation of a
generic event `y ∈ Y`

.

```
E[|Xᵧ|] = ∑ᵧ p(y)·|Xᵧ| , ∀ y ∈ Y
```

Because `H(X|Y)`

are the average bits of uncertainty after the observation of
a generic event `y ∈ Y`

then as the upper bound to the entropy we can use the
average elements of `X`

after the observation of the same variable `Y`

:

```
0 ≤ H(X|y) ≤ log₂(|Xᵧ|)
```

Taking the average values over `Y`

and using the *Jensen’s Inequality*

```
0 ≤ ∑ᵧ p(y)·H(X|y) ≤ ∑ᵧ p(y)·log₂(|Xy|)
0 ≤ H(X|Y) ≤ E[log₂(|Xy|)] ≤ log₂(E[|Xy|])
```

And thus

```
1 ≤ 2^H(X|Y) ≤ E(|Xy|).
```

Example. For die roll `H(X|Y) = log₂3`

, thus `E[|Xy|] ≥ 2^log₂3 = 3`

## Kullback-Leibler Divergence

Also known as KL divergence or relative entropy, is a measure of how much two probability distributions are different from each other.

**Definition**. Given two probability distributions `p`

and `q`

defined for the
same variable `X`

, KL divergence measures some kind of *distance* between the
two distributions.

```
D(p||q) = ∑ₓ p(x)·log₂(p(x)/q(x)) ∀x ∈ X
```

With the convention that:

```
0·log₂(0/q) = 0 for q ≥ 0
p·log₂(p/0) = +∞ for p ≥ 0
```

Note that it is not a distance in the strict mathematical sense of the term,
as triangle inequality doesn’t hold and `D(p||q) ≠ D(q||p)`

.

Furthermore, it is additive for independent distributions.

**Gibbs Inequality**

```
D(p||q) ≥ 0, with D(p||q) = 0 iff p = q
```

*Proof*

Given that `log₂x = logₑx/logₑ2`

, we’ll use `logₑ`

instead of `log₂`

as `logₑ2`

only scales the relation we want to prove.

Because `logₑx ≤ x - 1`

for all `x > 0`

, with equality iff `x = 1`

, We have:

```
D(p||q) = -∑ₓ p(x)·logₑ(q(x)/p(x)) ≥ -∑ₓ p(x)·(q(x)/p(x) - 1)
= -∑ₓ q(x) + ∑ₓ p(x) = 1 - ∑ₓ q(x)
```

In the sums we consider only the indexes for whom `p(x) > 0`

, follows that some
non-zero `q(x)`

values may have been excluded from the sums and thus
`0 ≤ ∑ₓ q(x) ≤ 1`

. The thesis follows.

∎

`logₑx ≤ x - 1`

can be easily proven using calculus to study the critical points
of the function `f(x) = x - logₑx - 1`

(i.e. find local minima using derivative).

### Application to Hypothesis Testing

Hypothesis testing is a statistical methodology where we are required to choose
between two hypotheses: `H0`

and `H1`

who correspond to two possible
distributions `p`

and `q`

.

Given a random variable `X`

we want to decide if it follows the distribution
`p`

or `q`

, and thus to check which of the hypothesis is correct.

`H0`

is called **null hypothesis** and `H1`

is called **alternative hypothesis**.

The process involves calculating a test statistic and determining the
corresponding *p-value*, which represents the probability of observing a test
statistic as extreme or more extreme than the one calculated, given that the
null hypothesis is true.

A *statistic* is a single value computed from a sample of data summarizing
some aspects of the sample and used to make inferences about the population.
Example statistics are *mean*, *median* and *mode* of a dataset.

**Log-Likelihood Ratio (LLR)**

For each independent event `x ∈ X`

we compute the LLR:

```
LLR = log₂(p(x)/q(x))
```

For each event:

- If
`LLR > 0`

, i.e.`p(x)/q(x) > 1`

, then the event`x`

is more probable under`H0`

than under`H1`

. - If
`LLR < 0`

, i.e.`p(x)/q(x) < 1`

, then the event`x`

is more probable under`H1`

than under`H0`

. - If
`LLR = 0`

then are equally likely.

We then calculate the `LLR`

empirical expected value as:

```
E[LLR] = 1/|X| · ∑ₓ log(p(x)/q(x)), ∀ x ∈ X
```

- If
`H0`

is true:`E[LLR]`

converges to`∑ₓ p(x)·log₂(p(x)/q(x)) = D(p||q)`

- If
`H1`

is true:`E[LLR]`

converges to`∑ₓ q(x)·log₂(p(x)/q(x)) = -∑ₓ q(x)·log₂(q(x)/p(x)) = -D(q||p)`

Follows that if `H0`

is true `E[LLR] ≥ 0`

else `E[LLR] < 0`

Note that the test can fail:

**False positive**: if we incorrectly reject`H0`

.**False negative**: if we incorrectly accept`H0`

.

The test error probability can be quantified.

#### Chernoff-Stein Lemma

The decision error probability respects the following laws (`k = |X|`

):

- The false positive probability
`α`

decreases asymptotically as`2^(-k·D(q||p))`

- The false negative probability
`β`

decreases asymptotically as`2^(-k·D(p||q))`

In both cases we assume that both `D(p||q)`

and `D(q||p)`

are less than `+∞`

.

Because in general `D(p||q) ≠ D(q||p)`

then `α ≠ β`

.

Example with coin toss.

```
p = {1/2, 1/2}, q = {3/5, 2/5}
D(p||q) = 1/2·log₂(1/2·5/3) + 1/2·log₂(1/2·5/2) ≈ 0.029
D(q||p) = 3/5·log₂(3/5·2/1) + 2/5·log₂(2/5·2/1) ≈ 0.093
α ≈ 2^(-k·0.093) , β ≈ 2^(-k·0.029)
```

Using these estimations we can arbitrarily lower the error probability, for example:

```
α ≈ 2^(-k·D(q||p)) < ε → k > -log₂ε/D(q||p)
```

## Cross Entropy

When we decide what is the optimal encoding for a language that we empirically
observed then we may end up using a distribution `q`

that is not equal to the
real distribution driving the data source `p`

.

Using the code determined by `q`

when the real distribution is `p`

gives us an
average encoding for a symbol `x`

:

```
H(X;p||q) = ∑ₓ p(x)·|c(x)| ≈ ∑ₓ p(x)·log₂(1/q(x))
```

Where `c(x)`

is the encoding of the symbol `x`

.

In general:

`H(X;p||q)`

is not an entropy value (in the strict sense)`H(X;p||q) ≠ H(X;q||p)`

`H(X) ≤ H(X;p||q)`

The last statement proof is a corollary of Gibb’s inequality:

```
D(p||q) = ∑ₓ p(x)·log₂(p(x)/q(x)) = ∑ₓ p(x)·(log₂p(x) - log₂q(x))
= ∑ₓ p(x)·log₂p(x) - ∑ₓ p(x)·log₂q(x) ≥ 0
→ ∑ₓ p(x)·log₂p(x) ≥ ∑ₓ p(x)·log₂q(x)
→ H(X) = -∑ₓ p(x)·log₂p(x) ≤ -∑ₓ p(x)·log₂q(x) = H(X;p||q)
```

**Linking Identity**:

```
H(X;p||q) = H(X) + D(p||q)
```

*Proof*. Let’s assume that `q(x) ≥ 0`

.

```
H(p||q) = ∑ₓ p(x)·log₂(1/q(x))
= ∑ₓ p(x)·log₂(1/p(x)·p(x)/q(x))
= ∑ₓ (p(x)·log₂(1/p(x)) + p(x)·log₂(p(x)/q(x)))
= ∑ₓ p(x)·log₂(1/p(x)) + ∑ₓ p(x)·log₂(p(x)/q(x))
= H(p) + D(p||q)
```

## Other Properties

**Proposition**. Given `pₓᵧ = p(X,Y)`

, `pₓ = p(X)`

, `pᵧ = p(Y)`

```
I(X;Y) = H(X) - H(X|Y) = D(pₓᵧ||pₓ·pᵧ)
```

Recall that:

`I(X;Y) = 0`

if`X`

and`Y`

are independent.`I(X;Y) = H(X)`

is`X`

is completely determined by`Y`

.

*Proof*.

Starting from `D(pₓᵧ||pₓ·pᵧ)`

, using the logarithm additive property and given
that `H(X,Y) = H(Y) + H(X|Y) → H(Y) - H(X,Y) = -H(X|Y)`

```
D(pₓᵧ||pₓ·pᵧ) = ∑ₓᵧ pₓᵧ(x,y)·log₂[pₓᵧ(x,y)/(pₓ(x)·pᵧ(y))] =
= ... (some exapansions)
= H(X) + H(Y) - H(X,Y) = H(X) - H(X|Y)
= I(X;Y)
```

∎

**Proposition**. Observing an event, in general, doesn’t increment the entropy
of another event.

```
0 ≤ H(X|Y) ≤ H(X)
```

*Proof*

First inequality follows from `H(X|Y)`

definition, a sum of positive quantities.
Second inequality proof: `H(X|Y) = H(X) - I(X;Y) = H(X) - D(pₓᵧ||pₓ·pᵧ) ≤ H(X)`

.

∎

**Corollary**.

```
H(X,Y) ≤ H(X) + H(Y)
```

*Proof*

```
H(X,Y) = H(X) + H(Y|X) ≤ H(X) + H(Y)
```

∎

The equality holds when `X`

and `Y`

are independent.

**Corollary**.

```
I(X;Y) ≥ 0
```

*Proof*. Follows because it is equal to `D(pₓᵧ||pₓ·pᵧ)`

and the Gibbs
inequality. The equality to `0`

holds when `pₓᵧ = pₓ·pᵧ`

, i.e. when `X`

and `Y`

are independent.

∎

Practical consideration. If we construct a compression code that operates
on *digrams*, but we don’t know the exact distribution of the couples in the
language of choice, we may decide to approximate `pₓᵧ`

with `pₓ·pᵧ`

.

Because in a natural language `X`

and `Y`

are not independent, the encoding
in this case can’t be optimal, and the extra bits used by our code are exactly
`D(pₓᵧ||pₓ·pᵧ)`

.

*Example*. (somehow counterintuitive) Observation of an event which increments
the entropy

```
X ∈ { 1,..,6}
p(1) = 1-10⁻⁹ and p(k) = 1/5·10⁻⁹ for k ≠ 1
H(X) ≈ 0 since it is very probable that X = 1
If we find out that the result is one (not specified) z ≠ 1, then
p(1|z) = 0
p(x|z) = 1/5, for x≠1
H(X|z) = -∑ p(x|z)·log₂p(x|z) = -5·1/5·log₂(1/5) = log₂5 ≈ 2.32
→ H(X|z) ≥ H(X)
```

**Important**. The proposition `H(X|Y) ≤ H(X)`

is still valid since it refers to
the expected value over all the possible values of `Y`

and not to the entropy of
`X`

after one specific event `y ∈ Y`

.

## Appendix - Jensen’s Inequality

For any differentiable concave function `f`

and random variable `X`

```
E[f(X)] ≤ f(E[X])
```

*Proof*

For a concave function `f`

and any `x`

and `y`

:

```
(f(x) - f(y))/(x - y) ≤ f'(x)
→ f(x) ≤ f(y) + f'(x)·(x - y)
```

Let `x = X`

and `y = E[X]`

. We can write

```
f(X) ≤ f(E[X]) + f'(X)·(X - E[X])
```

This inequality is true for all `X`

, so we can take the expected value on both
sides to get

```
E[f(X)] ≤ f(E[X]) + f'(E[X])·E(X - E[X]) = f(E[X])
```

∎

## References

- Douglas Stinson, Cryptography Theory and Practice