Suite d'Ehrenfeucht-Mycielski

Un article de Wikipédia, l'encyclopédie libre.
Page d’aide sur l’homonymie

Pour les articles homonymes, voir Mycielski.

La suite d'Ehrenfeucht-Mycielski (en anglais « Ehrenfeucht-Mycielski sequence » est une suite binaire qui a des propriétés qui ressemblent à celles de suites pseudo-aléatoires. Elle a été définie par Andrzej Ehrenfeucht et Jan Mycielski en 1992[1].

Définition[modifier | modifier le code]

La suite commence avec le bit 0 ; chaque bit est calculé en fonction des bits précédents : on cherche le plus long suffixe qui apparaît déjà une autre fois dans la suite, et on ajoute le bit qui ne suit pas cette autre occurrence (s'il y a plusieurs occurrences, on prend la dernière).

Par exemple, pour la suite

01001101011100010000111

le plus long suffixe qui apparaît déjà une autre fois dans ce mot est 0111 puisque l'on a :

01001101011100010000111

Son occurrence autre que la dernière est suivie de 0, donc la suite continue par 1 et devient

010011010111000100001111

Construction de la suite[modifier | modifier le code]

Le principe décrit ci-dessus donne successivement les bits suivant :

  1. 0 : bit initial ; le mot vide est le suffixe qui apparaît déjà, il est suivi de 0 donc on ajoute 1
  2. 01 : à nouveau, seul le mot vide apparaît déjà, sa dernière occurrence est suivie de 1 donc on ajoute 0
  3. 010 : le suffixe 0 apparaît suivi de 1, donc on ajoute 0
  4. 0100 : le suffixe 0 apparaît deux fois, la dernière fois suivi de 0, donc on ajoute 1
  5. 01001 : le suffixe 01 apparaît suivi de 0, donc on ajoute 1
  6. 010011 : le suffixe 1 apparaît deux fois, la dernière fois suivi de 1, donc on ajoute 0
  7. 0100110 : etc.

Les premiers termes de la suite sont :

0100110101110001000011110110010100100111010001100...

C'est la suite A038219 de l'OEIS. Une variante de la suite est obtenue en remplaçant (0,1) par (1,2) : c'est la suite A007061 de l'OEIS :

121122121222111211112222...

On a aussi calculé la suite de plages formée par des symboles identiques consécutifs (suite des runs du run-length encoding, c'est la suite A201881 de l'OEIS :

11221113314412211...

Algorithme[modifier | modifier le code]

L'algorithme naïf calcule un bit de la suite en comparant chaque suffixe à la séquence tout entière. Il prend un temps en O(n3) pour engendrer les n premiers termes. De fait, une structure de donnée similaire à un arbre des suffixes permet d'engendrer la suite en temps constant par bit engendré[2].

Universalité[modifier | modifier le code]

La suite d'Ehrenfeucht-Mycielski est une suite univers ; elle a la propriété que toute suite finie de bits y apparaît comme facteur une infinité de fois[3]. Une telle suite est parfois appelée disjonctive. De manière équivalente, le nombre 0.01001101... dont la suite est le développement en base 2 est un nombre univers. Il a été calculé[2] que tout facteur de longueur i apparaît au moins j fois dans le préfixe de longueur A(4i,j) de la suite, où A est la fonction d'Ackermann, mais des observations expérimentales suggèrent une borne bien meilleure : la longueur d'un préfixe contenant tous les mots de longueur i en facteur semble être proche de la plus petite valeur possible, à savoir 2i + i, celle des suites de de Bruijn[4].

Normalité[modifier | modifier le code]

Ehrenfeucht et Mycielski[1] conjecturent que le nombre de bits égaux à 0 et à 1 bits est équilibré, et converge vers une densité limite de 1/2. Plus précisément, si f(i) est le nombre de bits égaux à 0 parmi les i premiers bits de la suite d'Ehrenfeucht–Mycielski, on devrait avoir :

.

Une hypothèse formulée par Irving John Good et mentionnée en appendice dans la note d'Ehrenfeucht et Mycielski précise cette conjecture : la vitesse de convergence de cette limite doit être nettement plus rapide que celle d'une suite aléatoire, pour laquelle la loi du logarithme itéré donne[1]

.

La conjecture d'équilibre d'Ehrenfeucht et Mycielski est un premier pas vers une affirmation plus forte, à savoir que le nombre univers 0.01001101... dont la suite est le développement binaire est un nombre normal en base 2. Cette conjecture est encore ouverte en 2009[2]; toutefois, on sait[5] que tout point limite de la suite des f(i)/i est dans l'intervalle [1/4,3/4].

Notes et références[modifier | modifier le code]

Notes
  1. ↑ a b et c Ehrenfeucht et Mycielski 1992.
  2. ↑ a b et c Herman et Soltys 2009
  3. ↑ Ehrenfeucht et Mycielski 1992
  4. ↑ Sutner 2003
  5. ↑ Kieffer et Szpankowski 2007
Références
  • Andrzej Ehrenfeucht et Jan Mycielski, « A pseudorandom sequence: how random is it? », American Mathematical Monthly, vol. 99,‎ , p. 373–375 (DOI 10.2307/2324917, JSTOR 2324917).
  • Grzegorz Herman et Michael Soltys, « On the Ehrenfeucht–Mycielski sequence », Journal of Discrete Algorithms, vol. 7, no 4,‎ , p. 500–508 (DOI 10.1016/j.jda.2009.01.002, lire en ligne).
  • John C. Kieffer et Wojciech Szpankowski, « On the Ehrenfeucht–Mycielski balance conjecture », Proc. Conf. Analysis of Algorithms (AofA 2007),‎ , p. 19–28 (lire en ligne).
  • Klaus Sutner, « The Ehrenfeucht–Mycielski sequence », dans O. H. Ibarra et Z. Dang (éditeurs), Proc. Conf. Implementation and Application of Automata (CIAA 2003), Springer-Verlag, coll. « Lecture Notes in Computer Science Volume 2759 », (DOI 10.1007/3-540-45089-0_26, lire en ligne), p. 73–82.
  • Terry R. McConnell, The Ehrenfeucht-Mycielski Sequence. — Contient notamment une table d'un million de termes de la suite d'Ehrenfeucht–Mycielski]
  • Terry R. McConnell, « DeBruijn Strings, Double Helices, and the Ehrenfeucht-Mycielski Mechanism », NN,‎ (arXiv 1303.6820v2)

Articles liés[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Suite_d%27Ehrenfeucht-Mycielski&oldid=186580012 ».