Computation, math

Chaînes et hasard

Introduction

Comment mesurer le caractère aléatoire d’une chaîne de bits ? Prenons quatre exemples :

    A = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    B = 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
    C = 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
    D = 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 1

Clairement, il y a un sens du mot « aléatoire » pour lequel la chaîne B est plus « aléatoire » que la A, la C plus que la B, etc. Malheureusement, ce sens est probablement la complexité de Kolmogorov. En une phrase, c’est la longueur du plus petit programme qui génère la chaîne de bits considérée. Évidemment, la complexité de Kolmogorov est incalculable. Aujourd’hui, j’estime donc la complexité de Kolmogorov d’une chaîne de bits par différentes méthodes.

Méthodes


Shannon

Ma première idée était d’utiliser l’entropie de Shannon. Il faut donc choisir la longueur des lettres de l’alphabet considéré. Pour reprendre les exemples plus haut avec différentes longueurs de lettres (en bits):

Chaîne Taille des lettres
1 bit/lettre 2 bit/lettre 4 bit/lettre 8 bit/lettre 16 bit/lettre
A = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
B = 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0
C = 0 1 1 0 0 1 1 0 0 1 1 0 1 0,5 0 0 0
D = 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0,5 0,125 0

Avec des lettres de 1 bit, toutes les chaînes (sauf la première) ont la même entropie maximale de 1 bit/lettre. Avec des lettres de 12 bits, toutes les chaînes ont la même entropie minimale de 0 bit/lettre. Pour chaque chaîne, l’entropie est nulle quand la longueur de la lettre est égale à (un multiple de) la longueur du pattern utilisé. Il y a deux difficultés majeures : il faut détecter les régularités qui sont effectivement présentes, mais il faut avoir assez de lettres dans la chaîne pour que les fréquences soient représentatives.

Méthode :

  1. Calculer l’entropie de Shannon de la chaîne pour des longueurs de lettres entre 1 et m bits. (avec m tel que 2m > n/(32m) et n le nombre total de bits dans la chaîne ; ainsi il y a toujours au moins 32 fois plus de lettres dans la chaîne qu’il n’y a de lettres possibles dans l’alphabet)
  2. Garder l’entropie la plus basse

ApEn

En cherchant plus, je suis tombé sur un papier1 du NIST contenant des techniques pour décider si une chaîne de bits est aléatoire. La première qui a attiré mon attention est l’entropie approximative (ApEn). Elle consiste à calculer l’entropie de Shannon de la chaîne pour deux longueurs successives de mots puis les soustraire. Pour les mêmes exemples que plus haut :

Chaîne ApEn
A = 0 0 0 0 0 0 0 0 0 0 0 0 0
B = 0 1 0 1 0 1 0 1 0 1 0 1 0
C = 0 1 1 0 0 1 1 0 0 1 1 0 0
D = 0 1 1 1 0 0 1 0 1 0 0 1 0,78

Je ne suis pas très sûr d’avoir compris ce qui était mesuré ainsi, mais on peut au moins différencier les chaînes peu aléatoires et très aléatoires.

Méthode :

  1. Calculer l’entropie de Shannon Hm de la chaîne pour deux longueurs de lettres m et m+1. (avec m = floor(log2(n))-5, n est le nombre total de bits dans la chaîne ; ainsi il y a au moins 32 fois plus de lettres dans la chaîne qu’il n’y a de lettres possibles dans l’alphabet)
  2. Calculer Hm+1 – Hm

Serial Test

La deuxième méthode qui a attiré mon attention dans le même papier2 du NIST, est le Test Sériel. Il consiste à comparer la fréquence observée de chaque lettre possible avec sa fréquence attendue si le message était aléatoire. Ce calcul est répété pour trois longueur de lettre successives (m, m+1 et m+2) que le test combine pour donner une mesure. Encore les mêmes exemples :

Chaîne Test Sériel
A = 0 0 0 0 0 0 0 0 0 0 0 0 64
B = 0 1 0 1 0 1 0 1 0 1 0 1 32
C = 0 1 1 0 0 1 1 0 0 1 1 0 16
D = 0 1 1 1 0 0 1 0 1 0 0 1 3

