Composition of random functions and word reconstruction

Guillaume Chapuy, Guillem Perarnau

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…