Comment puis-je déterminer le caractère aléatoire statistique d'une chaîne binaire?

Question

Comment puis-je déterminer le caractère aléatoire statistique d'une chaîne binaire? Ergo, comment puis-je coder mon propre test, et retourner une seule valeur qui correspond au hasard statistique, une valeur entre 0 et 1.0 (0 étant aléatoire, 1.0 étant aléatoire)?

Le test devrait fonctionner sur des chaînes binaires de toute taille.

Lorsque vous le faites avec un stylo et du papier, vous pouvez explorer des chaînes comme ceci:
    0 (aléatoire arbitraire, le seul autre choix est 1)
    00 (pas au hasard, sa répétition et matchs la taille)
    01 (mieux, deux valeurs différentes)
    010 (moins aléatoire, palindrome)
    011 (moins aléatoires, plus de 1, encore acceptable)
    0101 (moins aléatoire, motif)
    0100 (meilleurs, moins chers, mais toute autre distribution provoque des motifs)

Exemples de cas:

Taille: 1, Possibilités: 2
    0: 1,0 (aléatoire)
    1: 1,0 (aléatoire)

Taille: 2, P: 4
    00:?
    01: 1.0 (aléatoire)
    10: 1,0 (aléatoire)
    11:

S: 3, P: 8
    000:? non aléatoire
    001: 1,0 (aléatoire)
    010:? moins aléatoire
    011: 1.0 (aléatoire)
    100: 1,0 (aléatoire)
    101: moins aléatoire
    110 1,0 (aléatoire)
    111:? non aléatoire

Et ainsi de suite.Je pense que cela peut jouer un rôle important dans la rupture de la chaîne dans toutes les sous-chaînes possibles et la comparaison des fréquences, mais il semble que ce genre de travail de fond aurait déjà dû être fait dans les débuts de l'informatique. Il semble que vous ayez un tas d'heuristiques pour l'aléatoire.

Answer 1

Cela vous donnera un compte d'entropie de 0 à 1,0:

Vous pouvez essayer de regarder en le Shannon Entropy, qui est une mesure de l'entropie appliquée aux données et informations. En fait, il est en fait presque un analogue direct de la formule physique pour l'entropie telle que définie par les interprétations les plus acceptées de la thermodynamique. Plus précisément, dans votre cas, avec une chaîne binaire, vous pouvez voir le Binary Entropy Function, qui est un cas particulier impliquant l'aléatoire dans les bits binaires de données.

Il est calculé par

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

(logarithmes en base 2, supposons 0*log(0) est 0)

Où p est votre pourcentage de 1 de (ou de 0, le graphique est symétrique, de sorte que votre réponse est le même dans les deux cas)

Voici ce que les rendements de la fonction:

Comme vous pouvez le voir, si p est 0.5 (même nombre de 1 que 0), votre entropie est au maximum (1.0). Si p est 0 ou 1.0, l'entropie est 0.

Cela semble être juste ce que vous voulez, non? La seule exception est votre cas de taille 1, qui pourrait simplement être mis en exception. Cependant, 100% 0 et 100% 1 ne me semblent pas trop entropiques. Mais implémentez-les comme vous le souhaitez.

De même, cela ne prend en compte aucun "classement" des bits. Seulement la somme totale d'entre eux. Donc, répétition/palindromes ne sera pas boosté. Vous pourriez vouloir ajouter une heuristique supplémentaire pour cela.

Voici vos autres exemples de cas:

 
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

Faites simplement quelque chose qui traverse ces heuristiques et marque le flux binaire sur la moyenne de toutes les heuristiques?

Answer 3

Vous pouvez essayer un algorithme de compression sur la chaîne. Plus il y a de répétitions (moins de hasard), plus la chaîne peut être compressée.

Answer 4

Vous semblez demander un moyen de trouver la complexité de Kolmogorov d'une chaîne binaire. Malheureusement, c'est . La taille de votre chaîne après l'avoir exécutée via un algorithme de compression vous donnera une idée de son caractère aléatoire, en ce sens que des chaînes plus aléatoires sont moins compressibles.

Answer 5

Il ya quelque temps, j'ai développé une heuristique simple qui a fonctionné pour mes buts.

Vous calculez simplement l '"égalité" de 0 et de 1 non seulement dans la chaîne elle-même, mais aussi sur les dérivées de la chaîne. Par exemple, la première dérivée de 01010101 est 11111111, car chaque bit change, et la dérivée seconde est 00000000, car aucun bit de la dérivée première ne change. Ensuite, il vous suffit de peser ces "even-nesses" selon vos goûts.

Voici un exemple:

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

Vos entrées exemple, le rendement d'un « hasard » de 0,129032, 0,133333 et 3,2 respectivement.

Sur une note côté, vous pouvez obtenir graphiques fractales fraîches par des chaînes dérivant;)

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