Je ne suis toujours pas très sûr de ce qui est mesuré exactement, mais là aussi ça semble plutôt marcher. Cette fois-ci les chaînes moins aléatoires obtiennent des scores plus élevés.

Méthode

  1. Voir la description donnée dans la source3 parce que j’ai la flemme de tout réexpliquer
  2. Et de toute façon j’aime pas cette méthode.
  3. Non mais, bon, hein, voilà.

Bientropy

En fouillant un peu plus, je suis tombé sur un papier4 de G. J. Croll, qui semble approcher le problème selon un angle légèrement différent. La méthode décrite utilise l’entropie de Shannon avec des lettres de 1 bit, mais l’applique à toutes les dérivées binaires successives de la chaîne. La dérivée binaire est le résultat d’un XOR de la chaîne sur elle-même. La mesure finale est une somme pondérée des entropies calculées. Toujours les mêmes exemples :

Chaîne Bientropy
A = 0 0 0 0 0 0 0 0 0 0 0 0 0
B = 0 1 0 1 0 1 0 1 0 1 0 1 0,02
C = 0 1 1 0 0 1 1 0 0 1 1 0 0,10
D = 0 1 1 1 0 0 1 0 1 0 0 1 0,78

Cette méthode a l’air prometteuse, les chaînes ont toutes un score différent et elles sont classées dans le bon ordre.

Méthode :

  1. Calculer l’entropie de Shannon de le chaîne et de toutes ses dérivés binaire.
  2. Calculer la somme pondérée de toutes les entropies obtenues (le poids de chaque entropie est log2(k+2) avec k le nombre de fois que la chaîne a été dérivée pour obtenir cette entropie)

Échantillon

Pour confronter les méthodes ci-dessus à des cas de figure variés, j’ai décidé de tester des chaînes de bits de longueurs différentes (16, 64, 256, 1024 et 4096 bits). Je les ai aussi générées de façon obtenir des taux de compression qui vont de ~0 (très aléatoire) à ~1 (très régulier).

Étalon

Pour comparer les différentes méthodes, il me faut une mesure étalon que je sais être bonne. J’ai choisi le taux de compression de l’algorithme DEFLATE (utilisé pour compresser les images png notamment).

Chaîne DEFLATE
A = 0 0 0 0 0 0 0 0 0 0 0 0 1
B = 0 1 0 1 0 1 0 1 0 1 0 1 0,89
C = 0 1 1 0 0 1 1 0 0 1 1 0 0,56
D = 0 1 1 1 0 0 1 0 1 0 0 1 0

Pourquoi DEFLATE ?

  • 1re raison : la complexité de Kolmogorov est environ équivalente au formalisme longueur minimale de message. Et le formalisme longueur minimale de message est (je simplifie) le nombre minimum de bits qu’il faut transmettre à un interlocuteur pour qu’il puisse reconstruire un message. Si le message est peu aléatoire, il est peu complexe selon Kolmogorov, un message court suffit pour le transmettre et donc il devrait être facilement compressible.
  • 2e raison : je connais un peu DEFLATE (je l’avais implémenté dans octave pour un autre projet)
  • 3e raison : il y a des scripts (notamment le fabuleux optipng) pour optimiser très agressivement la taille d’une image png, ce qui devrait m’approcher aussi près que possible du cas idéal (incalculable aussi, évidemment).

Mesure

Ce qui m’intéresse surtout ici, plus que les valeurs obtenues par chaque méthode, c’est l’ordre dans lequel chaque méthode classe les différentes chaînes de bits. Le score de chaque méthode dans la suite est donc le coefficient de correlation de Spearman entre les valeurs de compression de DEFLATE et les valeurs données par la méthode considérée pour l’ensemble des chaînes de bits préparées.

Résultats

Méthode Longueur de la chaîne
16 64 256 1024 4096 Moyenne
Shannon 0.71 0.31 0.28 0.05 0.10 0.29
ApEn 0.95 0.79 0.60 0.64 0.60 0.72
Test Sériel 0.90 0.76 0.74 0.72 0.63 0.75
Bientropie 0.88 0.68 0.90 0.85 0.84 0.83

