-3
$\begingroup$

There is test data derived from pi that is supplied by NIST for validating their entropy measurement formulae listed in NIST's Recommendation for the Entropy Sources Used for Random Bit Generation. The data is of the following hex format (one varying bit per byte):-

01 01 01 00 00 01 00 01 00 00 00 01 01 00 00 00 01 00 01 00 01 00 01 01 00 01 00 00 00 01 00 01 00 00 01 01 00 01 01 00 00 00 01 00 00 00 01 01 00 01 01 01 00 01 01 01 00 00 01 00 01 00 00 00 00 01 01 00 00 01 01 01 00 01 01 01 01 00 00 00 01 00 01 01 01 01 01 00 00 00 00 00 01 00 01 00 00 00 00 00 01 00 00 00 01 01 00 01 00 01 00 01 00 00 00 01 00 01 01 01 01 01 01 00 00 01 01 00 01 01 00 00 01 00 00 00 01 00 01 00 01 01 00 ...

  1. I checked to see if the data was considered independent and identically distributed (IID), and it fails the IID test.

  2. I then measured the entropy (treating the file as non-IID) getting two measures of 0.57 bits/byte and 0.083 bits /byte. There are two versions of their tool hence two numbers. They are the outputs from a collision test and compression test respectively.

  3. I also estimated the entropy using my own compression technique to get 0.98 bits/byte.

Simple deduction implies that the true entropy of such a pi file is ~1 bit/byte. Neither NIST measure was close. Why are these three measures wildly different?


Raw I/O on a 1165666 byte pi file with 1 bit per symbol:-

 ./non_iid_test  ~/nist_h_tests/bin/data.pi.bin 1 -v
Opening file: .../nist_h_tests/bin/pi_1bit.bin

Running non-IID tests...

Entropic statistic estimates:
Most Common Value Estimate = 0.810967
Collision Test Estimate = 0.287049
Markov Test Estimate = 0.723549
Compression Test Estimate = 0.0828647  ####
t-Tuple Test Estimate = 0.704954
Longest Reapeated Substring Test Estimate = 8.5665  ####

Predictor estimates:
Multi Most Common in Window (MultiMCW) Test: 100% complete
    Correct: 568135
    P_avg (global): 0.569447
    P_run (local): 0.461426
Multi Most Common in Window (Multi MCW) Test = 0.812367
Lag Test: 100% complete
    Correct: 500378
    P_avg (global): 0.501667
    P_run (local): 0.427246
Lag Prediction Test = 0.995199
MultiMMC Test: 100% complete
    Correct: 533117
    P_avg (global): 0.534403
    P_run (local): 0.461426
Multi Markov Model with Counting (MultiMMC) Prediction Test = .903999
LZ78Y Test: 99% complete
    Correct: 494588
    P_avg (global): 0.495884
    P_run (local): 0.427246
LZ78Y Prediction Test = 1.01192   ####
Min Entropy: 0.0828647

#### indicates peculiar result. (I added these flags)

and to determine whether this is actually an IID file instead:-

./non_iid_test  /tmp/mentropy/bin/data.pi.bin 1 -v
Calculating baseline statistics...
Beginning initial tests...
Threading is off
Beginning permutation tests... these may take some time
** Failed IID permutation tests

DIY compression tests with fp8.exe and paq8px_v112.exe create a ~143000 byte file (as expected from hypothesis that pi is random).

$\endgroup$
  • 1
    $\begingroup$ Also, how many bits_per_symbol are you telling the tool? If you're telling it 8 (and the files are obviously formatted for 1), that tool might not be set up to handle that well... $\endgroup$ – poncho Apr 1 '18 at 2:52
  • 3
    $\begingroup$ Compression is never an effective way to measure entropy. It can only show that data has a very, very limited type of redundancy. $\endgroup$ – forest Apr 7 '18 at 2:24
  • 3
    $\begingroup$ Compression with a specific compression algorithm is an effective way to measure entropy in the following sense: It tells you an estimate of the relative entropy from the modeling assumption of the compression algorithm to the actual distribution of whatever black box whose output you're compressing! Compression algorithms like gzip are optimized for (i.e., tacitly use as a modeling assumption) English text, machine instructions, etc., and are not optimized for the binary expansion of $\pi$. $\endgroup$ – Squeamish Ossifrage Apr 7 '18 at 16:39
  • 2
    $\begingroup$ Here's a compression algorithm: If the message is the binary expansion of $\pi$, output 0; otherwise output 1 followed by the message. For a black box that generates the binary expansion of $\pi$, this compression algorithm works amazingly well: it compresses your whole message of arbitrary length into a single bit! But it won't be competing with gzip (or xz or Brotli or zstd or whatever the cool kids are using these days) any time soon. $\endgroup$ – Squeamish Ossifrage Apr 7 '18 at 16:41
  • 1
    $\begingroup$ Entropy testing is implemented in the form of randomness testing, since there is no algorithmic way to test for entropy (e.g. to distinguish the output of a CSPRNG from random). $\endgroup$ – forest Apr 8 '18 at 2:34
