# Given enough length, which string of symbols will have the greatest entropy?

Which arbitrarily long string will have the greatest entropy?

1. A string constitued of random letters, with each letter having a probability of being picked equal to its frequency of apparition in the english language.
2. A text written in english.

Let's assume there's only 27 different symbols (letters+space), and each symbol is coded on 8 bits.

• My intuition says 1. will have highest entropy. While both strings have each individual character distributed equally, the string in 2. will also have dependencies between characters. For example, in 1. the string "eee" will have relatively high probability while it will have essentially 0 probability in 2. – Guut Boy Sep 20 '16 at 7:15

As examined by Shannon in his paper "Entropy of printed English", higher order models which allow for dependencies between nearby characters are more accurate models of English. And in general, dependencies reduce but never increase entropy, so @Guut Boy is correct, the first shall have higher entropy. In the extreme case there is essentially zero entropy about the $(n+1)$st character if the $n$th character is q, it is almost always followed by u ("coq au vin" is taken to be French).
Edit To verify this experimentally given the string $(x_1,\ldots,x_n)$ over the alphabet $A$ define the sequence $(y_1,\ldots,y_{n-k+1})$ by $$y_i=x_i,x_{i +1},\ldots,x_{i+k-1},\quad i =1,\ldots,n-k+1,$$ over $A^k.$
Compute the entropy corresponding to the frequencies of the $y_i$ sequence. Divide by $k$ to obtain entropy per symbol.
Put simply, $k=2$ would give the entropy of bigrams and divided by 2 it should be lower than that given by monogram frequencies.
• Entropy is calculated with sum(Ps * log2(1/Ps)), with Ps being the probability of the source generating the symbol s. Pseudo entropy of a string is calculated with the same formula but with Fs instead of Ps, with Fs being the frequency of apparition of the symbol s in the string. – user39469 Sep 20 '16 at 14:02