Как я могу определить статистическую случайность двоичной строки?

Некоторое время назад я разработал простую эвристику, которая работала для моих целей.

Вы просто вычисляете "четность" нулей и единиц не только в самой строке, но и на производных от строки. Например, первая производная 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

Вы, кажется, просите найти колмогорову сложность двоичной строки. К сожалению, это невычислимо. Размер вашей строки после ее запуска через алгоритм сжатия даст вам представление о том, насколько она случайна, в том, что более случайные строки менее сжимаемы.

Вы можете попробовать алгоритм сжатия строки. Чем больше повторений (меньше случайности), тем сильнее можно сжать строку.