- tags
- Complexity metrics
- references
- (Shannon and Weaver 1975)

For a discrete random variable \(X\) with outcomes \(x_i\),
\(P(X=x_i) = P_i\), the **entropy** or
**uncertainty function** of \(X\) is defined as \[
H(X) = -\sum_{i=1}^{N} P_i \log P_i \]

Entropy is always positive, and is maximized when the uncertainty is maximal, that is when \(P_1 = P_2 = … = P_N = \frac{1}{N}\) entropy in that case is \(\log N\).

Interpretations:

- \(H\) measures uncertainty of a process (or the average number of yes/no answers one needs to specify the value of \(i\)).
- Average information received by an observer when reading the outcomes of \(X\).

If we encode the random variable \(X\) with an erroneous encoding \(P_i'\), the resulting code length is \(\sum P_i \log \frac{1}{P_i'}\). The difference between this encoding and the optimal encoding is the Kullback-leibler divergence.

## Shannon entropy for a sequence

In the case of a sequence of symbols $s_1, …, s_i, …$, following a translation invariant distribution (for any \(n\) and \(k\), \(P(s_1s_2…s_n) = P(s_{1+k}s_{2+k}…s_{n+k})\)).

We can define the block entropy of the $n$-tuple random variable \(S=(S_1…S_n)\) like above \[ H_n = \sum_{s_1…s_n} P(s_1…s_n) \log P(s_1…s_n) \]

Then, we can define the average length of the description per symbol of the sequence as \[ h =\lim_{n \rightarrow \infty} h_n \] \[ h_n =H_{n+1} - H_n \]

\(h\) is called by Shannon the entropy of the source emitting the sequence, or entropy of the sequence.

## Bibliography

Shannon, Claude E., and Warren Weaver.
1975. *The Mathematical Theory of Communication*. Urbana:
University of Illinois Press.