On voit que l’entropie de Shannon est nettement inférieure aux autres méthodes. L’Entropie Approximative est meilleure pour les chaines courtes. La Bientropie est nettement meilleure pour les chaînes longues. Le Test Sériel est entre les deux.

La suite au prochain épisode pour savoir à quoi tout ça va servir.

Par défaut
math

Busy Beaver

Pour coder en FORTRAN, j’ai décidé de retrouver les Busy Beavers de petite taille (nombre d’états  n \leqslant 4 ).

Comme les valeurs de  S(n,2) sont connues pour  n petit, j’ai simplement simulé toutes les Machines de Turing (TM) à  n état(s) et deux symboles pendant 125 steps (soit  S(4,2)+18 steps). Celles qui ne se sont pas arrêtées après  S(n,2) steps ne s’arrêtent jamais. Et Ô bonheur, j’ai retrouvé les bonnes valeurs :

n  S(n,2)  \Sigma(n,2)
1 1 1
2 6 4
3 21 6
4 107 13

Mais la partie interessante de ce projet, pour moi, c’est les temps qu’il a fallu à mon pauvre ordinateur pour calculer tout ça. Pour n=1, mon ordinateur teste toutes les TM possibles en quelques fractions de secondes. Mais pour n=4, il lui a fallu 12 (!) jours. Les TM avec plus d’états ne sont pas (beaucoup) plus difficiles à simuler, mais il y en a beaucoup plus :

 TM(n) = (4n+4)^{2n}

Avec  TM(n) le nombre de TM à n états et deux lettres. Pour chacune des  2n combinaisons de [état(n) + lecture(2)], il y a  2\times2\times(n+1) choix de [direction(2) + écriture(2) + état(n+1)]. Inutile de dire que  TM(n) grandit vite.

Voici un tableau qui récapitule le nombre de TS à tester pour chaque nombre d’état et le temps qu’il a fallu pour calculer tout ça :

n  TM(n) Temps (s)
1 64 0.007
2 20736 0.66
3 1.7×107 537 (9 min)
4 2.6×1010 1036800 (288 h)

J’ai tracé le temps de calcul en fonction du nombre de TM à tester, en log-log.

BBgraph1

Ça à l’air suspicieusement linéaire, mais avec si peu de points, je ne m’avancerai pas. Juste pour être sûr, j’ai aussi tracé le ratio  \frac{\text{Temps de calcul}}{TM(n)}  en fonction de  TM(n) :

BBgraph2

C’est moche.

Je suis déçu de ne pas avoir plus de points, mais pour  n=5 , non seulement il faudra tester  63403380965376=6.3\times10^{13} machines, mais je ne saurais pas quand les arréter, puisque  S(5,2) n’est pas connu. Je soupçonne fortement que le temps de calcul passerait de toutes façons de interminable à stupidement long.

Par défaut
math

L’ami Robert

Imaginez un crabe. Il s’appelle Robert. C’est un crabe comme on en trouve sous n’importe quel rocher. Mais Robert a un problème : il ne sait pas tourner. Il ne peut faire que des pas de côté. Et il s’ennuie. Comme tous les gens qui s’ennuient, il décide donc de faire un petit jeu mathématique : toutes les secondes, il lance une pièce. Si c’est pile il fait un pas à droite, si c’est face il fait un pas à gauche. À votre avis, combien de temps met-il (en moyenne) pour revenir à son point de départ ?

Il est assez facile d’écrire un programme de 38 lignes qui simule Robert faisant des pas vers la gauche ou vers la droite et calculer la durée moyenne entre deux passages par le point de départ. J’ai essayé et la moyenne ne converge apparemment pas, mais semble augmenter avec le temps de simulation, ce qui n’est pas rassurant. Il reste donc a trouver un moyen de formaliser tout ça pour être sûr.

Commençons par nous intéresser à toutes les trajectoires que Robert peut parcourir en n  secondes.

