6

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

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 (随机)
  010: ? 少随机
  011: 1.0 (随机)
  100: 1.0 (随机)
  101: ? 少随机
  110 1.0（随机）
  111：？非随机

等等。

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

4

4 回答 4

12

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

于 2010-06-22T23:55:41.030 回答
11

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

您可能想尝试研究香农熵，它是应用于数据和信息的熵的度量。事实上，它实际上几乎是熵的物理公式的直接类似物，这是由最被接受的热力学解释所定义的。

更具体地说，在您的情况下，使用二进制字符串，您可以看到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
于 2010-06-23T01:31:44.633 回答
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
于 2010-06-23T00:21:22.160 回答
1

您可以尝试对字符串使用压缩算法。重复越多（随机性越小），字符串可以压缩的越多。

于 2010-06-22T23:55:15.687 回答