c++ - ¿Cómo puedo determinar la aleatoriedad estadística de una cadena binaria?

algorithm entropy

Question

¿Cómo puedo determinar la aleatoriedad estadística de una cadena binaria?

Ergo, ¿cómo puedo codificar mi propia prueba y devolver un único valor que corresponde a la aleatoriedad estadística, un valor entre 0 y 1.0 (0 no es aleatorio, 1.0 es aleatorio)?

La prueba necesitaría trabajar en cadenas binarias de cualquier tamaño.

Cuando lo haces con lápiz y papel, puedes explorar cadenas como esta:
0 (aleatoriedad arbitraria, la única otra opción es 1)
00 (no aleatorio, es una repetición y coincide con el tamaño)
01 (mejor, dos valores diferentes)
010 (menos aleatorio, palíndromo)
011 (menos aleatorio, más 1, aún aceptable)
0101 (menos aleatorio, patrón)
0100 (mejor, menos unos, pero cualquier otra distribución causa patrones)

Ejemplos de casos:

Tamaño: 1, Posibilidades: 2
0: 1.0 (al azar)
1: 1.0 (aleatorio)

Tamaño: 2, P: 4
00:?
01: 1.0 (aleatorio)
10: 1.0 (aleatorio)
11: ¿?

S: 3, P: 8
000:? no aleatorio
001: 1.0 (al azar)
010:? menos aleatorio
011: 1.0 (al azar)
100: 1.0 (aleatorio)
101:? menos aleatorio
110 1.0 (aleatorio)
111:? no aleatorio

Y así.

Siento que esto puede ser una gran ventaja para dividir la cadena en todas las subcadenas posibles y comparar frecuencias, pero parece que este tipo de base ya debería haberse hecho en los primeros días de la informática.

Answer 1

Parece que está buscando una forma de encontrar la complejidad de Kolmogorov de una cadena binaria. Lamentablemente, esto es incomputable . El tamaño de la cadena después de ejecutarlo a través de un algoritmo de compresión le dará una idea de qué tan aleatorio es, ya que las cadenas más aleatorias son menos compresibles.

Answer 2

Puede probar un algoritmo de compresión en la cadena. Cuanta más repetición (menos aleatoriedad) haya, más se puede comprimir la secuencia.

Answer 3

parece que tienes un montón de heurísticas para la aleatoriedad. ¿Simplemente hace algo que se ejecuta a través de esas heurísticas y puntúa el flujo de bits en promedio de todas las heurísticas?

Answer 4

Hace algún tiempo, desarrollé una heurística simple que funcionó para mis propósitos.

Simplemente calcula la "igualdad" de 0 y 1 no solo en la cadena en sí, sino también en las derivadas de la cadena. Por ejemplo, la primera derivada de 01010101 es 11111111, porque cada bit cambia, y la segunda derivada es 00000000, porque ningún bit en la primera derivada cambia. Entonces simplemente tiene que sopesar estos "pares" según su gusto.

Aquí hay un ejemplo:

#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;
}

Sus entradas de ejemplo producen una "aleatoriedad" de 0.129032, 0.133333 y 3.2 respectivamente.

En una nota lateral, puedes obtener gráficos fractales al derivar cadenas;)

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

Answer 5

Esto le dará una cuenta de entropía de 0 a 1.0:

Puede intentar buscar en la Entropía de Shannon , que es una medida de entropía aplicada a datos e información. De hecho, en realidad es casi un análogo directo de la fórmula física para la entropía según lo definido por las interpretaciones más aceptadas de la termodinámica.

Más específicamente, en su caso, con una cadena binaria, puede ver la Función de Entropía Binaria , que es un caso especial que involucra la aleatoriedad en bits de datos binarios.

Esto es calculado por

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

(logaritmos en la base 2; supongamos que 0*log(0) es 0)

Donde p es su porcentaje de 1 (o de 0, el gráfico es simétrico, por lo que su respuesta es la misma)

Esto es lo que produce la función:

Como puede ver, si p es 0.5 (la misma cantidad de 1 es 0), su entropía es máxima (1.0). Si p es 0 o 1.0, la entropía es 0.

Esto parece ser justo lo que quieres, ¿verdad?

La única excepción son los casos de tamaño 1 , que podrían ser una excepción. Sin embargo, 100% de 0 y 100% de 1 no me parecen demasiado entrópicos. Pero impleméntalos como quieras.

Además, esto no tiene en cuenta ningún "orden" de los bits. Solo la suma total de ellos. Por lo tanto, la repetición / palíndromos no recibirá ningún impulso. Es posible que desee agregar una heurística adicional para esto.

Aquí están sus otros ejemplos de casos:

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