n=2  :

dd dg
gg gd

Les deux trajectoires rouges sont celles qui ramènent Robert à son point de départ. Il y en a deux, sur quatre trajectoires possibles, soit   \frac{2}{4}=\frac{1}{2}  .

n=4  :

dddd dddg ddgd ddgg
dgdd dgdg dggd dggg
gddd gddg gdgd gdgg
ggdd ggdg gggd gggg

Ah ! On dirait qu’il se passe des trucs. Pour commencer, les trajectoires qui commencent par gd ou dg sont « impossibles » : elles sont déjà passées une fois au point de départ ( pour n=2  ) et peuvent être ignorées. Parmi les huit qui restent, seules deux ramènent Robert à sont point de départ, soit  \frac{2}{8}=\frac{1}{4}  .

n=6  :

dddddd dddddg ddddgd ddddgg 
dddgdd dddgdg dddggd dddggg
ddgddd ddgddg ddgdgd ddgdgg 
ddggdd ddggdg ddgggd ddgggg
dgdddd dgdddg dgddgd dgddgg
dgdgdd dgdgdg dgdggd dgdggg
dggddd dggddg dggdgd dggdgg
dgggdd dgggdg dggggd dggggg
gddddd gddddg gdddgd gdddgg
gddgdd gddgdg gddggd gddggg
gdgddd gdgddg gdgdgd gdgdgg
gdggdd gdggdg gdgggd gdgggg
ggdddd ggdddg ggddgd ggddgg
ggdgdd ggdgdg ggdggd ggdggg
gggddd gggddg gggdgd gggdgg
ggggdd ggggdg gggggd gggggg

Ça devient long à taper, ces bêtises. Cette fois, il y a encore plus de trajectoires qui sont déjà repassées par la case départ pour n=2 ou n=4  . Parmi les vingt-quatre qui restent, quatre ramènent Robert à son point de départ, soit  \frac{4}{24}=\frac{1}{6}  .

Vous remarquez un pattern ? Moi aussi : la proportion des trajectoires qui s’arrêtent après n secondes parmi celles qui ne se sont pas encore arrêtées vaut \frac{1}{n} . J’ai vérifié jusqu’à n=20  et ça a l’air de tenir :

  n     valides  finales    proportion
  2         4        2     1/2  =    2/4      
  4         8        2     1/4  =    2/8      
  6        24        4     1/6  =    4/24     
  8        80       10     1/8  =   10/80     
 10       280       28     1/10 =   28/280    
 12      1008       84     1/12 =   84/1008   
 14      3696      264     1/14 =  264/3689   
 16     13728      858     1/16 =  858/13728  
 18     51480     2860     1/18 = 2860/51480  
 20    194480     9724     1/20 = 9724/194480 

Avec dans la colonne ‘valides’ le nombre de trajectoires qui ne sont pas encore passées par le point de départ après n -1  secondes et ‘finales’ le nombre de trajectoires qui sont au point de départ après n secondes. Par contre, je n’ai aucune idée comment ces proportions valent toujours \frac{1}{n}  , donc si vous avez une illumination, n’hésitez pas à me le dire.

On avance : on veut savoir quelle proportion des trajectoires reviennent au point de départ en exactement n secondes. Mais on a seulement cette proportion parmi les trajectoires qui ne sont jamais repassées par le point de départ durant les n-1 secondes précédentes. Pas de problème ! Si on prend  U_n la proportion des trajectoires qui ne sont jamais repassées par le départ après n  secondes, alors :

U_2=\frac{1}{2}

U_{n+2} = U_n \times \left (1-\frac{1}{n} \right )

Toutes les deux secondes, \frac{1}{n} des trajectoires restantes reviennent au point de départ. Wolfram a la gentillesse de trouver une relation directe pour U_n :

U_n = \frac{ \left ( n-2 \right ) ! }{ 2^{n-1} \: ( \frac{n-2}{2} ! )^2 }

