Composition of random functions and word reconstruction

Abstract

Given two functions $\mathbf{a}:[n]\to [n]$ and $\mathbf{b}:[n]\to [n]$ chosen uniformly at random, any word $w=w_1{w}_2\dots w_k\in \{a,b{\}}^k$ induces a random function $\mathbf{w}:[n]\to [n]$ by composition, i.e. $\mathbf{w}=\ddot{I}{•}_{w_k}\circ \cdots \circ \ddot{I}{•}_{w_1}$ with $\ddot{I}{•}_a=\mathbf{a}$ and $\ddot{I}{•}_b=\mathbf{b}$. We study the following question: assuming $w$ is fixed but unknown, and $n$ goes to infinity, does the random function $\mathbf{w}$ carry enough information to (partially) recover the word $w$ with good enough probability, in one or several i.i.d. samples? We prove that the random functions stemming from two non-isomorphic words can be discriminated with probability arbitrarily close to $1$ with a bounded number of samples, when $n$ goes to infinity. Equivalently, the total variation distance between their distributions is bounded away from zero. The proof relies on the study of certain auto-correlation functions appearing in the variance of the weighted number of quasi-leaves. Whether the total variation distance goes to 1, or equivalently, whether one sample is enough to distinguish the words with high probability, is the major question we leave open. We show that this is the case when the two words have different lengths or different exponents.

v2: we now prove separation in TV-distance for non-isomorphic words unconditionally, without the Schanuel conjecture. To do this, we change our main observable from a leaf count to a weighted quasi-leaf count, with an extra real parameter u (after a suggestion of Andrea Sportiello). Only local modifications are needed and the structure of the paper and the techniques are essentially unchanged