计算机科学

首页 > 计算机科学

随机性

随机性英语:Randomness)这个词是用来表达目的、动机、规则或一些非科学用法的可预测性的缺失。

一个随机的过程是一个不定因子不断产生的重复过程,但它可能遵循某个概率分布。

术语随机经常用于统计学中,表示一些定义清晰的、彻底的统计学属性,例如缺失偏差或者相关。随机与任意不同,因为“一个变量是随机的”表示这个变量遵循概率分布。而任意在另一方面又暗示了变量没有遵循可限定概率分布。

随机在自然科学和哲学上有着重要的地位。

目录

  • 1 科学与随机
    • 1.1 物理科学
    • 1.2 生物学
    • 1.3 通信理论
  • 2 随机性测试方法
  • 3 参考文献
    • 3.1 引用
    • 3.2 书籍

科学与随机

在自然与工程学里一些现象会通过随机性模型来模拟,例如:

  • 混沌理论
  • 密码学
  • 博弈论
  • 信息论
  • 模式识别
  • 机率论
  • 量子力学
  • 统计学
  • 统计力学

物理科学

在19世纪,科学家使用分子的不规则行动的概念去发展统计力学,以解释热力学和气体定律的现象。

根据一些量子力学的标准解释,微观现象是客观地随意。换句话说,在一个所有相关的参量受控的实验中,也会出现任意变化的情况,例如我们无法预计在受控环境中放置一粒不稳定的原子衰败的时间,只能计算在指定的时间内衰败的可能性,所以量子力学计算的是机会率而非单一实验的结果。Hidden variable theories尝试避开大自然包含不能降低的随机性,这样的理论假定在看上去任意的过程中,有些符合统计分布而暗藏的特性在幕后运作以得出结果。

生物学

进化论将观察到的多样性归因于随机突变。由于一些突变的基因带给了拥有它们的个体更高的存活与繁衍的机会,随机突变保留在了基因库中。

生物体的特征在某种程度上是确定性地发生的(例如:在基因和环境的影响下),在某种程度上是随机发生的。例如,基因与曝光量仅仅支配着人体皮肤上出现的色斑密度;而单个色斑的精确位置看来是随机决定的。

通信理论

在通信理论中,一个信号的随机性称作噪声,它对立于由源(信号)所引起的那一部分变化。

随机性测试方法

  1. 频数测试:测试二进制串行中,“0”和“1”数目是否近似相等。如果是,则串行是随机的。[1]
  2. 块内频数测试:目的是确定在待测串行中,所有非重叠的长度为M位的块内的“0”和“1”的数目是否表现为随机分布。如果是,则串行是随机的。
  3. 游程测试:目的是确定待测串行中,各种特定长度的“0”和“1”的游程数目是否如真随机串行期望的那样。如果是,则串行是随机的。
  4. 块内最长连续“1”测试:目的是确定待测串行中,最长连“1”串的长度是否与真随机串行中最长连“1”串的长度近似一致。如果是,则串行是随机的。
  5. 矩阵秩的测试:目的是检测待测串行中,固定长度子串行的线性相关性。如果线性相关性较小,则串行是随机的。
  6. 离散傅里叶变换测试:目的是通过检测待测串行的周期性质,并与真随机串行周期性质相比较,通过它们之间的偏离程度来确定待测串行随机性。如果偏离程度较小,串行是随机的。
  7. 非重叠模板匹配测试:目的是检测待测串行中,子串行是否与太多的非周期模板相匹配。太多就意味着待测串行是非随机的。
  8. 重叠模板匹配测试:目的是统计待测串行中,特定长度的连续“1”的数目,是否与真随机串行的情况偏离太大。太大是非随机的。
  9. 通用统计测试:目的是检测待测串行是否能在信息不丢失的情况下被明显压缩。一个不可被明显压缩的串行是随机的。
  10. 压缩测试:目的是确定待测串行能被压缩的程度,如果能被显著压缩,说明不是随机串行。
  11. 线性复杂度测试:目的是确定待测串行是否足够复杂,如果是,则串行是随机的。
  12. 连续性测试:目的是确定待测串行所有可能的m位比特的组合子串出现的次数是否与真随机串行中的情况近似相同,如果是,则串行是随机的。
  13. 近似熵测试:目的是通过比较m位比特串与m-1位比特串在待测串行中出现的频度,再与正态分布的串行中的情况相对比,从而确定随机性。
  14. 部分和测试:目的确定待测串行中的部分和是否太大或太小。太大或太小都是非随机的。
  15. 随机游走测试:目的是确定在一个随机游程中,某个特定状态出现的次数是否远远超过真随机串行中的情况。如果是,则串行是非随机的。
  16. 随机游走变量测试:目的是检测待测串行中,某一特定状态在一个游机游程中出现次数与真随机串行的偏离程度。如果偏离程度较大,则串行是非随机的。

参考文献

引用

  1. ^ 师, 国栋; 康绯,顾海文. 随机性测试的研究与实现. 2009年10月 [2013-02-23]. 

书籍

  • Randomness by Deborah J. Bennett. Harvard University Press, 1998. ISBN 0-674-10745-4
  • Random Measures, 4th ed. by Olav Kallenberg. Academic Press, New York, London; Akademie-Verlag, Berlin (1986). MR0854102
  • The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, 3rd ed. by Donald E. Knuth, Reading, MA: Addison-Wesley, 1997. ISBN 0-201-89684-2
  • Fooled by Randomness, 2nd ed. by Nassim Nicholas Taleb. Thomson Texere, 2004. ISBN 1-58799-190-X
  • Exploring Randomness by Gregory Chaitin. Springer-Verlag London, 2001. ISBN 1-85233-417-7

上一篇:费斯妥密码
下一篇:雪崩效应
相关推荐