| Paper ID | D5-S2-T3.1 |
| Paper Title |
Broadcasting on Trees Near Criticality: Perturbation Theory |
| Authors |
Qian Yu, University of Southern California, United States; Yury Polyanskiy, MIT, United States |
| Session |
D5-S2-T3: Reconstruction on Graphs |
| Chaired Session: |
Friday, 16 July, 22:20 - 22:40 |
| Engagement Session: |
Friday, 16 July, 22:40 - 23:00 |
| Abstract |
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 $\delta$. 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\delta)^2 d \le 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 $\delta$ 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 $\mathcal{N}(\mu,2\mu)$ approximation of the LLR distribution in the EXIT-chart heuristics.
|
