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}))$$

$\endgroup$
  • 1
    $\begingroup$ There should be a $1/2$ before each term. Your calculation is wrong. $\endgroup$ – xskxzr Mar 29 '18 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 Mar 29 '18 at 10:06
  • $\begingroup$ Yes, of course. $\endgroup$ – xskxzr Mar 29 '18 at 14:22
2
$\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.

$\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.