4
$\begingroup$

Whilst studying Shannon entropy, I came up with a singular idea, which surely someone already analysed, about which I cannot find anything though. I'm going to explain myself better.

Let's suppose we deal with a string of $N$ characters, written with an alphabet of $k$ letters $\{a_1, a_2, \ldots, a_k\}$, each one with a probability $p(a_i)$ to appear. Of course we need

$$\sum_{k = 1}^{k}\ p(a_i) = 1$$

Then here is a simple application: suppose we have a binary alphabet in which "$1$" has a probability of $p$ to appear, and "$0$" has a probability $1-p$ to appear. Given a message of $N$ characters, for large $N$,it'll have $N(1-p)$ characters "$0$" and $Np$ characters "$1$".

Now, the number of the total possible messages is given by

$$\binom{N}{Np}$$

And taking the $\log$ (in base two in this case)m using Stirling we get

$$\log\binom{N}{Np} \approx n\ H(p)$$

Where

$$H(p) = -(p\log_2 p + (1-p)\log_2 p)$$

Now it says: if we deal with $k$ letters, then what we get is the well known Shannon Entropy

$$H(X) = -\sum_{x = 1}^{k}\ p(x)\log p(x)$$

associated to the distribution $X = \{x, p(x)\}$.

Question

Is it possible to apply this, somehow, in order to find the entropy of a conversation? Or the entropy of a single phrase like ?

$$\text{THE PEN IS ON THE TABLE}$$

In this case we would deal with an alphabet of $26$ letters, but how to deal with more than one word? (Namely more than one string, if I understood well. Unless it use string for a complete phrase...)

$\endgroup$
  • 2
    $\begingroup$ This is covered in Shannon's original paper. I think he explains it better than I could. Just make a Markovian model of your language, and calculate the entropy in the usual way. If you want I can give a more verbose explanation. $\endgroup$ – Real Aug 27 '16 at 13:55
  • $\begingroup$ @Real That is cool!! Thank you so much for the paper! $\endgroup$ – Les Adieux Aug 27 '16 at 13:57
  • 1
    $\begingroup$ No problem, I forgot another important observation: the entropy of a string (symbol sequence in communication theory language) is not defined. Entropy is only defined for a source. What's defined for a symbol sequence (produced by a source, or equivalently a state from a statistical ensamble in physics) is surprise. Surprise is simply $- \log p(x)$, while entropy is the average surprise from symbols generated by the source $-\sum_{x = 1}^{k}\ p(x)\log p(x)$. Symbols optimally encoded will, on average, require at least as many bits as their surprise. $\endgroup$ – Real Aug 27 '16 at 14:09
  • $\begingroup$ @Real Is there really something called "Surprise"? Woah, that made my day :D $\endgroup$ – Les Adieux Aug 27 '16 at 14:33
  • $\begingroup$ I really love the concept of surprise, it's given nowhere near the attention of it's elder sibling, entropy. $\endgroup$ – Real Aug 27 '16 at 15:16
4
$\begingroup$

Entropy is only defined for a source. What's defined for a symbol sequence (produced by a source, or equivalently a state from a statistical ensamble in physics) is surprise.

Surprise (which we can call $S(x)$) is simply

$$S(x) = −\log p(x)$$

while entropy is the expected (or average) surprise from symbols generated by the source

$$H(X) = E[S] =\sum_{x = 1}^{k}\ p(x) S(x)$$

Symbols optimally encoded will, on average, require at least as many bits as their surprise.

Equivalently in physics, one cannot ask "What is the entropy of this classical discrete configuration?". Instead, one must assume this configuration is a sample from a statistical ensemble, and the ensemble actually possesses a characteristic entropy.

However, one may ask "What is the surprise of this classical discrete configuration?"; which represents how likely we are to observe that configuration given the statistical ensemble. For a discrete model of a gas, for example, the event of finding all particles confined within a small region of a box is highly surprising.

So your question admits two answers, assuming (for simplicity) a 1-gram Markov model of your sentence:

1) The entropy of a 24-letter sample from English text is approximately

$$H_{24} = \sum_{k = 1}^{24}{(-\sum_{x = 1}^{26}\ p(x) \log p(x))} = 24 \times 4.07 = 97.73 \: bits$$

2) The surprise of

$$f = THE \: PEN \: IS \: ON \: THE \: TABLE$$

is given by

$$S(f) = \sum_{k = 1}^{24}{S(k)} = -\log p(T) -\log p(H) -\log p(E) - ... = 75.24 \: bits$$

Your phrase in unsurprising! (less surprising than average, $S(f) \le E[S]$)

You can find this probabilities on the Google n-gram dataset.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.