Broadcasting on trees near criticality
share
We revisit the problem of broadcasting on d-ary trees: starting from a Bernoulli(1/2) random variable X_0 at a root vertex, each vertex forwards its value across binary symmetric channels BSC_δ to d descendants. The goal is to reconstruct X_0 given the vector X_L_h 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 δ<δ_c) using purely information-theoretic ideas. This is in contrast with previous derivations, which explicitly analyze distribution of the Hamming weight of X_L_h (a so-called Kesten-Stigum bound).
READ FULL TEXT