6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If randomness tests fail, this usually imples the RNG is really bad. But there's usually also a small chance that you just got unlucky with this execution even if is a good one. $\endgroup$ – SEJPM Sep 1 '15 at 16:53
  • 1
    $\begingroup$ 8 million values is probably not enough to run full dieharder suite, when run manually from the command line. Usually you wire it up to the generator e.g. prng_bytes_source | dieharder -g 200 -a, and also usually it expects a random byte stream, each byte should be between 0 and 255. You could construct that from your spreadsheet, but the transformation would leave you with even less data. $\endgroup$ – Neil Slater Sep 2 '15 at 11:34
  • $\begingroup$ I wish to thank everyone for useful comments. I have added a link for the data set in the starting post. I will be very grateful if someone could tell anything helpful about the data. $\endgroup$ – nmerci Sep 3 '15 at 10:41
  • 1
    $\begingroup$ I missed the correlation due to draw without relacement effect. Some randomness tests could fail due to that, unfairly to your source if it is intended. E.g. a test for repeated runs would never see 3 identical values in a row (which should occur with $p = \frac{1}{80^2}$ at any point within a fully random sequence). It is likely your failing tests are just picking up on this property of the data, which breaks the most common assumption of fully independent values that the tests need in order to do their job. $\endgroup$ – Neil Slater Sep 3 '15 at 15:07
  • $\begingroup$ @Neil Slater Wherein, combined data pass Runs Test , unlike the last two. However, data in each column should be independent, but p-values in both cases are comparable. $\endgroup$ – nmerci Sep 3 '15 at 15:21
7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Sorry, but the small p-values indicate that I should take an alternative hypothesis (which corresponds to trend or something in the sequence). Also I have mentioned that the values in each row correlate, since each value must be unique. I am not sure, however, it seems like data are drawn from a lottery machine with 80 balls. $\endgroup$ – nmerci Sep 3 '15 at 14:03
  • $\begingroup$ @nmerci: oups, thanks for noting - removed my nonsense. $\endgroup$ – fgrieu Sep 3 '15 at 14:24
  • $\begingroup$ I want to test hypothesis about "perfectness" of the lottery machine. I agree that I used tests like a monkey, however I am not a specialist in this field. Therefore, I come here for help. $\endgroup$ – nmerci Sep 3 '15 at 16:04

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.