Bonus question, what is the formula to calculate this?


closed as off-topic by e-sushi, Henrick Hellström, cygnusv, cpast, ddddavidee Jan 19 '15 at 15:50


  • "Questions on mathematics are off-topic unless they relate directly to cryptography. These questions can usually be asked on Mathematics Stack Exchange." – e-sushi, Henrick Hellström, cygnusv, cpast, ddddavidee

  • 2
    $\begingroup$ If it's an unbiased coin, you get one bit per toss. Since Shannon entropy is additive for independent events, you get 300 bits total. (This assumes that you toss 300 times, not that you toss 300 indistinguishable coins together) $\endgroup$ – CodesInChaos Jan 5 '15 at 15:09
  • $\begingroup$ The formula is $n$ bits of entropy for $n$ coin tosses with a fair coin. $\endgroup$ – Guut Boy Jan 5 '15 at 15:23
  • $\begingroup$ @CodesInChaos Re: fair coin, does is really matter when each toss varies in rotational speed and length of time it rotates? $\endgroup$ – user21767 Jan 5 '15 at 15:33
  • $\begingroup$ @user21767, "fair coin" refers to a coin that has an even chance of turning up heads or tails, one that shows no bias over multiple flips. It encompasses the entire process of flipping a coin, including rotations, speed, wind, gravity, whatever; and it is considered fair only if the outcome is statistically unpredictable. $\endgroup$ – John Deters Jan 11 '15 at 4:29

Let $X\colon\;\Omega\to\Sigma$ be a random source that emits symbols from a finite alphabet $\Sigma$. Write $p_\sigma:=\Pr[X=\sigma]$ for the probability that $\sigma$ is emitted. Then, the entropy $H(X)$ of $X$ is defined as $$H(X) = -\sum_{\sigma\in\Sigma}p_\sigma\log_2p_\sigma\text.$$ (If $p_\sigma$ is $0$, one uses the convention $p_\sigma\log_2p_\sigma=0$.)

In this case, $\Sigma=\{0,1\}^{300}$, hence $\lvert\Sigma\rvert=2^{300}$, and, assuming the coin is fair, all $p_\sigma$ are equal to $1/\lvert\Sigma\rvert=2^{-300}$. Therefore: $$H(X)=-\sum_{\sigma\in\Sigma}p_\sigma\log_2p_\sigma=-\lvert\Sigma\rvert\cdot2^{-300}(-300)=300\text,$$ which is just what one would intuitively expect from 300 random bits.

Note: One could also repeatedly apply the fact that, for independent random variables $X\colon\;\Omega\to\Sigma_1$ and $Y\colon\;\Omega\to\Sigma_2$, their combined entropy — that is, the entropy of $$X\times Y\colon\;\Omega^2\to\Sigma_1\times\Sigma_2,\;(\omega_1,\omega_2)\mapsto(X(\omega_1),Y(\omega_2))$$ in the product space — is $$H(X\times Y)=H(X)+H(Y)\text,$$ to $X\colon\;\Omega\to\{0,1\}$ uniformly distributed.

  • 4
    $\begingroup$ This seems like an overly complicated / formalised answer to a very simple problem. Sure, it's correct, but I find it questionable if it helps the understanding of the matter. $\endgroup$ – QuadrExAtt Jan 5 '15 at 15:31
  • $\begingroup$ Is that Klingon? +1 for trying. Edit: I can't +1, not enough rep, sorry. $\endgroup$ – user21767 Jan 5 '15 at 15:34
  • $\begingroup$ It is overly complicated when trying to understand entropy, no doubt, but formally proving something about entropy requires the definition of entropy. Besides that, @user21767 specifically asked for the formula. $\endgroup$ – yyyyyyy Jan 5 '15 at 15:36
  • $\begingroup$ Yeah, I'm the OP, if you look at the question it's a given that I won't be able to understand this answer. Thanks anyway, hopefully other users will upvote you. $\endgroup$ – user21767 Jan 5 '15 at 15:42
  • 1
    $\begingroup$ @SteveSether As I wrote above, this is the formal answer to the question. If you deem it unhelpful, feel free to create a better one! $\endgroup$ – yyyyyyy Jan 6 '15 at 17:44
