• 1 Research Center for Information Security

[en]
In this article, we investigate the asymptotic occurrence rates of specific subwords in any infinite binary word. We prove that the asymptotic occurrence rate for the subwords is upper- and lower-bounded in the same way for every infinite binary word, in terms of the asymptotic occurrence rate of the zeros. We also show that both of the bounds are best-possible by constructing, for each bound, a concrete infinite binary word such that the bound is reached. Moreover, we apply the result to analyses of recently-proposed pseudorandom number generators that are based on integer-valued variants of logistic maps.

[fr]
Dans cet article, nous étudions les fréquences asymptotiques d’occurrence de suites spécifiques dans tout mot binaire infini. Nous prouvons que la fréquence asymptotique d’occurrence pour ces suites est borné supérieurement et inférieurement de la même façon pour chaque mot binaire infini, en termes des fréquences asymptotiques d’occurrence de zéros. Nous montrons aussi que les deux limites sont les meilleures possibles en construisant concrètement, pour chaque limite, un mot binaire infini tel que la borne est atteinte à la limite. De plus, nous appliquons ce résultat à des analyses de générateurs de nombres pseudo-aléatoires proposés récemment qui sont basés sur des variantes des fonctions logistiques à valeurs entières.