Information Reconstruction on an Infinite Tree for a 4×4-State Asymmetric Model with Community Effects.

The reconstruction problem on an infinite tree, is to collect and analyze massive data samples at the nth level of the tree to identify whether there is non-vanishing information of the root, as n goes to infinity. This problem has wide applications in various fields such as biology, information theory, and statistical physics. Although it has been studied in numerous contexts, the existing literature with rigorous reconstruction thresholds established are very limited. In this paper, we study the noise channel in terms of a 4 × 4 -state asymmetric transition matrix with community effects. By means of refined analyses of moment recursion, in-depth concentration estimates, and thorough investigations on an asymptotic 4-dimensional nonlinear second order dynamical system, we give the first rigorous result on asymmetric noisy channels with community effects by providing the exact conditions that the reconstruction bound is not tight, which yields the hybrid-hard phase in corresponding stochastic block models. [ABSTRACT FROM AUTHOR]