0
$\begingroup$

Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} p_i\log_2(p_i)[bit]$$

So if I were to calculate the Entropy of a coin toss. it would be $$H(\frac{1}{2}, \frac{1}{2})=-(\log_2(\frac{1}{2})+\frac{1}{2}\log_2(\frac{1}{2}))=-(0-1)=1 Bit$$

But why is there a $\frac{1}{2}$ before the $\log$? Also if I were doing an experiment where the probability of an outcome is $\frac{1}{3}$ and there are $3$ outcomes, so would the entropy be

$$H(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})=(\log_2(\frac{1}{3})+\frac{1}{3}\log_2(\frac{1}{3})+\frac{1}{3}\log_2(\frac{1}{3}))$$

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ There should be a $1/2$ before each term. Your calculation is wrong. $\endgroup$
    – xskxzr
    Commented Mar 29, 2018 at 6:32
  • $\begingroup$ @xskxzr So if the probability was $\frac{1}{3}$, would there be $\frac{1}{3}$ before each term? $\endgroup$
    – Ski Mask
    Commented Mar 29, 2018 at 10:06
  • $\begingroup$ Yes, of course. $\endgroup$
    – xskxzr
    Commented Mar 29, 2018 at 14:22

1 Answer 1

Reset to default
1
$\begingroup$

Your formula is totally inapplicable in computer randomness harvesting. I think that people use it because it's easy to write down. Even then, it's not really usable - what's i exactly? For any non trivial application, there are correlations. Try using this formula for the English language. No you can't say there are just 26 letters as they are hugely correlated. There are two, three, four letter combinations, and then there are words and sentences that have lexological and grammatical structure. I don't know what you do with full stops. The entropy rate will very much depend on who wrote the words and about what. If you try the Shannon formula in it's most simplistic typical use case, "1111111111...0000000000..." has exactly 1 bit/bit of entropy. Clearly it doesn't.

Entropy harvesting by a computer kernel consists of sucking up hardware device interrupts including keyboard presses. Non of this is uncorrelated. The official cryptographic term is non IID (non independent and identically distributed). And for measurement of such non IID entropy, there is no set standard. The best we have currently is either direct compression, or the NIST SP800-90B_Entropy Assessment tools (which also include compression as one of the tests). They may have been written by a chap using up his spare time.

Is von Neumann's randomness in sin quote no longer applicable? is a currently open question featuring such entropy measurements. So essentially coin toss randomness is completely different to operating system randomness.

Improve this answer
$\endgroup$

Your Answer

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

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