Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I calculated the entropy for "variable", "property" and their concatenation "variableproperty" (with e.g. the Shannon Entropy) and got $2.75, 2.5$ and $3.33$ respectively. These are all entropy per byte, if I don't err. But why is the last value greater than the other two and not lying between them?

share|improve this question
1  
I don't think it is doing entropy per byte. Look at the string "ab" vs "ababababababab" using that calculator. – mikeazo Feb 29 at 17:59
    
Entropy is a measure of impurity. If you got a bowl of food, with only rice in it, you would say that it's generally pure (thus low entropy). But if you get a bowl of food with rice, chicken, fish, and curries, then it is not pure cause it has all sorts of parties going on (thus high entropy). So the reason "variableproperty" has higher entropy is because it has more scrambled things in it (like rice + chicken + fish). Turns out that we can use entropy to generally describe information. It's a hot concept. I suggest you read about it. – caveman Feb 29 at 23:47

The calculator you've linked to is calculating the Shannon entropy of the character frequency distribution of your text. That is, if you type in e.g. variable, what it will calculate is the entropy of the following probability distribution:

p("a") = 2/8 = 0.25
p("b") = p("e") = p("i") = p("l") = p("r") = p("v") = 1/8 = 0.125

In particular, you would get the exact same result if you typed in aabeilrv or any other permutation of the letters in the word variable. Repeating the input several times won't change the letter frequencies, and thus their entropy, either.

Essentially, the entropy value returned by that calculator may be considered a measure of how many questions it would take, on average, to correctly guess a letter picked at random from the input text, using yes/no questions like "is the letter a vowel?" or "is it before N in the alphabet?", assuming that we know the text it has been picked from.

Based on this, it should be obvious why the input variableproperty gives a higher entropy value than just variable or property alone: the combined input string has more distinct letters, and thus it's harder to guess which letter a randomly chosen one of them might be.

share|improve this answer
    
You have pointed to the fact that the entropy value computed is the same for all permutations of a sequence. But therein is IMHO a basic problem with Shannon's formula. Suppose a fairly random looking alphabetical sequence A gets a correspondingly good entropy value u. Sort it to B such that all a's are at the front, followed by b's etc. Then B is evidently less random than A but has the same entropy value u as A. – Mok-Kong Shen Mar 3 at 9:33
    
@Mok-KongShen: If you only measure the entropy of the single-character frequencies, yes (because, by definition, that distribution ignores the order of the characters). If you instead measured, say, the distribution of consecutive groups of $n$ characters (where $n > 1$), the randomly shuffled sequence would have a much higher entropy than the sorted one. – Ilmari Karonen Mar 3 at 9:51
    
Certainly, but that only weakens the problem and doesn't basically eliminate the problem in my view. Another issue is how to judge whether an entropy value computed is sufficiently good. I mean for statistical tests one has confidence intervals so that one knows what the values obtained signify. Entropy values seem to be fuzzy in comparison. – Mok-Kong Shen Mar 3 at 9:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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