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

Question

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

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

等等.

我觉得这可能会在将字符串分解为所有可能的子串并比较频率方面发挥很大作用,但似乎这种基础工作应该在计算机科学的早期就已经完成了.

Answer 1

你似乎在寻找一种方法来找到二进制字符串的Kolmogorov复杂性.可悲的是,这是无法计算的.通过压缩算法运行后,字符串的大小将让您了解它的随机性,因为更多随机字符串的可压缩性更低.

Answer 2

这将为您提供从0到1.0的熵计数:

您可能想尝试查看Shannon熵,它是应用于数据和信息的熵的度量.事实上,它实际上几乎是熵的物理公式的直接类比,正如最常被接受的热力学解释所定义的那样.

更具体地说,在您的情况下,使用二进制字符串,您可以看到二进制熵函数,这是一个涉及二进制数据位随机性的特殊情况.

这是通过计算的

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

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

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

这是函数产生的:

如您所见,如果p是0.5(与0的1相同的数量),则您的熵最大(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

Answer 3

前段时间,我开发了一个适用于我的目的的简单启发式算法.

你只需要在字符串本身中计算0和1的"偶数",而且还可以计算字符串的导数.例如,01010101的一阶导数是11111111,因为每个位都改变,而二阶导数是00000000,因为一阶导数中的位没有改变.然后你只需根据自己的口味称量这些"偶数".

这是一个例子:

#include <string>
#include <algorithm>

float variance(const std::string& x)
{
    int zeroes = std::count(x.begin(), x.end(), '0');
    float total = x.length();
    float deviation = zeroes / total - 0.5f;
    return deviation * deviation;
}

void derive(std::string& x)
{
    char last = *x.rbegin();
    for (std::string::iterator it = x.begin(); it != x.end(); ++it)
    {
        char current = *it;
        *it = '0' + (current != last);
        last = current;
    }
}

float randomness(std::string x)
{
    float sum = variance(x);
    float weight = 1.0f;
    for (int i = 1; i < 5; ++i)
    {
        derive(x);
        weight *= 2.0f;
        sum += variance(x) * weight;
    }
    return 1.0f / sum;
}

int main()
{
    std::cout << randomness("00000000") << std::endl;
    std::cout << randomness("01010101") << std::endl;
    std::cout << randomness("00000101") << std::endl;
}

您的示例输入产生的"随机性"分别为0.129032,0.133333和3.2.

在旁注中,您可以通过派生字符串获得酷分形图形;)

int main()
{
    std::string x = "0000000000000001";
    for (int i = 0; i < 16; ++i)
    {
        std::cout << x << std::endl;
        derive(x);
    }
}

0000000000000001
1000000000000001
0100000000000001
1110000000000001
0001000000000001
1001100000000001
0101010000000001
1111111000000001
0000000100000001
1000000110000001
0100000101000001
1110000111100001
0001000100010001
1001100110011001
0101010101010101
1111111111111111