随机性测试 - randtests - 失败

机器算法验证 r 随机性 肯德尔陶
2022-03-23 08:07:10

假设我有一个由 PRNG 提供的具有 400,000 行和 20 列的矩阵形式的数据集。每行包含 20 个从 1 到 80 的唯一整数值​​。我需要检查 PRNG 的正确性。

为此,我将 R 与randtests包一起使用。首先,我将所有数据合并到一个向量中并在其上运行所有测试。然后我分别在每一列上运行每个测试。但是,我得到了类似的结果:第一个值是第一个实验中的 p 值,以下值是第二个实验中的 5 个最小 p 值:

  • 巴特尔斯等级检验0.90910.064、0.2218、0.2297、0.2573、0.3964
  • Cox Stuart 趋势测试0.88220.0701 0.0905 0.199 0.2407 0.2783
  • 差分符号检验0.79990.0153 0.01867 0.0226 0.0283 0.1538
  • Wald-Wolfowitz 运行测试0.97660.126 0.1279 0.232 0.2546 0.2705
  • 转折点测试6e-090.0037 0.0127 0.0175 0.0322 0.0672
  • Mann-Kendall 秩检验2e-161e-06 4e-05 2e-04 3e-04 5e-04

由于 2 次测试失败,我可以得出结论,这些数字不是真正随机的吗?除了运行这个测试,我还能做什么?

这是 .csv 格式数据的链接:第一列表示实验 ID,其他列是结果值。

2个回答

至少对于“Mann-Kendall Rank Test”,问题似乎出在您正在使用的测试包中,而不是数据中。

具体来说,Mann-Kendall 检验应该通过计算数据点与其在输入序列中的位置之间的Kendall 秩相关系数来检测数据中的单调趋势。但是,查看您正在使用randtests R 包的源代码,我发现它存在两个问题:

  • 它使用的是天真O(n2)算法来计算 Kendall 相关系数,这意味着它对于大型数据集变得非常慢。您的数据集包含 20 乘以 400,000 个点,几乎达到了它可以处理的极限。

  • 此外,似乎假设没有两个数据点具有相同的值。对于您的数据,这显然是错误的,从而导致虚假结果。

我使用更好的 Kendall 测试实现重新测试了您的数据,并得到了τB=0.0012,p=0.25对于整个数据,以及τB=0.010,p=0.03对于最强烈的趋势(即最低p值)列(最后一个,碰巧)。对于最低p值超出 20,这完全在合理的随机变化范围内。我也只花了几分钟就在我的笔记本电脑上运行了这个测试。

FWIW,这是我用来运行此测试的 Python 代码:

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)

(对于完整的数据测试,C表示行优先顺序和F列优先顺序;为了完整起见,我对它们都进行了测试。)

无法使用其输出测试来证实(更不用说断言)密码安全伪随机数生成器的正确性(因为任何有用的测试都符合 CSPRNG 中断的定义);这似乎是问题中尝试的内容(因为它是关于“检查 PRNG 的正确性”并且最初是在加密组中询问的)。这样的测试只能给出不正确的证明/论据。

只有通过检查该设计,才能证实 CSPRNG 设计的正确性。CSPRNG 实施的正确性可以通过将已知种子的输出与已知良好输出进行比较来证实。

如果TRNG 简单和/或足够了解,则可以通过类似于问题中的统计测试来证实真随机数生成器的正确性(作为播种 CSPRNG 所必需的) 。特别是,这样的标准统计测试

  • 无法有意义地检查在输出中包含 CSPRNG 的 TRNG(同样,对 TRNG 的有效测试将是对 CSPRNG 的中断)
  • 可以有意义地检查输出是噪声源的周期性采样的 TRNG,包括该 TRNG 是否在其输出上具有冯诺依曼去偏器(或其他具有极小状态的去偏器)。

[我不再解释 p 值;不过,请注意“将所有数据组合在一个向量中”,您获得的数据集(最多为 80 个正整数)不是均匀随机的,因为在原始数据集的每一行上,整数都是唯一的]。