五项基本检测包括

• 频数检验（F-检验）
• 序偶检验（S-检验）
• 扑克检验（P-检验）
• 游程检验（R-检验）
• 自相关检验（A-检验）

1. 频数检验（F-检验）

目的：F-检验用来保证"0"和"1"的个数大致相同

输入：n比特序列样本Z，显著性水平α

输出：检验通过或检验失败

步骤：（参见文[1]的5.4.4节）

1. 在此序列截断中统计比特“0”和“1”的个数，分别记为和。

2. 计算检验统计量

（该检验统计量服从自由度为1的开方分布）

3. 计算。如果，则认为待检序列通过本检验。

注1：步骤3和也可改为比较验统计量V与其对应的临界值B（显著性水平α与临界值B的部分取值如下表），即，如果，则认为待检序列通过本检验。

表1 F-检验的显著性水平与临界值B的部分取值

2. 序偶检验（S-检验）

目的：F-检验用来保证合理的转移概率：连续码彼此相同或相异的概率大致相

等，即每个比特都独立于它前面的比特。

输入：n比特序列样本Z，显著性水平α

输出：检验通过或检验失败

步骤：（参见文[1]的5.4.4节）

1. 在此序列截断中统计比特串“00”、“01”、“10”、“11”的个数，分别记为n00,n01,n10,n11；统计比特“0”和“1”的个数，分别记为n0,n1。

2. 计算检验统计量

（该检验统计量近似服从自由度为2的开方分布）

3. 计算。如果，则认为待检序列通过本检验。

注1：步骤3和也可改为比较验统计量V与其对应的临界值B（显著性水平α、临界值B的部分取值如下表），即，如果，则认为待检序列通过本检验。

表2 S-检验的显著性水平α与临界值B的部分取值

3. 扑克检验（P-检验）

同GM/T 0005-2012《随机性检测规范》的扑克检测。

算法描述略。

表3 S-检验的显著性水平α与临界值B的部分取值

4. 游程检验（R-检验）

同GM/T 0005-2012《随机性检测规范》的扑克检测。

算法描述略。

表4 R-检验的显著性水平α与临界值B的部分取值

5. 自相关检验（A-检验）

同GM/T 0005-2012《随机性检测规范》的扑克检测。

算法描述略。自相关的统计量服从正态分布，表略。

参考文献

1. A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography[M]. CRC Press, 1996.
2. GM/T 0005-2012 随机性检测规范.

个人理解，随机搜索是一种在巨大数据规模下执行一个耗时上无法接受的程序的优化方法。
它可以用以对一个搜索算法施展优化的前提是：

1、数据规模大，精确的结果难以在一定时间计算出。
2、结果的些许的不精确能够被接受。
3、求取的结果是最优化（optimization）问题，有一个成本计算模型。

以上自己总结，欢迎补充。

下面还是一步步深入随机搜索算法叙述，也有人把有导向的随机搜索算法称为启发式搜索。

一、最基本的随机搜索

顾名思义，就是随机的搜索，没有特别的要说的，举个例子：有十亿个数字，我想搜索十万次就找出一个比较理想的最小（大）数。这就是一个简单的应用随机搜索的一个场景。这时候我们需要设计一个随机取样的函数，然后在十亿个数里取出十万个数进行比较获取最小（大）的数。虽然后最的结果不精确，但是如果并不需要知道确切的最优值的时候，这还是非常棒的提高程序效率的算法。

这只是一个简单的样例，当然还有许多其他场景会用到随机搜索。但是这种模型非常简单，有时候并不能给出令我们满意的结果，我们还需要对其一步步进行改进。但是核心的思想就是这样的，以后的都是围绕这一思想进行的，这先提前说一下。

二、爬山搜索算法

爬山搜索算法是一种简单的贪心改进，通过基本的搜索算法我们发现，我们并没有利用到已经获得的最优解（假如十亿个数字按一定多项式分布），而是粗暴的进行了随机抽样求取最优解（简单粗暴有时候确实非常好）。贪心策略的假如，使随机搜索算法的效率和准确性有一个较好的提升。如下图所示：

图中有ABCDE五个点，我们想搜寻曲线中最高点，如果我们起始点随机选取到了C点，根据贪心策略，我们会向比C更高的点搜索过去，以此递归能够找到最高点A。同样的如果随机选取的E点同样的搜到最高点A。只有随机开始点在D的位置，我们才能够搜到真正的最高点B。由此我们可以发现爬山搜索算法的一个缺陷，就是比较容易陷入局部最优解中。

