2
$\begingroup$

I am interested in tests and definitions of randomness of a sequence generated by a pseudo-random number generator. A similar question was asked a few years ago, and the response was to use a Kolmogorov-Smirnov test for membership in the distribution. However, it seems possible to construct non-random sequences that would give a false positive on that test. The most natural test seems to be compressibility.

I asked this question a while ago and I didn't get an answer which convincingly refuted the idea of using compressibility as a test. I am restating the question here and focussing just on compressibility.

I will mix Python code here with some definitions to try to be as concrete as possible. I am a naive programmer, so mathematicians, please accept the use of code here as just my way of trying to be clear.

Let $X=(X^{(1)},\ldots,X^{(m)})$ be a set of $m$ sequences of length $n$, so that $X^{(i)}=(X_1^{(i)},\ldots,X_n^{(i)})$, where each where each $X_j^{(i)} \in [0,1]$. Suppose that $X \in U[0,1]$ in the sense that each generated sequence $X^{(i)}$ passes a statistical test like K-S for membership in $U[0,1]$.

import scipy.stats as st
import numpy as np
D=st.uniform(0,1)
D.random_state = np.random.RandomState(seed=7)
(m,n)=(1000, 50)
X=D.rvs((m,n))

Let $\Omega=[0,1]$. Let invertible $C:\Omega^\ast\rightarrow \Omega^\star$ be a compression function. For purposes of discussion we will use the JSON string representation of $X$ as the uncompressed baseline. We will use the zlib compression algorithm to measure compressibility:

import zlib, json
def C(X):
    Xstar=bytes(json.dumps(X.tolist()), 'UTF-8')
    return (Xstar, zlib.compress(Xstar))

Let $R:\Omega^\star \to[0,1]$ be a compression ratio function which gives the ratio of the compressed size to the uncompressed size.

def R(CX):
    return len(CX[1])/len(CX[0]) 

RX=[R(C(x)) for x in X ]

Question: Is it reasonable say that we have evidence that $X$ is pseudorandom in $U[0,1]$ if the normalized histogram or empirical PDF of $\{R(x): x \in X\}$ clusters around a number close to $r=1$.

Goal: Find a rigorous, quantitative, computable metric to capture the visual intuition that a picture of the output of a linear congruential generator that is without shuffling is somehow "less random" than one with shuffling. For example, it is visually obvious that the output on the left is "less random" than the output on the right, but left and right might both fare as well on a K-S test:

Linear congruential PRNG with and without shuffling

This motivates the idea of quantifying the sense that one output is "more random" than another, while still knowing that both are obviously not random at all because they are both generated by a deterministic computer program. So what I'm looking for here is an intuitively satisfying quantification of relative randomness, while still being aware that neither output is, on it's own "truly random".

Note 1: The following code will produce a histogram with positive skew clustered around $r=0.485$:

%matplotlib inline
from matplotlib.pylab import *
hist(RX, normed=True,bins=50);

Per comment from @r.e.s. below, if the text to be compressed is "truly random", then this ratio just arises as the difference between encoding a number as a sequence of base-10 digits versus a more compact binary encoding, i.e. the constant deflation ratio for going from decimal ASCII character encoding to pure binary encoding, so $\alpha=\frac{\log_{10}{2}}{8}$. In this case, we can simply divide by $\alpha$ in

def R(CX):
    alpha=np.log10(2)/8
    return len(CX[1])/(alpha*len(CX[0]))

and we will get clustering closer to 1 which fits with our expectation that the output of the Python Uniform pseudo-random number generator will be "relatively more random" than say

np.linspace(0,1,1000)

repeated 50 times.

Note 2: Per answer of @mathreadler below, because this is the output of a deterministic program (note that I have set the seed above to emphasize this fact: the output is entirely reproducible), the optimal $C^*$ is really the optimal compression of the 6-line computer program above that generates the sequence. Which can be much shorter still than the optimal compression of the program's output.

This reframing observation misses the point. We know that the output of any pseudorandom number generator that we can program in Python on a conventional computer is deterministic. We still make random number generators, and we still have some more or less quantifiable sense of what makes one PRNG "more pseudo-random" than another. The test of distribution fit can be spoofed to produce the same results for outputs such as the shuffled and non-shuffled versions above, where one output is visually "more pseudo-random" than the other. That "visual obviousness" should be rigorously quantifiable. I think the compression test fits the bill, for comparing the outputs of two PRNGs, while still knowing that the PRNGs themselves can have their code compressed to a shorter sequence than the compression of the outputs.

Then to get back to my original question, I would compare the compressibility of the output a given PRNG against the compressibility using the same algorithm of a completely non-random sequence that covers the distribution, such as, for $U[0,1]$, np.linspace(0,1,1000).

Note 3: The idea of using compressibility to measure randomness was used in a Maple blog post in 2010 by John May. In the blog, Robert Israel commented that

