如何确定二进制字符串的统计随机性?
因此,我如何编写自己的测试,并返回与统计随机性相对应的单个值,即 0 到 1.0 之间的值(0 不是随机的,1.0 是随机的)?
该测试需要适用于任何大小的二进制字符串。
当您使用笔和纸执行此操作时,您可能会探索如下字符串:
0(任意随机性,唯一的其他选择是1)
00(不是随机的,它是重复的并且与大小匹配)
01(更好,两个不同的值)
010(随机性较低,回文)
011(随机性较低,1较多,仍然可以接受)
0101(随机性较低,图案)
0100(更好,更少,但任何其他分布都会导致模式)
案例:
尺寸:1,可能性:2
0:1.0(随机)
1:1.0(随机)
尺寸:2,P:4
00: ?
01:1.0(随机)
10:1.0(随机)
11: ?
S:3, P:8
000:?非随机
001:1.0(随机)
010:?不太随机
011:1.0(随机)
100:1.0(随机)
101:?不太随机
110 1.0(随机)
111:?非随机
等等。
我觉得这可能在将字符串分解为所有可能的子字符串和比较频率方面发挥很大作用,但似乎这种基础工作应该在计算机科学的早期就已经完成了。
您似乎在寻求一种找到二进制字符串的柯尔莫哥洛夫复杂度的方法。可悲的是,这是无法计算的。通过压缩算法运行字符串后的大小将使您了解它的随机性,因为随机字符串越多,可压缩性就越差。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)