10
$\begingroup$

I'm confused.

I thought that tossing a 6-sided die 100 times had a greater than 256-bit entropy because $6^{99} < 2^{256} < 6^{100}$. (A similar concept appeared in this XKCD comic, where choosing four random words from a dictionary of presumably 2048 words has a 44-bit entropy, presumably because $2048^4 = 2^{44}$.)

On the other hand, the Shannon entropy of a 6-sided die tossed 100 times is $-6 × 1/6 × \log_2(1/6) = 2.5849625007$ bits. (According to the comments by Sakamaki Izayoi to my other question.)

Are these two different concepts of "entropy" entirely? If so, what's the difference and if not, what am I missing?

I read this thread but I'm still confused.

$\endgroup$

migrated from security.stackexchange.com Aug 19 '15 at 15:13

This question came from our site for information security professionals.

  • 2
    $\begingroup$ log2(6^100) = log2(6)*100 $\endgroup$ – Anonymous Coward Aug 19 '15 at 11:30
  • $\begingroup$ Can someone explain what the point of this formula is? -6*1/6 == -1. -1*log(1/6) = log(6). Under what circumstances are the terms different? $\endgroup$ – Random832 Aug 20 '15 at 2:54
  • $\begingroup$ @Random832 $H(X)=\log_2n$ is a simplified formula for the entropy of a random variable $X$ which is uniformly distributed over $n$ possible values. In the general case (i.e. for non-uniform distributions), the formula is $H(X)=-\sum_{x\in A}(\log_2\Pr[X=x])\cdot\Pr[X=x]$, from which the complicated expression for $\log_26$ can be obtained. $\endgroup$ – yyyyyyy Aug 20 '15 at 12:19
20
$\begingroup$

On the other hand, the Shannon entropy of a 6-sided die tossed 100 times is $-6 × 1/6 × \log_2(1/6) = 2.5849625007$ bits.

That is wrong: $-6\cdot\frac16\cdot\log_2\frac16$ is the entropy of a single die roll. Assuming the $100$ die rolls are independent, you can simply sum the entropies of the individual rolls to obtain $$ 100 \cdot\left(-6 \cdot\frac16\cdot\log_2\frac16\right) \approx 258.49625 \text, $$ which is precisely $\log_2(6^{100})$ as expected.

$\endgroup$
12
$\begingroup$

It seems that with your shannon entropy, you are using 100 tosses to estimate the shannon entropy of a single die toss. If it is a fair die, that would be $\log_2{6}\approx 2.58$.

This is different from rolling a die 100 times to generate a cryptographic key, for example. Each roll of the fair die would contain $2.58$ bits of entropy, so in total you would have approximately $2.58\cdot 100=258$ bits of entropy, or $\log_2{6^{100}}=\log_2(6)\cdot 100$ as mentioned in the comment.

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