一个简单的消除（可能也消除不了）该缺陷的方法就是，我们多次执行该搜索算法，以期随机选取的开始点落在B点两侧的下降曲线上。最后再比较多次执行爬山搜索算法的结果获取更理想的解。有时候被称为“多重爬山算法”。

三、模拟退火算法(Simulated Annealing、SA)

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。
模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。可以证明，模拟退火算法所得解依概率收敛到全局最优解。

以上模拟退火介绍引自wiki，简单的说就是在爬山搜索算法的基础上，添加一个概率函数，这个函数能给出一个概率值来决定是否选取该解当当前一步骤下的局部最优解，即有一定概率能够跳出局部最优解。

模拟退火算法新解的产生和接受可分为如下四个步骤：

1、由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

2、判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。

3、当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

4、模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

算法步骤引自wiki，看wiki上说的已经很清晰了，所以就粘贴过来不再改了。说一下这个接受新解概率的问题，也是算法的关键部分。上述概率公式就是退火过程中原子选择新位置的概率的原理转换过来的，在退火的过程开始阶段，会有较大的概率接受较差的解。随着退火过程的不断进行，算法越来越不可能接受较差的解，直到最后只能接受最优解。比多重爬山算法更可靠，被证明以概率1收敛全局最优解，注意是收敛于全局最优解，而不是一定是全局最优解。（最后细说）

ps：额外说一下，这里模拟退火算法看起来有点聚类算法中K-Means算法的味道，只是比前者多一个概率函数。而我们又知道K-Means算法是有一定概率陷入局部最优解的。那是不是能够在K-Means算法中添入概率函数来改进该算法呢？可以的，其实K-Means算法更类似爬山算法，每次只接受最优解，如果我们每次在选取K个中心点的过程中，添加这一概率函数，使其有一定概率选取周围一些非局部最优点的话，就可以了，或者设计一个模型来选取新点。

模拟退火算法，如果模型建的够好，都是能够改进其他穷举搜索算法的。当然别忘了随机搜索算法应用的前提。

四、遗传算法（Genetic Algorithm、GA）

这个算法也是受自然科学的启发，模拟生物种群的进化，实现的一种计算机模拟算法。算法中参考了种群（population）的形成、进化、物竞天择等概念，有颜色体串（基因串，即某一题解），发生交叉（crossover）、配对（breeding）、变异（mutation）等行为，繁殖产生新的一个更接近全局最优解的新种群，这样递归下去到某一步结束种群的发展。

算法步骤：

1、选取初始种群
2、评价种群个体的适应度
3、按比例选择产生下一个种群
4、改变种群
5、判断停止条件，不满足则返回第二步循环执行

初始种群的选取一般可以随机的选取一些题解。种群个体适应度就是根据成本函数计算出的花费。按比例选择下一代，一般会较高比例选取适应度高（花费低）的个体，也称之为精英选拔，按较低比例选取其他适应度低的个体。这样就产生了新的种群，新种群的组成还没完，还要包括第四步的改变种群，也就是交叉、配对、变异等操作，对已经加入新种群的个体进行修改产生新的个体。一般简单的操作就是进行一些题解的范围的、随机的修改、部分的值的互换、按规则合并等操作。这样一个全新的种群就产生了。然后就是继续评价种群适应度继续选拔。迭代到得到满意解或一定次数为止。

过程中比较关键的一些值还是需要经过多次计算来确定合适值的选取的，比如精英选拔比例，变异概率，成本函数，种群数量等，这些值如果选取还需根据自己需要进行实验而定。

一般的终止条件有：

1、进化次数限制
2、计算耗费的资源限制
3、得到一个满足的最优个体
4、适应度不发生变化
5、人为干预

当然也可以组合使用。

本篇先说这四个随机搜索的算法，还有其他的随机搜索算法，像：局部搜索、禁忌搜索、蚁群算法、人工免疫系统（AIS）算法、人工免疫系统（AIS）、粒子群优化（PSO ）、引力搜索算法（ GSA ）、蚁群聚类方法（ ACCM中） 、随机传播搜索（ SDS ）等等，非常多，自己也需要学习消化和实践，改篇再述。如有问题请留言指正，非常感谢。

最后，很难优化的一个问题：

在上图的最右边，有一个狭长的成本最低区域，接近它的任何解都可能被排除在外，因为这些解的成本都很高，所以我们几乎没有概率得到这样一个全局最小值的途径。这是随机化算法的共同缺陷，没有很好的解决途径。

