Interesting properties of the entropy function

Update 2017-07-03: Corrected equation for associative definition, thank you /u/Syrak.

This may not be the first time someone recognized this, but I have recently discovered some interesting and useful properties of the entropy function and now share them.

First a definition:

Entropy — H(p₁, p₂, ..., p_n) — is a function that quantifies surprise in selecting an object from a set where the probability of selecting each object is given: {p₁, p₂, ..., p_n}. This has utility in communications, information theory and other fields of math.

H_b(p₁, p₂, ..., p_n) = Σ(i..n)-p_ilog_b(p_i)

where b is normally 2, to express entropy in bits.

Other definitions of H() use expected values and random variables. As an analog to the definition above, I will discuss entropy of a set of frequencies. p_i = f_i / Σ f_i.

Entropy defined without bits:

A definition that doesn't use bits is:

H(p₁, p₂, ..., p_n) = Π(i..n) p_i^-p_i

And you can convert between the definitions with H_b = log_b H. H() is also called perplexity.

A recursive (associative) definition of entropy:

The entropy function is associative. Or maybe it should be said that the entropy function can be applied recursively. Consider the function as applying to frequencies (rather than probabilities).

If we have the frequencies f = {17, 24, 16, 0, 9}, we can find the entropy H(f) if we have a bifurcation of the set f_a + f_{b =} f, entropy of the bifurcations H(f_a), H(f_b), and the total of each set's frequency, Σ f_a, Σ f_b.

H_b(f_a + f_b) = H_b(f_a) Σ f_a / (Σ f_a + Σ f_b) + H_b(f_b) Σ f_b / (Σ f_a + Σ f_b) + H_b({Σ f_a, Σ f_b})

One case of the above definition is when f_b contains a single element, i. (We use t = Σ f_a hereafter.)

H_b(f_a + i) = H_b(f_a) t/(t+i) + t/(t+i) log_b[(t+i)/t] + i/(t+i) log_b[(t+i)/i]

And we can use this without bits as well

H(f_a + i) = H(f_a)^t/(t+i) * (t+i)/i^i/(t+i) * (t+i)/t^t/(t+i)

An iterative definition of entropy:

Entropy can be defined directly from the symbol frequencies f_i, and not the probabilities p_i. This is useful in computations where the entire symbol set is not know in advance and you want to avoid two passes (one to find the total, one to calculate), especially in parallel processing; or where arithmetic is expensive and precalculation will be used.

H_b(f₁, f₂, ..., f_n) = log_b(t) - 1/t Σ(i..n) f_i log_b(f_i).

And, for completeness, the iterative definition of entropy without bits:

H(f₁, f₂, ..., f_n) = t (Π(i..n) f_i^f_i)^-1/t