Given two functions a:[n]→[n] and b:[n]→[n] chosen uniformly at random, any word w of length k on {a,b} induces a random function w:[n]→[n] by composition. We study the following question: assuming w is fixed but unknown, and n goes to infinity, does the random function w carry enough information to (partially) recover the word w with good enough probability, in one or several i.i.d. samples?
We show that this is possible with a finite number of samples w.h.p., but leave open the question of knowing if one can do it in one sample.
At the technical level, most of the work deals with studying number of leaves in certain "self-overlapping" random trees, and with certain transcendence properties of towers of exponential functions, related to the Schanuel conjecture from number theory.
This is joint work with Guillem Perarnau