随机变量

随机变量定义：
样本空间为Ω，随机变量X表示样本空间Ω中的一个样本点（样本空间和随机变量的关系类似于实数轴上的x轴和自变量x的区别）。如随机抛掷一枚骰子，X就是表示骰子的点数。

分布函数

分布函数定义：
F(X)=P(X<=x)
离散型随机变量的分布函数：

连续性随机变量的分布函数：

分布函数的性质：
1.非降性
F(x)是一个非递减函数
2.归一性
在x趋向于+∞时，F(x)趋向于1
3右连续性
因为 F（x）是单调有界非减函数，所以其任一点x0的右极限F（x0+0）必存在。

数学期望

在概率论和统计学中，数学期望（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。

离散型随机变量的期望：

连续型随机变量的期望：

性质：
1.E©=C
2.E(CX)=CE(X)
3.E(X+Y)=E(X)+E(Y)
4.当X和Y相互独立时，E(XY)=E(x)E(y)

方差

方差是在概率论和统计方差衡量随机变量或一组数据时离散程度的度量。概率论中方差用来度量随机变量和其数学期望（即均值）之间的偏离程度。
D(x)=E ( ( X-E( X ) )²)

离散型变量的方差：

随机型变量的方差：

展开上式可得：

性质L:
D©=0
D(CX)=C²D(X)
D(X±Y)=D(X)+D(Y)±2E( (X-E(X))*(Y-E(Y)) )
若X,Y相互独立，则D(X±Y)=D(X)+D(Y)

离散型随机变量三大常见分布：

1.两点分布（伯努利分布）
定义：
一个非常简单只有两个可能结果的试验，比如正面或反面，成功或失败，有缺陷或没有缺陷，病人康复或未康复。记为X~（0,1）

分布律：

性质：
期望E(X)=p
方差D(X)=p(1-p)

2.二项分布
定义：
在n次独立重复的伯努利试验中，设每次试验中事件A发生的概率为p。用X表示n重伯努利试验中事件A发生的次数，则X的可能取值为0，1，…，n,且对每一个k（0≤k≤n）,事件{X=k}即为“n次试验中事件A恰好发生k次”，随机变量X的离散概率分布即为二项分布。
可以简单理解为多次抛硬币事件的概率分布。
记做X~b（n，p）

分布律：

性质：
期望E(X)=np
方差D(X)=np(1-p)
就是在两点分布的基础上乘以一个n

泊松分布：
定义：
二项分布的近似解，当n非常大，p非常小，计算十分复杂时，可以用泊松公式求近似解。（n＞200，p＜0.05） 记做X~P（λ）

概率函数：
λ表示数学期望，即np
k表示事件发生的次数

性质：
期望E(X)=λ=np
方差D(X)=λ

均匀分布
定义：
均匀分布也叫矩形分布，它是对称概率分布，在相同长度间隔的分布概率是等可能的。 均匀分布由两个参数a和b定义，它们是数轴上的最小值和最大值，通常缩写为X~U（a，b）。

概率密度函数：
a表示区间上界，b表示区间下界

性质：
期望E(X)=(a+b)/2
方差D(X)=(b-a)²/12

指数分布：
定义：
指数分布（也称为负指数分布）是描述泊松过程中的事件之间的时间的概率分布，即事件以恒定平均速率连续且独立地发生的过程。 这是伽马分布的一个特殊情况。 它是几何分布的连续模拟，它具有无记忆的关键性质。 除了用于分析泊松过程外，还可以在其他各种环境中找到。记做X~ E（λ）

概率密度函数：
λ表示期望的倒数

性质
期望E(X)=1/λ
方差D(X)=1/λ²

正态分布（高斯分布）
定义：
若随机变量X服从一个数学期望为μ、方差为σ²的正态分布，记为X~N(μ，σ2)。其概率密度函数为正态分布的期望值μ决定了其位置，其标准差σ决定了分布的幅度。当μ = 0,σ = 1时的正态分布是标准正态分布。

概率密度函数：

标准化：

将Y化为x的形式，转换为标准正态分布，方便查表计算。也可以用来算μ和σ。
F((96-0.5)/σ)=0.05，查表的到（96-0.5）/σ=2，可以求得σ。

性质
期望E(X)=μ
方差D(X)=σ²

到这里概率论的基础就完结了，开始上数理统计部分了。概率论对深度学习帮助挺大的，主要是帮助理解概念，方便搭建更优化的神经网络。