{"id":"arxiv/2603.28936","url":"https://arxiv.org/abs/2603.28936","tags":["math.PR","cs.DS","math.CO","math.NT","math.ST"],"score":0,"title":"Composition of random functions and word reconstruction","domain":"math.PR","source":"arxiv","authors":["Guillaume Chapuy","Guillem Perarnau"],"reviews":0,"subject":"math.PR","summary":"Given two functions $\\mathbf{a}\\!:\\! [n] \\rightarrow [n]$ and $\\mathbf{b}\\!:\\! [n] \\rightarrow [n]$ chosen uniformly at random, any word $w=w_1w_2\\dots w_k\\in \\{a,b\\}^k$ induces a random function $\\mathbf{w}\\!:\\! [n] \\rightarrow [n]$ by composition, i.e. $\\mathbf{w}=φ_{w_k}\\circ \\dots \\circ φ_{w_1}$ with $φ_a=\\mathbf{a}$ and $φ_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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-30","reactions":{}}