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

Question

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

Ergo，我该如何编码我自己的测试，并返回一个对应于统计随机性的单值，一个介于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（随机）
    0123：？少随机
    011：1.0（随机）
    100：1.0（随机）
    101：？随机性较差
    110 1.0（随机）
    0123：非随机

依此类推。

我觉得这可能玩了很多破入串入所有可能子和比较频率，但似乎这种基础的应该已经在计算机科学的早期完成。

Answer 1

这会给你从0到1.0熵数：

你可能想尝试寻找到Shannon Entropy，这是应用于数据和信息的熵度量。事实上，它实际上几乎是熵的物理公式的直接模拟，这是由热力学最公认的解释所定义的。

更具体地说，就你而言，使用二进制字符串，你可以看到Binary Entropy Function，这是一个涉及二进制数据位随机性的特殊情况。

这是通过

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 2

好像你有一堆随机性的启发式。简单地通过这些启发式方法做出一些事情，并对所有启发式方法的平均得分进行评分？

Answer 3

您可能会尝试对字符串进行压缩算法。有更多的重复（更少的随机性），可以压缩的字符串越多。

Answer 4

您似乎在寻找一种方法来查找二进制字符串的Kolmogorov复杂性。可悲的是，这是incomputable。通过压缩算法运行后，字符串的大小可让您了解它的随机程度，因为更多随机字符串的可压缩性较差。

Answer 5

前一段时间，我开发了一个简单的启发式，为我的目的工作。

您只需计算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