Rauzy complexity and block entropy

Authors: Verónica Becher; Olivier Carton; Santiago Figueira.

Abstract:
In 1976, Rauzy studied two complexity functions, β and β, for infinite sequences over a finite alphabet. The function β achieves its maximum precisely for Borel normal sequences,
while β reaches its minimum for sequences that, when added to any Borel normal sequence, result in another Borel normal sequence. We establish a connection between Rauzy’s complexity functions, β and β, and the notions of non-aligned block entropy, h and h, by providing sharp upper and lower bounds for h in terms of β, and sharp upper and lower bounds for h in terms of β. We adopt a probabilistic approach by considering an infinite sequence of random variables over a finite alphabet. The proof relies on a new characterization of non-aligned
block entropies, h and h, in terms of Shannon’s conditional entropy. The bounds imply that sequences with h = 0 coincide with those for which β = 0. We also show that the non-aligned block entropies, h and h, are essentially subadditive.

More information:
https://arxiv.org/html/2406.18383v2