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

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:     00:?
    01: 1.0 (случайный)
    10: 1.0 (случайный)
    11:?

S: 3, P: 8
    000:? неслучайное
    001: 1.0 (random)
    010:? менее случайные
    011: 1.0 (случайная)
    100: 1.0 (случайные)
    101:? менее случайным
    110 1,0 (случайный)
    111:? неслучайное

И так далее.

Я чувствую, что это может сыграть большую роль в разрыве струны во всевозможные подстроки и сравнение частот, но похоже, что эта основа была уже сделана в первые дни компьютерных наук.

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 (такое же количество 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 

Answer 2

похоже, что у вас есть куча эвристик для случайности. Просто сделать что-то, что проходит через эти эвристики и оценивает битовый поток в среднем по всем эвристикам?

Answer 3

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

Answer 4

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

Answer 5

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

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