一尘不染

如何确定二进制字符串的统计随机性?

algorithm

如何确定二进制字符串的统计随机性?

如此,我该如何编码自己的测试,并返回与统计随机性相对应的单个值,即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 :?非随机

等等。

我认为这可能对将字符串分成所有可能的子字符串和比较频率起很大作用,但是似乎这种基础工作应该在计算机科学的早期就已经完成。


阅读 317

收藏
2020-07-28

共1个答案

一尘不染

这将使您的熵计数从0到1.0:

您可能想尝试研究Shannon熵,它是一种应用于数据和信息的熵的度量。实际上,实际上,它几乎是熵的物理公式的直接类似物,如热力学最受接受的解释所定义。

更具体地说,在您的情况下,对于二进制字符串,您可以看到 Binary Entropy
Function

,这是一种特殊情况,涉及数据二进制位中的随机性。

这是由

H(p) = -p*log(p) - (1-p)*log(1-p)

(以2 0*log(0)为底的对数;假设为0)

p您的1(或0)的百分比在哪里;图形是对称的,所以您的答案都是相同的

函数产生的结果如下:

二进制熵函数

如您所见,如果p为0.5(1的数量与0的数量相同),则您的熵最大(1.0)。如果p为0或1.0,则熵为0。

这似乎正是您想要的,对吗?

唯一的例外是您的 1号尺码 案件,可以将其作为例外。但是,对于我来说100%0和100%1似乎不太熵。但是,您可以根据需要实施它们。

而且,这没有考虑到位的任何“排序”。只有它们的总和。因此,重复/回文不会得到任何帮助。您可能要为此添加一个额外的启发式方法。

这是您的其他案例示例:

00:-0 * log(0)-(1-0)* log(1-0)= 0.0
01:-0.5 * log(0.5)-(1-0.5)* log(1-0.5)= 1.0
010:-(1/3)* log(1/3)-(2/3)* log(2/3)= 0.92
0100:-0.25 * log(0.25)-(1-0.25)* log(1-0.25)= 0.81
2020-07-28