2020/05/15 by Gu, Yuzhou, Roozbehani, Hajir, Polyanskiy, Yury
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2005.07801
We revisit the problem of broadcasting on d-ary trees: starting from a Bernoulli(1/2) random variable X0 at a root vertex, each vertex forwards its value across binary symmetric channels BSCδ to d descendants. The goal is to reconstruct X0 given the vector XLh of values of all variables at depth h. It is well known that reconstruction (better than a random guess) is possible as h→ ∞ if and only if δ< δc(d). In this paper, we study the behavior of the mutual information and the probability of error when δ is slightly subcritical. The innovation of our work is application of the recently introduced "less-noisy" channel comparison techniques. For example, we are able to derive the positive part of the phase transition (reconstructability when δ