4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Guut Boy
    Sep 20, 2016 at 7:15

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Got it, thanks! Do you think this difference will be more or less apparent if we calculate the pseudo entropy of a short string (e.g. a hundered letters)? This was a huge subject of debate between me and a friend :) $\endgroup$
    – user39469
    Sep 20, 2016 at 12:41
  • $\begingroup$ Can you define what you mean by pseudo entropy? I've found a range of definitions in theoretical crypto literature. If ou mean it is the entropy of the distribution of consecutive character 2-grams, 3-grams, etc., the answer is yes it should. $\endgroup$
    – kodlu
    Sep 20, 2016 at 13:57
  • $\begingroup$ 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. $\endgroup$
    – user39469
    Sep 20, 2016 at 14:02
  • $\begingroup$ oh, I see. that's usually called "empirical" entropy in traditional information theory. I will modify my answer to clarify what I meant in my comment above. $\endgroup$
    – kodlu
    Sep 20, 2016 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.