Independence of normal numbers

BECHER, VERÓNICA

Marsella

Conferencia; Conference on Computability, Randomness and Applications; 2016

Centre International de Rencontres Mathématiques

dependence of normal wordsVerónica BecherUniversidad de Buenos Aires & CONICETRecall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency.We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has Lebesgue measure 1.We prove that not only the join of two normal words is normal, but, more generally, the shuffling with a finite transducer of two normal independent words is also a normal word. The converse of this theorem fails: we construct a normal word as the join of two normal words that are not independent. Our constructed word is such that the symbol at position n is equal to the symbol at position 2n, for every n. Thus, the constructed word, call it x, is the join of x itself and the subsequence of odd positions of x. This result is interesting per se.We also show that selection by finite automata acting on pairs of independent words preserves normality. This is a counterpart version of Agafonov's theorem for finite automata with two input tapes.This is joint work with Olivier Carton (Université Paris Diderot) and Pablo Ariel Heiber (Universidad de Buenos Aires).