Robust Reconstruction on Trees with a Growing Alphabet

Source abstract

We study robust reconstruction for the $q$-state Potts broadcast process on a Galton-Watson tree in the growing-alphabet regime $q\to\infty$, with boundary depth growing sufficiently quickly in relation to $q$. We show that, in the regime $dλ>1$, where $d$ is the expected number of offspring and $λ$ is the nontrivial eigenvalue of the Potts transition matrix, the root posterior is asymptotically unchanged by a broad class of noise channels applied independently to the boundary labels. This remains true even when the probability of retaining the true label at an individual boundary vertex tends to zero as $q\to\infty$. More precisely, under suitable moment and noise assumptions, the noiseless and noisy root posteriors converge to one another in expected total variation, and hence have the same asymptotic Bayes-optimal reconstruction accuracy.