Paper detail

Broadcasting on trees near criticality

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 $\mathrm{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\to \infty$ 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 &#34;less-noisy&#34; 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).