LCG是否像我的代码所显示的那样无法通过Kolmogorov-Smirnov测试？

Question

我使用以下Python代码向学生演示随机变量的生成：

import numpy as np
import scipy.stats as stats

def lcg(n, x0, M=2**32, a=1103515245, c=12345):
    result = np.zeros(n)
    for i in range(n):
        result[i] = (a*x0 + c) % M
        x0 = result[i]

    return np.array([x/M for x in result])

x = lcg(10**6, 3)
print(stats.kstest(x, 'uniform'))

根据维基百科的说法，默认参数是glibc使用的参数。打印代码的最后一行

KstestResult(statistic=0.043427751892089805, pvalue=0.0)

P值为0.0表明，如果x的元素真正按照均匀分布分布，则观测基本上永远不会发生。我的问题是:我的代码中是否有bug，或者带有给定参数的LCG没有通过带有10**6副本的Kolmogorov-Smirnov测试？

Answer 1

你的代码有问题，它使得均匀分布像这样

​

​

我对你的LCG实现做了一些修改，现在一切都很好了(Python3.7，蟒蛇，Win10 x64)

import numpy as np
import scipy.stats as stats
import matplotlib.pyplot as plt

def lcg(n, x0, M=2**32, a=1103515245, c=12345):
    result = np.zeros(n)
    for i in range(n):
        x0 = (a*x0 + c) % M
        result[i] = x0

    return np.array([x/float(M) for x in result])

#x = np.random.uniform(0.0, 1.0, 1000000)
x = lcg(1000000, 3)
print(stats.kstest(x, 'uniform'))

count, bins, ignored = plt.hist(x, 15, density=True)
plt.plot(bins, np.ones_like(bins), linewidth=2, color='r')
plt.show()

哪种打印

KstestResult(statistic=0.0007238884545415214, pvalue=0.6711878724246786)

和情节

​

​

更新

正如@pjs指出的，你最好在循环中除以浮点数(M)，不需要对整个数组进行第二次传递

def lcg(n, x0, M=2**32, a=1103515245, c=12345):
    result = np.empty(n)
    for i in range(n):
        x0 = (a*x0 + c) % M
        result[i] = x0 / float(M)

    return result

Answer 2

为了补充谢韦林的回答，我的代码不能正常工作的原因是result是一个浮点数的数组。我们可以在第二次迭代中看到两个实现之间的差异。在第一次迭代之后，x0 = 3310558080。

In [9]: x0 = 3310558080

In [10]: float_x0 = float(x0)

In [11]: (a*x0 + c) % M
Out[11]: 465823161

In [12]: (a*float_x0 + c) % M
Out[12]: 465823232.0

In [13]: a*x0
Out[13]: 3653251310737929600

In [14]: a*float_x0
Out[14]: 3.6532513107379297e+18

所以这个问题与浮点数的使用有关。