随机数检测规范里面提供了一份附录A，是测试的原理解释。然而里面的内容对于我这种菜鸡稍微有点简略，所以我稍微补充总结了一下。
理论基础
中心极限定理
设$X_{1}$, $X_{2}$, …, $X_{n}$, … 为独立同分布的随机变量, $E(X_{i})=a$, $Var(X_{i})=\sigma^{2}(0 < \sigma^{2} < \infty)$. 则对任何实数$x$, 有
$$ \lim\limits_{n \to \infty} P(\dfrac{1}{\sqrt{n} \sigma}(X_{1} + … + X_{n} - na) \leq x) = \phi(x) $$
这里$\phi(x)$是标准正态分布$N(0,1)$的分布函数, 即
$$ \phi(x) = \dfrac{1}{\sqrt{2\pi}}\int^{x}_{-\infty}e^{-t^{2}/2}dt $$
De Moivre–Laplace定理
设$X_{1}$, $X_{2}$, …, $X_{n}$, … 独立同分布, $X_{i}$的分布是
$$ P(X_{i} = 1) = p, P(X_{i} = 0) = 1 - p \quad (0 < p < 1) $$
则对任何实数$x$, 有
$$ \lim\limits_{n \to \infty} P(\dfrac{1}{\sqrt{np(1 - p)}}(X_{1} + … + X_{n} - np) \leq x) = \phi(x) $$
皮尔森卡方检验
P值
以下为我的理解：设定了置信系数$\alpha$以后，通过分布函数可以求出临界点 $ x_{\alpha} $，那么在临界点以内的观测值可以算作零假设成立，以外的观测值可以认为推翻零假设。$P$值即$1 - F(x_{i})$，其中$x_{i}$为随机变量观测值，$F(x_{i})$为随机变量在此观测值下的分布函数值。根据概率密度函数的图像可以看出(概率密度函数的积分为分布函数)，当$P$值大于等于置信系数，可知观测的随机变量值位于临界点内，从而可支持零假设成立，反之，$P$值小于置信系数，观测的随机变量值位于临界点外，可以认为推翻零假设。$P$值提供了一种假设检验的方式。
P值与erfc, igamc等函数之间的关系
$erfc$
$$ erfc(x) = \dfrac{2}{\sqrt{\pi}} \int^{\infty}_{x}e^{-u^{2}}du $$
$igamc$
$$ igamc(a, x) = \dfrac{\int^{\infty}_{x} e^{-t} t^{a-1}dt}{\Gamma(a)} $$
对于标准正态分布，考虑观测值大于0($x_{i} > 0$)的情况(正态分布对称，可只考虑半边)，有
$$ 1 - \phi(x) = \dfrac{1}{\sqrt{2\pi}}\int^{\infty}_{x}e^{-t^{2}/2}dt = \dfrac{1}{\sqrt{\pi}}\int^{\infty}_{x}e^{-t^{2}/2}d(\dfrac{t}{\sqrt{2}}) $$
使用$z$替换$\dfrac{t}{\sqrt{2}}$，可得
$$ 1 - \phi(x) = \dfrac{1}{\sqrt{\pi}}\int^{\infty}_{x/\sqrt{2}}e^{-z^{2}/2}dz $$
对比$erfc$函数可得
$$ 2(1 - \phi(x)) = erfc(\dfrac{x}{\sqrt{2}}) $$
又由于标准正态分布关于y轴对称，因此，只有观测值位于[$-x_{\alpha/2}$, $x_{\alpha/2}$]之间才可以支持零假设成立。因此需要满足
$$ 1 - \phi(x_{i}) \geq \dfrac{\alpha}{2} $$
即如果支持零假设，需满足下面条件
$$ erfc(\dfrac{x_{i}}{\sqrt{2}}) = 2(1 - \phi(x_{i})) \geq \alpha $$
即观测的随机变量为正态分布时，需要使用$erfc(\dfrac{x}{\sqrt{2}})$作为$P$值
对于自由度为$k$的卡方分布，假定其分布函数为$F_{k}(x)$，有
$$ 1 - F_{k}(x) = 1 - \dfrac{\gamma(k/2, x/2)}{\Gamma(k/2)} = 1 - \dfrac{\int_{0}^{x/2}t^{k/2-1}e^{-t}dt}{\int_{0}^{\infty}t^{k/2-1}e^{-t}dt} = \dfrac{\int_{x/2}^{\infty}t^{k/2-1}e^{-t}dt}{\Gamma(k/2)} = igamc(\dfrac{k}{2}, \dfrac{x}{2}) $$
如果支持零假设，需满足下面条件
$$ 1 - F_{k}(x) = igamc(\dfrac{k}{2}, \dfrac{x}{2}) \geq \alpha $$
即观察的随机变量为卡方分布时，需要使用$igamc(\dfrac{k}{2}, \dfrac{x}{2})$作为$P$值
卡方分布相加后的分布
设X和Y分别有密度函数$p_{X}(x)$和$p_{Y}(y)$，且$X$和$Y$相互独立，则$Z = X + Y$有分布函数
$$ p_{Z}(z) = \int_{-\infty}^{+\infty}p_{X}(x)p_{Y}(z-x)dx $$
对于自由度为k的卡方分布，有概率密度函数
$$ f_{k}(x) = \dfrac{x^{k/2-1}e^{-x/2}}{2^{k/2}\Gamma(\dfrac{k}{2})} $$
则对于自由度分别为$m$和$n$的卡方分布$X$和$Y$，有$Z=X+Y$的概率密度函数如下，其中由于卡方分布满足随机变量值非负，调整积分上下限($x \geq 0$且$z - x \geq 0$)，则
\begin{equation}
\begin{split}
p_{Z}(z) &= \int_{0}^{z} \dfrac{x^{m/2-1}e^{-x/2}}{2^{m/2}\Gamma(\dfrac{m}{2})} \dfrac{(z-x)^{n/2-1}e^{-(z-x)/2}}{2^{n/2}\Gamma(\dfrac{n}{2})}dx \\
&= \dfrac{e^{-z/2}z^{(m+n)/2-1}}{2^{(m+n)/2}\Gamma(\dfrac{m}{2})\Gamma(\dfrac{n}{2})} \int_{0}^{z}\dfrac{x}{z}^{m/2-1}(1-\dfrac{x}{z})^{n/2-1}d\dfrac{x}{z} \\
&= \dfrac{e^{-z/2}z^{(m+n)/2-1}}{2^{(m+n)/2}\Gamma(\dfrac{m}{2})\Gamma(\dfrac{n}{2})} \int_{0}^{1}t^{m/2-1}(1-t)^{n/2-1}dt \\
&= \dfrac{e^{-z/2}z^{(m+n)/2-1}}{2^{(m+n)/2}\Gamma(\dfrac{m}{2})\Gamma(\dfrac{n}{2})} B(\dfrac{m}{2},\dfrac{n}{2}) \\
&= \dfrac{e^{-z/2}z^{(m+n)/2-1}}{2^{(m+n)/2}\Gamma(\dfrac{m+n}{2})}\\
\end{split}
\end{equation}其中利用了B函数(贝塔函数)的性质
$$ B(x,y) = \int_{0}^{1} t^{x-1}(1-t)^{y-1} dt $$
$$ B(x,y) = \dfrac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)} $$
可见Z的概率密度函数满足自由度为$m+n$的卡方分布，因此对于相互独立的自由度分别为$m$和$n$的卡方分布，它们的和的分布为自由度为$m+n$的卡方分布
15项检测
单比特频数检测
可知比特序列被经过转换，0 -> -1, 1 -> 1，从而单比特代表的随机变量$X_{i}$满足以下分布
$$ \begin{array}{c|lcr}
X_{i} & 1 & -1 \\
\hline
p & \dfrac{1}{2} & \dfrac{1}{2} \\
\end{array} $$由于单比特代表的随机变量$X_{i}$为独立同分布，且可计算得到该分布满足$E(X_{i})= 0$, $Var(X_{i}) = 1$，由中心极限定理，有
$$ \lim\limits_{n \to \infty} P(\dfrac{S_{n}}{\sqrt{n}} \leq x) = \phi(x) $$
可知此时观测的随机变量为$\dfrac{S_{n}}{\sqrt{n}}$，满足正态分布，因此可利用上面$P$值与$erfc$的关系中的结论，得到
$$ p-value = erfc(\dfrac{|S_{n}|}{\sqrt{2n}}) $$
块内频数检测
单比特代表的随机变量$X_{i}$满足以下分布
$$ \begin{array}{c|lcr}
X_{i} & 1 & 0 \\
\hline
p & \dfrac{1}{2} & \dfrac{1}{2} \\
\end{array} $$由$\pi_{i}$的计算方式可知，$\pi_{i} = \dfrac{X_{1} + X_{2} + … + X_{m}}{m}$由于$X_{i}$独立同分布，由$De Moivre–Laplace$定理有
$$ \lim\limits_{n \to \infty} P(2\sqrt{m}(\pi_{i} - \dfrac{1}{2}) \leq x) = \phi(x) $$
可知$\pi_{i}$满足期望$\mu = \dfrac{1}{2}$, 方差$\sigma^{2} = \dfrac{1}{4m}$的正态分布
因此标准中的统计量为
$$ V = \sum\limits_{i=1}^{N} (\dfrac{\pi_{i} - \dfrac{1}{2}}{\dfrac{1}{\sqrt{2m}}})^2 $$
由于取的是不重叠子序列，因此易知$\pi_{i}$相互独立，根据卡方分布的定义可知$V$满足自由度为N的卡方分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(\dfrac{N}{2},\dfrac{V}{2}) $$
扑克检测
此检测利用了皮尔森卡方检验，长度为m的非重叠子序列可分为$2^{m}$类，且每个类别的子序列出现的概率完全相同，均为$\dfrac{1}{2^{m}}$，观测数为N，因此以下统计量
$$ V = \sum\limits_{i=1}^{2^{m}} \dfrac{(n_{i} - N / 2^{m})^2}{N/2^{m}} = \dfrac{2^{m}}{N}\sum\limits_{i=1}^{2^{m}}n_{i}^{2} - N $$
由皮尔森卡方检验，V满足自由度为$2^{m}-1$的$\chi^{2}$分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(\dfrac{2^{m}-1}{2},\dfrac{V}{2}) $$
重叠子序列检测
这个检测利用了I. J. Good在1953年的论文中证明的一个结论，即对于以下统计值
$$ \psi^{2}_{m} = \dfrac{2^{m}}{n} \sum\limits_{i_{1}i_{2}…i_{m}} (v_{i_{1}i_{2}…i_{m}} - \dfrac{n}{2^{m}})^{2} = \dfrac{2^{m}}{n} \sum\limits_{i_{1}i_{2}…i_{m}} v^{2}_{i_{1}i_{2}…i_{m}} - n $$
$$ \psi^{2}_{m-1} = \dfrac{2^{m-1}}{n} \sum\limits_{i_{1}i_{2}…i_{m-1}} (v_{i_{1}i_{2}…i_{m-1}} - \dfrac{n}{2^{m-1}})^{2} = \dfrac{2^{m-1}}{n} \sum\limits_{i_{1}i_{2}…i_{m-1}} v^{2}_{i_{1}i_{2}…i_{m-1}} - n $$
$$ \psi^{2}_{m-2} = \dfrac{2^{m-2}}{n} \sum\limits_{i_{1}i_{2}…i_{m-2}} (v_{i_{1}i_{2}…i_{m-2}} - \dfrac{n}{2^{m-2}})^{2} = \dfrac{2^{m-2}}{n} \sum\limits_{i_{1}i_{2}…i_{m-2}} v^{2}_{i_{1}i_{2}…i_{m-2}} - n $$
$$ \nabla \psi^{2}_{m} = \psi^{2}_{m} - \psi^{2}_{m-1} $$
$$ \nabla^{2} \psi^{2}_{m} = \psi^{2}_{m} - 2\psi^{2}_{m-1} + \psi^{2}_{m-2} $$
有$\nabla \psi^{2}_{m}$和$\nabla^{2} \psi^{2}_{m}$满足自由度为$2^{m-1}$和$2^{m-2}$的$\chi^{2}$分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(2^{m-2},\dfrac{\nabla \psi^{2}_{m}}{2}) $$
$$ p-value = igamc(2^{m-3},\dfrac{\nabla^{2} \psi^{2}_{m}}{2}) $$
游程总数检测
这个检测利用了S Miramontes Beltrán书中讲到的一个结论，由于原来的分布函数在游程数过大的情况下计算量过大，不太方便，因此采用了近似分布
$$ Z = \dfrac{R - 2n\pi(1 - \pi)}{2\sqrt{n}\pi(1 - \pi)} $$
其中$R$为游程总数，且$Z$满足标准正态分布，即游程总数$V_{n} = \sum\limits_{k=1}^{n-1}r(k) + 1$满足期望$\mu = 2n\pi(1 - \pi)$, 方差$\sigma^{2} = 4n\pi^{2}(1 - \pi)^{2}$的正态分布，因此可利用上面$P$值与$erfc$的关系中的结论，得到
$$ p-value = erfc(\dfrac{|V_{n} - 2n\pi(1 - \pi)|}{2\sqrt{2n}\pi(1 - \pi)}) $$
游程分布检测
一个长度为n的随机二元序列中长度为i的游程数目的期望值为
$$ e_{i} = \dfrac{n - i + 3}{2^{i+2}} $$
因此根据皮尔森卡方检验，可分为k类，且每一类的期望可由上面的公式给出，可得
$$ V_{1} = \sum_{i=1}^{k}\dfrac{(b_{i}-e_{i})^{2}}{e_{i}} $$
$$ V_{0} = \sum_{i=1}^{k}\dfrac{(g_{i}-e_{i})^{2}}{e_{i}} $$
且$V_{0}$，$V_{1}$均满足自由度为$k-1$的卡方分布。由卡方分布之和仍为卡方分布的前置知识，可得
$$ V = \sum_{i=1}^{k}\dfrac{(b_{i}-e_{i})^{2}}{e_{i}} + \sum_{i=1}^{k}\dfrac{(g_{i}-e_{i})^{2}}{e_{i}} $$
V满足自由度为$2k-2$的$\chi^{2}$分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(k-1, \dfrac{V}{2}) $$
块内最大”1”游程检测
此检测利用了皮尔森卡方检验，长度为$m$的子序列的最大1游程可按照附录提供的表格分为$K + 1$类，且每个类别的子序列出现的概率也由附录提供的表格给定，观测数为N，因此以下统计量
$$ V = \sum\limits_{i=0}^{K} \dfrac{(v_{i} - N\pi_{i})^{2}}{N\pi_{i}} $$
由皮尔森卡方检验，V满足自由度为$K$的$\chi^{2}$分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(\dfrac{K}{2},\dfrac{V}{2}) $$
由于附录提供的表格中可得$m$为10000时有$K$为6，且标准中$m$取10000，因此有
$$ p-value = igamc(3,\dfrac{V}{2}) $$
二元推导检测
单比特代表的随机变量$X_{i}$满足以下分布
$$ \begin{array}{c|lcr}
X_{i} & 1 & 0 \\
\hline
p & \dfrac{1}{2} & \dfrac{1}{2} \\
\end{array} $$按照标准中的操作，定义函数$\varepsilon_{i}^{(k)} = \varepsilon_{i}^{(k-1)} \oplus \varepsilon_{i+1}^{(k-1)}$，因此可得
$$ \varepsilon_{i}^{(4)} = \varepsilon_{i} \oplus \varepsilon_{i+4} $$
$$ \varepsilon_{i}^{(8)} = \varepsilon_{i} \oplus \varepsilon_{i+8} $$
之所以之选择$k$为4和8的情形，是因为标准中取$k$为3和7且异或操作进行了$k+1$次，以下假定$k$为4或8
累加时的变量满足变换1->1, 0->-1，记该随机变量为$Y_{i}$(由$\varepsilon_{i}^{(k)}$经过该变换得到)，则有
$$ \begin{array}
\varepsilon_{i} & \varepsilon_{i+k} & \varepsilon_{i+2k} & Y_{i} & Y_{i+k} & Y_{i}Y_{i+k} \\
\hline 0 & 0 & 0 & -1 & -1 & 1 \\
\hline 0 & 0 & 1 & -1 & 1 & -1 \\
\hline 0 & 1 & 0 & 1 & 1 & 1 \\
\hline 0 & 1 & 1 & 1 & -1 & -1 \\
\hline 1 & 0 & 0 & 1 & -1 & -1 \\
\hline 1 & 0 & 1 & 1 & 1 & 1 \\
\hline 1 & 1 & 0 & -1 & 1 & -1 \\
\hline 1 & 1 & 1 & -1 & -1 & 1 \\
\end{array} $$现证明$Y_{i}$与$Y_{i+k}$相互独立，$Y_{i}$与$Y_{i+k}$的协方差为
$$ Cov(Y_{i}, Y_{i+k}) = E(Y_{i}Y_{i+k}) - E(Y_{i})E(Y_{i+k}) $$
由表中数据计算可得$E(Y_{i}Y_{i+k}) = E(Y_{i}) = E(Y_{i+k}) = 0$，可知$Y_{i}$与$Y_{i+k}$的协方差$Cov(Y_{i}, Y_{i+k}) = 0$，因此$Y_{i}$与$Y_{i+k}$相互独立，从而$Y_{i}$满足独立同分布，且$Y_{i}$满足如下分布
$$ \begin{array}{c|lcr}
X_{i} & 1 & -1 \\
\hline
p & \dfrac{1}{2} & \dfrac{1}{2} \\
\end{array} $$因此类似单比特频数检测，由中心极限定理，有
$$ \lim\limits_{n \to \infty} P(\dfrac{S_{n-k}}{\sqrt{n-k}} \leq x) = \phi(x) $$
可知此时观测的随机变量为$\dfrac{S_{n-k}}{\sqrt{n-k}}$，满足正态分布，因此可利用上面$P$值与$erfc$的关系中的结论，得到
$$ p-value = erfc(\dfrac{|S_{n-k}|}{\sqrt{2(n-k)}}) $$
自相关检测
类似二元推导检测，此时另$Y_{i} = \varepsilon_{i} \oplus \varepsilon_{i+d} $有
$$ \begin{array}
\varepsilon_{i} & \varepsilon_{i+d} & \varepsilon_{i+2d} & Y_{i} & Y_{i+d} & Y_{i}Y_{i+d} \\
\hline 0 & 0 & 0 & 0 & 0 & 0 \\
\hline 0 & 0 & 1 & 0 & 1 & 0 \\
\hline 0 & 1 & 0 & 1 & 1 & 1 \\
\hline 0 & 1 & 1 & 1 & 0 & 0 \\
\hline 1 & 0 & 0 & 1 & 0 & 0 \\
\hline 1 & 0 & 1 & 1 & 1 & 1 \\
\hline 1 & 1 & 0 & 0 & 1 & 0 \\
\hline 1 & 1 & 1 & 0 & 0 & 0 \\
\end{array} $$现证明$Y_{i}$与$Y_{i+d}$相互独立，$Y_{i}$与$Y_{i+d}$的协方差为
$$ Cov(Y_{i}, Y_{i+d}) = E(Y_{i}Y_{i+d}) - E(Y_{i})E(Y_{i+d}) $$
由表中数据计算可得，$E(Y_{i}Y_{i+d}) = \dfrac{1}{4}$，而$E(Y_{i}) = E(Y_{i+d}) = \dfrac{1}{2}$，因此$Cov(Y_{i}, Y_{i+d}) = \dfrac{1}{4} - \dfrac{1}{2} × \dfrac{1}{2} = 0 $，可证得$Y_{i}$与$Y_{i+d}$相互独立，从而$Y_{i}$满足独立同分布，且$Y_{i}$满足如下分布
$$ \begin{array}{c|lcr}
X_{i} & 1 & 0 \\
\hline
p & \dfrac{1}{2} & \dfrac{1}{2} \\
\end{array} $$因此由$De Moivre–Laplace$定理有
$$ \lim\limits_{n \to \infty} P(\dfrac{2(A(d) - \dfrac{n-d}{2})}{\sqrt{n-d}} \leq x) = \phi(x) $$
可知$A(d)$满足期望$\mu = \dfrac{n-d}{2}$, 方差$\sigma^{2} = \dfrac{n-d}{4}$的正态分布，因此统计值
$$ V = \dfrac{2(A(d) - \dfrac{n-d}{2})}{\sqrt{n-d}} $$
满足正态分布，可利用上面$P$值与$erfc$的关系中的结论，得到
$$ p-value = erfc(\dfrac{|V|}{\sqrt{2}}) $$
矩阵秩检测
此检测利用了皮尔森卡方检验，大小为32×32的矩阵，秩可分为三类，分别是32, 31, 小于31，且每个类别的子序列出现的概率由附录表格提供，观测数为N，记$F_{32}$，$F_{31}$分别为秩为32和31的矩阵的个数，因此以下统计量
$$ V = \dfrac{(F_{32} - 0.2888N)^{2}}{0.2888N} + \dfrac{(F_{31} - 0.5776N)^{2}}{0.5776N} + \dfrac{(N - F_{32} - F_{31} - 0.1336N)^{2}}{0.1336N} $$
由皮尔森卡方检验，V满足自由度为2的$\chi^{2}$分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(1,\dfrac{V}{2}) $$
累加和检测
根据$P$值的定义，有
$$ p-value = P(\max\limits_{1 \leq k \leq n}|S_{k}| \geq z) $$
根据Pal Revesz书中17页定理2.6的结论，可得到
$$ P(\max\limits_{1 \leq k \leq n}|S_{k}| \geq z) = 1 - \sum\limits_{k=-\infty}^{\infty}P((4k-1)z < S_{n} < (4k+1)z) + \sum\limits_{k=-\infty}^{\infty}P((4k+1)z < S_{n} < (4k+3)z) $$
与单比特频数检测中一致，统计值$V = \dfrac{S_{n}}{\sqrt{n}}$满足正态分布，且注意到$S_{n}$的范围是[$-n$, $n$]，因此有
$$ p-value = 1 - \sum\limits_{i=(-(n/z)+1)/4}^{((n/z)-1)/4}[\phi(\dfrac{(4i+1)z}{\sqrt{n}}) - \phi(\dfrac{(4i-1)z}{\sqrt{n}})] + \sum\limits_{i=(-(n/z)+1)/4}^{((n/z)-1)/4}[\phi(\dfrac{(4i+3)z}{\sqrt{n}}) - \phi(\dfrac{(4i+1)z}{\sqrt{n}})] $$
近似熵检测
此检测利用了A. Rukhin在2000年的论文中的一个结论，即统计值
$$ V = 2n[\log s - ApEn(m)] $$
V满足自由度为$(s-1)s^{m}$的卡方分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(\dfrac{(s-1)s^{m}}{2},\dfrac{V}{2}) $$
线性复杂度检测
此检测利用了皮尔森卡方检验，统计值按照规范的算法可分为七类，且每个类别的子序列出现的概率由附录表格提供，观测数为N，因此以下统计量
$$ V = \sum\limits_{i=0}^{6} \dfrac{(v_{i}-N\pi_{i})^{2}}{N\pi_{i}} $$
由皮尔森卡方检验，V满足自由度为6的$\chi^{2}$分布，因此可利用上面$P$值与$igamc$的关系中的结论，得到
$$ p-value = igamc(3,\dfrac{V}{2}) $$
Maurer通用统计检测
令
$$ Y_{i} = \log_{2}(i - T_{j}) $$
$$ f_{n} = \dfrac{1}{K} \sum_{i = Q + 1}^{Q + K} \log_{2}(i - T_{j}) $$
其中$Y_{i} = \log_{2}G$中$G$满足参数为$1 - 2^{-L}$的几何分布。由于$Y_{i}$相互独立，则由中心极限定理，有
$$ \lim\limits_{n \to \infty} P(\dfrac{1}{\sqrt{K} \sigma_{Y}}(Y_{1} + … + Y_{K} - KE(Y)) \leq x) = \phi(x) $$
即
$$ \lim\limits_{n \to \infty} P(\dfrac{\sqrt{K}}{\sigma_{Y}}(f_{n} - E(Y)) \leq x) = \phi(x) $$
此时可知统计值
$$ V = \dfrac{f_{n} - E(Y)}{\sigma} $$
V满足标准正态分布，且$\sigma$满足标准中给出的近似公式，因此可利用上面$P$值与$erfc$的关系中的结论，得到
$$ p-value = erfc(\dfrac{|V|}{\sqrt{2}}) $$
离散傅立叶检测
由于假设离散变量满足二项分布，小于门限值的概率为0.95，可令随机变量$Y_{i}$，当小于门限值时值为1，大于等于门限值时值为0，则满足以下分布
$$ \begin{array}{c|lcr}
Y_{i} & 1 & 0 \\
\hline
p & 0.95 & 0.05 \\
\end{array} $$因此，可计算得到$E(Y_{i})=0.95$, $Var(Y_{i})=\dfrac{0.95×0.05}{2}$。由中心极限定理，有
$$ \lim\limits_{n \to \infty} P(\dfrac{N_{1} - N_{0}}{\sqrt{0.95 × 0.05 × n / 2}} \leq x) = \phi(x) $$
但是貌似和标准中结果不同。因为在Song-Ju Kim等人的论文中提到对该测试的修正，认为并不是独立的，应该是满足$\sigma^{2}=\dfrac{npq}{4}$，从而有了标准中的修正，即
$$ \lim\limits_{n \to \infty} P(\dfrac{N_{1} - N_{0}}{\sqrt{0.95 × 0.05 × n / 4}} \leq x) = \phi(x) $$
由于统计值
$$ V = \dfrac{N_{1} - N_{0}}{\sqrt{0.95 × 0.05 × n / 4}} $$
V满足标准正态分布，因此可利用上面$P$值与$erfc$的关系中的结论，得到
$$ p-value = erfc(\dfrac{|V|}{\sqrt{2}}) $$
参考文献
- 概率论与数理统计-陈希儒
- 皮尔森卡方检验-维基百科
- P值-维基百科
- igamc
- B函数-维基百科
- NIST-STS文档
- I. J. Good (1953). The serial test for sampling numbers and other tests for randomness.
Mathematical Proceedings of the Cambridge Philosophical Society, 49, pp 276-284 doi:10.1017/
S030500410002836X - Rukhin A L. Approximate entropy for testing randomness[J]. Journal of Applied Probability, 2000, 37(1): 88-100.
- Kim S J, Umeno K, Hasegawa A. Corrections of the NIST statistical test suite for randomness[J]. arXiv preprint nlin/0401040, 2004.
- Révész P. Random walk in random and non-random environments[M]. 2005.
- Gibbons J D, Chakraborti S. Nonparametric statistical inference[M]//International encyclopedia of statistical science. Springer Berlin Heidelberg, 2011: 977-979.