Broadcasting on Trees Near Criticality: Perturbation Theory
Qian Yu, Yury Polyanskiy · 2021
Consider a setting where a single bit is broadcast down the d-ary tree, where each edge acts as a binary symmetric channel with a crossover probability δ. The goal is to reconstruct the root bit given the values of all bits at a large distance$h$from the root. It is known the reconstruction is impossible iff (1 - 2δ)2d ≤ 1. In this paper, we show that in the regime where the latter product converges to 1 from the above, the distribution of the log-likelihood ratio (LLR) of the root bit given the far-away boundary (normalized by the square root of deviation of δ from criticality) converges to an explicit Gaussian distribution. This strengthens a similar result of Jain-Koehler-Liu-Mossel (COLT'2019) and enables us to resolve conjectures stated in Gu-Roozbehani-Polyanskiy (ISIT'2020) for the scaling of the probability of error and mutual information near criticality. Our results also provide a rationale for the ubiquitous$N$(µ, 2µ) approximation of the LLR distribution in the EXIT-chart heuristics.