There are many different flavours of entropy. What you are using is the 0'th order entropy, which is appropriate for the case where each bit is independent of the previous ones. For a process where the probabilities of the next bit depend on the $k$ previous ones, you might use $k$'th order entropy. Of course, for a PRNG, in principle if $k$ is large enough $k$ consecutive bits should be enough to determine the seed and therefore all future bits, and then the $k$'th order entropy is 0. A sufficiently clever compression scheme would be able to do this calculation and obtain a compression ratio approaching 0.

The last sentence of this comment echoes @mathreadler's answer below. Then Jacques Carette commented that

What John is computing is a very rough approximation to the Kolmogorov complexity of the sequence. And as Robert mentions, this is also related to information entropy.

John May replied

Robert Israel, I probably should have been more specific, and said "Shannon Entropy" measured just with character counting a la ?StringTools:-Entropy or ?ImageTools:-Entropy . Clearly that sort of measure can not really say anything about LZ compressibility, but so much of what I found written on the web conflated entropy (typically immediately defined to be Shannon Entropy) with compressibility when as per Jacques Carette it would be better to save comparisons to compressibility for information theoretical measures of complexity (or a more subtle discussion of entropy).

I'm quoting the Maple blog post just to say that using compressibility to quantify randomness is in some sense a fairly obvious idea which has already been considered by others, and to bring in, for purposes of discussion here, the terms of art which are relevant for this discussion, namely these three somewhat distinct topics:

  • Shannon entropy
  • Kolmogorov complexity
  • Compressibility

Compressibility is used as a benchmark by the Fermi Lab. Entropy is in fact the first measure that they list, prior to Chi-Square test. The other "deep" test they employ is Serial Correlation Coefficient:

Compressibility is also discussed as a benchmark by NIST:

There have been several prior Stack Exchange questions from others on the same topic:

Here are some other discussions of compressibility and randomness:

Note 4: A directly related topic in theoretical computer science is that of pseudorandom generator testing. Wikipedia notes that

NIST announced SP800-22 Randomness tests to test whether a pseudorandom generator produces high quality random bits. Yongge Wang showed that NIST testing is not enough to detect weak pseudorandom generators and developed statistical distance based testing technique LILtest.

Under the heading of specific tests for randomness, Wikipedia notes

Measures of randomness for a binary sequence include Hadamard transforms and complexity. The use of Hadamard transform to measure randomness was proposed by Subhash Kak and developed further by Phillips, Yuen, Hopkins, Beth and Dai, Mund, and George Marsaglia and Zaman. These tests provide spectral measures of randomness. T. Beth and Z-D. Dai purported to show that Kolmogorov complexity and linear complexity are practically the same. Yongge Wang later showed their claims are incorrect. However Wang demonstrated that for Martin-Löf random sequences, the Kolmogorov complexity is the same as linear complexity. These practical tests make it possible to compare the randomness of strings. On probabilistic grounds, all strings of a given length have the same randomness. However different strings have a different Kolmogorov complexity. For example, consider the following two strings.

String 1: 0101010101010101010101010101010101010101010101010101010101010101
String 2: 1100100001100001110111101110110011111010010000100101011110010110

String 1 admits a short linguistic description: "32 repetitions of '01'". This description has 22 characters, and it can be efficiently constructed out of some basis sequences. String 2 has no obvious simple description other than writing down the string itself, which has 64 characters, and it has no comparably efficient basis function representation. Using linear Hadamard spectral tests, the first of these sequences will be found to be of much less randomness than the second one, which agrees with intuition.

The spectral test goes directly at the exact same problem this question is framed around: We can construct two sequences, one of which is visually less "random" than the other, and yet both will give back the exact same Chi-squared test results. So the question is how to measure the "randomness distance" between the two pictures, i.e. how to quantify the increase in randomness of one picture over the other.

$\endgroup$
2
  • $\begingroup$ To answer the question in your note ... Most of the bytes in your byte-string Xstar represent the decimal digits of the random sample, using a whole 8 bits to store each digit, which can, on average, be done with only $\log_2(10)$ bits per digit. For those parts of the byte-string, that's an immediate (theoretical) compression ratio of $\log_2(10)/8=0.415...$ $\endgroup$ – r.e.s. Jul 28 '20 at 20:51
  • $\begingroup$ Nice, I will redo and try to incorporate that lower bound observation or redo with a more efficient encoding to just compress the underlying bytes of the matrix without the round trip into JSON. $\endgroup$ – Lars Ericson Jul 28 '20 at 21:16
1
$\begingroup$

In short, no.

Any pseudorandom algorithm takes a seed and follows some algorithm to give a sequence of data.

The theoretical information carried by any outputted sequence is bounded by how much information required to describe the algorithm together with this random seed.

The optimal compression algorithm would be one that identifies the pseudorandom process, identifies the seed used and hands you the binary length or source code length and the random seed.

This will always be very compressed no matter how well any statistically relevant test performs on the data.

It is more likely going to be a test of how well your compression algorithm performs under hard conditions. I suspect that it would be extraordinarily hard to write a compression algorithm that could backtrack the pseudorandom process, but it is clearly possible straight from definition of pseudorandomness.

$\endgroup$
1

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.