First: Entropy is a property of a random variable in a physical process or a state of knowledge with more than one possible outcome, not a property of a deterministic function or a fixed known value. If you treat a fixed known value as a random variable with a trivial probability distribution with only one possible outcome, then its entropy is precisely zero. In this sense, the entropy of the binary expansion of $\pi$ is zero: from that description anyone can guess them with 100% probability of success.
Similarly, IID, or independent and identically distributed, is a property of several random variables in a physical process or state of knowledge.
- If you imagine fairly flipping a pair of coins yourself, the possible outcomes of that physical process are IID. Once you perform the experiment yourself, the actual outcomes you record are no longer IID—they are just fixed known values.
- If I tell you I fairly flipped a pair of coins, but not what the outcomes were, they are IID in your state of knowledge, provided you believe I'm not lying to you. Once I tell you what the first of my outcomes was, the first and second outcomes are no longer IID in your state of knowledge—the first one is a fixed known value, and the second one is a fair Bernoulli trial in your state of knowledge.
Now suppose you are presented with a black box that spits bits at you when you turn a crank on it. Here are two scenarios involving the black box:
You have a colleague on the other side of the Pacific ocean to whom you want to send the bits by telegram over the course of a several-year collaboration on a sociological study of black boxes handed out by strange birds. Telegrams cost money, so you would like to minimize costs by feeding them through a compression algorithm that on average reduces the number of bits you have to transmit.
If you have a model of how the black box operates, the (Shannon) entropy in that model is the average minimum number of bits you must send in telegrams per bit spat out by the black box. If your model is not the same as how the black box operates, your actual average costs will be multiplied by the KL divergence from your model to how the black box actually operates.
There is a million-euro prize for correctly guessing the one millionth 87-bit sequence. You can buy a lot of telegrams with a million euros, so it would be very convenient for your sociology study to win this prize, and you would therefore like to maximize the probability of correctly guessing that bit.
If you have a model for how the black box will operate on the millionth 87-bit sequence, the min-entropy in that model is minus the log of the probability of the most probable outcome.
Most of information theory and coding theory is dedicated to the study of Shannon entropy in scenario (1), because there's big money in compressing as many pixels onto discs and fiber optic links as possible to have big swooping action scenes in blockbuster movies, and because the physical world is full of black boxes like the electron orbits of hydrogen atoms that fat-fingered apes in Switzerland are only barely figuring out.
Most of cryptography is concerned with maximizing the min-entropy in scenario (2), and not with black boxes but with specific algorithms for mixing bits together. But there are centuries of mathematical tools built for scenario (1) which serve as a proxy for (2) because the Shannon entropy is an upper bound on the min-entropy.
Any putative ‘entropy testing’ tool really works like the following:*
- Start with a set of families of distributions for the output of the black box. This is the hypothesis space of the tool, its modeling assumptions.
- Given a sample of data from the black box, fit parameters for each of the hypothesis families.
- Analytically compute or numerically estimate the entropy of each particular hypothesis's distribution.
Here are a few stochastic processes that the tools might be programmed to assume as models for how the black box works:
- A gremlin inside generates each bit independently with identical distribution by flipping a coin with unknown probability $p$.
- A gremlin inside generates each pair of bits independently with identical distribution by flipping a coin with unknown probability $p$, and repeating it: if heads, 00; if tails, 11.
- A gremlin inside generates each octet independently with identical distribution by rolling a 256-sided die with unknown face probabilities $p_i$.
- A gremlin inside generates each octet consecutively using a hidden Markov model with unknown transition probabilities $p_{ij}$.
- A gremlin inside has a hat full of octets. It dumps them out on the floor of the box, and picks them up randomly, reporting each one, until they're back in the hat. Then it repeats the ordeal.
For each of these processes, there are various standard techniques for estimating parameters or posteriors, computing the entropy of the output, computing the conditional entropy of one output given another, etc.
Suppose you have an entropy estimation tool with the following single hypothesis family in its modeling assumptions:
- A gremlin inside generates each bit independently with identical distribution by flipping a coin with unknown probability $p$.
If a frequentist wrote the tool, they would probably program it to make the point estimate $p = \#\text{heads}/(\#\text{heads} + \#\text{tails})$ with maximum likelihood estimation and then print out the entropy $H = -p\log p - (1 - p)\log (1 - p)$. If a Bayesian† wrote the tool, they would probably program it with a $B(1,1)$ conjugate prior for this Bernoulli model and make it print the entropy of the posterior predictive distribution, which turns out to be exactly the same $H = -p\log p - (1 - p)\log (1 - p)$ with $p = \#\text{heads}/(\#\text{heads} + \#\text{tails})$.
The coin-flipping gremlin could generate the binary expansion of $\pi$, with probability decreasing exponentially in the number of coin tosses. When the coin-flipping gremlin makes fair coin flips with $p = 1/2$, its output has 1 bit of entropy per bit of output. One possible outcome of this gremlin is the binary expansion of $\pi$—but the ‘entropy of a fixed outcome’ (always exactly zero) is not the entropy of the process.
If you fed this tool a black box with a gremlin that always spits out the deterministic alternating sequence 0, 1, 0, 1, 0, 1, etc., it would always report exactly 1 bit of entropy per bit of output, even though this model of black box with a deterministic alternating gremlin inside—which is not in the hypothesis space of the tool—has zero entropy.
On the other hand, if the tool also considered the hidden Markov hypothesis
- A gremlin inside generates each octet consecutively using a hidden Markov model with unknown transition probabilities $p_{ij}$.
then for a box with the alternating gremlin, it would probably report an entropy near zero based on an empirical estimate of the transition probabilities.
If you fed this tool a black box with a gremlin that always spits out the binary expansion of $\pi$—also outside its modeling assumptions, and also zero entropy—it would report near 1 bit of entropy per bit of output because the ratio of one bits to zero bits in any finite truncation of the binary expansion of $\pi$ that anyone has examined is pretty close to 1:1, and the Markov model is not likely to help much either.
Most of these tools do not contain in their hypothesis spaces the zero-entropy deterministic process that is a gremlin dutifully computing the binary expansion of $\pi$. Physicists tend not to find gremlins like that when they peer at hydrogen atoms under magnifying glasses, so it's not really useful to include them in general-purpose tools. If you did include that modeling assumption, the tool could tell you that your sample matches the $\pi$-gremlin model exactly, $\Pr[X = \operatorname{trunc}_{1000}(\pi) \mathrel| \text{box yields binary expansion of $\pi$}] = 1$ where $X$ is the first 1000 bits of the black box.‡
Similarly, when applied to a sample that you know was produced by cryptography, such as $\operatorname{MD5}(0) \mathbin\Vert \operatorname{MD5}(1) \mathbin\Vert \cdots$, these tools are stupid in the precise sense that they don't know you used cryptography, so they exclude calculations involving MD5 from their possible hypothesis space, and if they had a next-bit guesser, it is unlikely to function like MD5 without being programmed explicitly to be so.
So what's the entropy of a black box containing a gremlin dutifully computing the binary expansion of $\pi$? Zero! Want to save costs on telegrams? Send your colleague a single telegram telling them this, and you don't have to send them a single extra bit; they can guess it for themselves.
Why do different tools print different entropy estimates? Because they all have different modeling assumptions, and each estimate is relative to the tool's modeling assumptions.
* Advanced ones may even do Bayesian model selection to combine all the distribution families, but traditional statistidigitators of yestercentury tend to abhor a cohesive Bayesian view of the world and prefer littering your terminal with incomprehensible jargon and numbers for you to interpret yourself. In fact, many statistics tools don't even articulate their modeling assumptions but rather blindly use standardized tests developed by respectable statistidigitators, which nobody ever got fired for buying. In contrast, the Bayesian rebels of yestercentury persistently asked annoying questions about priors that you never know how to answer so they stopped getting invited back to dinner parties.
† Certain advanced Bayesians might choose $B(1/2,1/2)$, or live on the unsampleable edge of the improper $B(0,0)$. Even more advanced ones might choose $B(\alpha, \beta)$ with a hyperprior on $\alpha$ and $\beta$, and if taken to extremes, stand on the backs of hyperturtles all the way down, which they dryly call ‘hierarchical modeling’ instead of listening to my suggestion because they started avoiding me after I dropped too many turtles on their heads.
‡ In a tool that did Bayesian model selection, this likelihood is so high that the hypothesis that the box generates the binary expansion of $\pi$ would probably outweigh all other hypothesis families in the posterior even if the hypothesis had a tiny prior probability, and a unified tool to guess the next bit with Bayesian model selection would probably do a good job for a $\pi$-generating black box.