Donc ! Après n -1  secondes, il y a U_n des trajectoires qui ne sont jamais repassées par le point de départ. Après exactement n secondes, Robert est revenu à son point de départ pour la première fois dans \frac{U_n}{n} des trajectoires. Donc pour avoir le temps moyen T que Robert met pour revenir au point de départ, il suffit de sommer pour tous les n pairs la proportion \frac{U_n}{n} fois le temps écoulé n .

T = \sum_{ \substack{ n=2, \\ n \: \text{pair}} }^{+\infty} \frac{U_n}{n} \times n = \sum_{ \substack{ n=2, \\ n \: \text{pair}} }^{+\infty} U_n

Voilà qui est suspicieusement sympathique, surtout que Wolfram nous dit (avec n=2k ) :

\begin{equation*} \begin{split} T_n & = \sum_{ \substack{ n=2, \\ n \: \text{pair}} }^{n} U_n = \sum_{k=1}^{\frac{n}{2}} U_{2k} \\[0ex] T_n & = \sum_{k=1}^{\frac{n}{2}} \frac{ \left ( 2k-2 \right ) ! }{ 2^{2k-1} \: ((k-1) ! )^2 } \\[1ex] T_n & = \frac{n \, n!}{2^{n+1}(\frac{n}{2}!)^2} \end{split} \end{equation*}

Où T_n est le temps moyen entre deux passages par le point de départ après n secondes. Et enfin si on suppose n grand, on peut utiliser la Formule de Stirling : n! \sim \, \sqrt{2\pi n} \, \left ( \frac{n}{e} \right )^n qui donne :

\begin{equation*} \begin{split} T_n & \sim \frac{n \sqrt{2 \pi n} \left ( \frac{n}{e} \right )^n}{2^{n+1} ( \sqrt{\pi n} ( \frac{n}{2e} )^{\! \frac{n}{2}} )^2} \\[0ex] T_n & \sim \frac{ \sqrt{2 n} \left ( \frac{n}{e} \right )^n}{2^{n+1} \: \sqrt{\pi} \ ( \frac{n}{e} )^n \ 2^{-n}} \\[1ex] T_n & \sim \frac{ \sqrt{n} }{\sqrt{2 \pi}} \ \xrightarrow[\: n \to +\infty \:]{ } \: + \infty \end{split} \end{equation*}

Donc le temps moyen entre deux passages par le point de départ diverge effectivement. C’est dommage, mais pas inattendu. En fin de compte, après n secondes, on peut s’attendre à ce que Robert soit repassé environ \frac{n}{\sqrt{n} / \sqrt{2 \pi}}=\sqrt{2 \pi n} fois par le point de départ. Mais en moyenne, plus le temps passe, plus Robert s’éloigne vers l’infini et au-delà.

la nébuleuse du crabe

Par défaut
math

ln is weird

L’autre jour, j’ai remarqué un truc bizarre à propos du logarithme.

On sait que la primitive de x^{-n} , c’est :

lnisweird001

Que l’on peut réécrire pour n<1  :

lnisweird003

et pour n>1 :

lnisweird004

Évidemment, quand n=1 , cette solution n’est plus valable, et à la place on a :

lnisweird005

Le tout résumé sur ce joli graphique pour vos yeux ébahis, avec n=.2 , n=1 et n=4 .

ébahissement en cours

Les lignes pointillées sont les primitives des lignes pleines.

D’accord, donc le logarithme est juste entre les primitives de la forme \sqrt[k]{x} et celles de la forme x^{-k} . Ce qui n’est d’ailleurs pas du tout surprenant :

lnisweird006
lnisweird007
lnisweird008a
lnisweird008b
lnisweird009

C’est à dire que quelque soit n, la primitive de x^{-n} est toujours soit au dessus soit en dessous de ln(x) . Mais ça ne veut pas dire que ces primitives tendent gentiment vers le logarithme quand n tends vers 1 , au contraire elles divergent :

Quand n tends vers 1 , les deux primitives explosent. Mais quand n=1 , la primitive est bien définie, et c’est le logarithme :

Donc on a une fonction qui diverge en un point, mais qui y est aussi définie. Vive le logarithme !

Par défaut