Test for randomness - randtests - fails

Question

Suppose I have a data set provided by PRNG in a matrix form with 400,000 rows and 20 columns. Each row consists 20 unique integer values from 1 to 80. I need to check the correctness of the PRNG.

For this purpose I have used R with randtests package. First I combined all data in a single vector and run all tests on it. Then I run each test on each column separately. However, I obtained similar results: the first value is a p-value in first experiment and the following values are 5 smallest p-values from the second experiment:

• Bartels Rank Test: 0.9091; 0.064, 0.2218, 0.2297, 0.2573, 0.3964
• Cox Stuart Trend Test: 0.8822; 0.0701 0.0905 0.199 0.2407 0.2783
• Difference Sign Test: 0.7999; 0.0153 0.01867 0.0226 0.0283 0.1538
• Wald-Wolfowitz Runs Test: 0.9766; 0.126 0.1279 0.232 0.2546 0.2705
• Turning Point Test: 6e-09; 0.0037 0.0127 0.0175 0.0322 0.0672
• Mann-Kendall Rank Test: 2e-16; 1e-06 4e-05 2e-04 3e-04 5e-04

Since 2 tests are failed can I conclude that the numbers are not truly random? What can I do besides running this test?

Here is a link for the data in .csv format.: the first column indicates an ID of experiment and others are resulted values.

Answer 1

At least for the "Mann-Kendall Rank Test", the problem seems to be in the testing package you're using, and not in the data.

Specifically, the Mann-Kendall test is supposed to detect monotone trends in the data by calculating the Kendall rank correlation coefficient between the data points and their position in the input sequence. However, looking at the source code of the randtests R package you're using, I see two problems with it:

• It's using a naïve $\mathrm O(n^2)$ algorithm to calculate the Kendall correlation coefficient, which means that it gets very slow for large data sets. Your data set, with 20 times 400,000 points, is just about at the limit of what it can handle.

• Also, it seems to be assuming that no two data points have identical values. For your data, this is patently false, leading to bogus results.

I retested your data using a better implementation of the Kendall test, and got $\tau_B = -0.0012$, $p = 0.25$ for the whole data, and $\tau_B = -0.010$, $p = 0.03$ for the most strongly trended (i.e. lowest $p$ value) column (the last one, as it happens). For the lowest $p$ value out of 20, this is well within the bounds of reasonable random variation. It also took me only a few minutes to run this test on my laptop.

FWIW, here's the Python code I used to run this test:

import numpy as np
import scipy.stats as stats

data = np.loadtxt('data.csv', delimiter=',', dtype=int, skiprows=1)

for col in range(1, len(data[0])):
    tau, p = stats.kendalltau(data[:,0], data[:,col])
    print "column %2d: tau = %+g, p = %g" % (col, tau, p)

for order in ('C', 'F'):
    flat = data[:,1:].flatten(order)
    tau, p = stats.kendalltau(flat, np.arange(len(flat)))
    print "full data (%s): tau = %+g, p = %g" % (order, tau, p)

(For the full data tests, C means row-major order and F means column-major order; I tested them both for the sake of completeness.)

Answer 2

One can not substantiate (much less assert) the correctness of a Cryptographically Secure Pseudo Random Number Generator using tests of its output (because any useful test fits the definition of a break of the CSPRNG); that seems to be what's attempted in the question (since it is about "check the correctness of the PRNG" and was initialy asked in the crypto group). Such tests can only give a proof/argument of non-correctness.

Correctness of design of a CSPRNG can be substantiated only by examining that design. Correctness of implementation of a CSPRNG can be substantiated by comparing the output for known seed to known good output.

Correctness of a True Random Number Generator (as necessary for seeding a CSPRNG) can be substantiated by statistical tests similar to those in the question if the TRNG is simple and/or known enough. In particular, such standard statistical tests

• can not meaningfully check a TRNG which incorporates a CSPRNG at the output (again, a valid test of the TRNG would be a break of the CSPRNG)
• can meaningfully check a TRNG which output is periodical sampling of a noise source, including if such TRNG has on its output a Von Neumann de-biaser (or other de-biaser with extremely small state).

[I quit interpreting the p-values; still, be careful that having "combined all data in a single vector" you obtained a data set (of positive integers at most 80) that is not uniformly random, since on each row of the original data set, the integers are unique].