8
+50
$\begingroup$

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:

  1. 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.

  2. 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:*

  1. 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.
  2. Given a sample of data from the black box, fit parameters for each of the hypothesis families.
  3. 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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Nov 7 '18 at 2:50
1
$\begingroup$

To put it simply, $\pi$ is not random, since it is a single object. Not only that, it is not even proved whether it is normal to even one base $b.$

Essentially a number is said to be simply normal to base $b$ if its base$-b$ expansion has each digit appearing with average frequency tending to $b^{-1}.$ Clearly no rational number can be normal.

A normal number is an irrational number for which any finite pattern of numbers occurs with the expected limiting frequency in the expansion in a given base. It is known that almost all real numbers are normal, but there are massive difficulties with exhibiting normal numbers, just like there were difficulties with designing codes achieving channel capacity though Shannon's proof of achievability dates back to 1949.

Going back to $\pi,$ experiments indicate that its digits are close to uniformly distibuted to all bases that have been checked, but this ignores second order dependence effects [which would have exponential complexity to check], and entropy of a random stream captures such properties, and presumably the tests have been designed to capture such effects, albeit with different assumptions for each test.

$\endgroup$
  • $\begingroup$ So what is NISTS' reasoning for including $ \pi $ in this and the NIST randomness test suite? PS. $ \pi $ 's irrational. $\endgroup$ – Paul Uszak Apr 9 '18 at 0:19
  • $\begingroup$ It is a little glib to say ‘almost all real numbers are normal’. While true in the technical sense that the set of non-normal real numbers has Lebesgue measure zero, what is also true in this technical sense is that for almost all real numbers, there is no algorithm to print out their digits—which is more commentary on the practical utility on esoteric characteristics of the bizarre space we call ‘real numbers’ than anything else. The first computable normal number was not demonstrated until 2002 by Becher and Figueira. $\endgroup$ – Squeamish Ossifrage Apr 9 '18 at 0:22
  • 1
    $\begingroup$ Yes I know $\pi$ is irrational :-). Who knows what their exact rationale may be $\endgroup$ – kodlu Apr 9 '18 at 0:22
  • $\begingroup$ @SqueamishOssifrage, fair enough, I didn't want to get too technical. There is nothing bizarre about real numbers, other than the fact that computer science deals with finite or countable subsets of them :-) $\endgroup$ – kodlu Apr 9 '18 at 0:23
  • $\begingroup$ What I'm getting at is that the term ‘almost all’ is deceptively glib in that it obscures a difficult technical concept which is very different from a lay interpretation of the phrase. ‘So is any rational normal? No? Is $\sqrt{2}$ normal? Is $\pi$ normal? Is $e$ normal? Is {list of a billion other real numbers} normal? Can you give me even two examples? Then whaddya mean “almost all real numbers are normal”!?’ $\endgroup$ – Squeamish Ossifrage Apr 9 '18 at 0:28
-4
$\begingroup$

We can interpret the 800-90B tests as rubbish.

The tests do not work effectively on any real world correlated or non uniform entropy data. These are the findings of John Kelsey, Kerry A. McKay and Meltem Sönmez Turan, Predictive Models for Min-Entropy Estimation, and Joseph D. Hart, Yuta Terashima, Atsushi Uchida, Gerald B. Baumgartner, Thomas E. Murphy and Rajarshi Roy, Recommendations and illustrations for the evaluation of photonic random number generators. They produce the following summaries, showing the massive under estimations the tests produce:-

1

2

and from my own testing, a chart confirming a similar magnitude of errors:-

3

In short, the more the raw entropy deviates from IID (as is common in the real word), the greater the errors 90B produce. This climaxes in a 215 fold error for the entropy measure of a JPEG file. It is not surprising then that no one can find any examples of 90B being applied in the wild, as demonstrated in Any concrete examples of the use of NIST Special Publication 800-90B?


I'm excluding the Shuangyi Zhu, Yuan Ma, Tianyu Chen, Jingqiang Lin and Jiwu Jing Analysis and Improvement of Entropy Estimators in NIST SP 800-90B for Non-IID Entropy Sources paper as they use a Markov model for simulation data which seems inappropriate to a critique of said model. However, they effectively reach the same conclusions (just less so).

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Nov 7 '18 at 2:45

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.