论文标题
在临界的树木上广播
Broadcasting on trees near criticality
论文作者
论文摘要
我们重新审查了在$ d $ -ary树上广播的问题：从bernoulli $（1/2）$随机变量$ x_0 $在root dertex上，每个顶点都在二进制对称频道上转发其价值，跨二进制对称性频道$ \ mathrm {bsc}_Δ$ to $ d $ d $ descendants。目标是重建$ x_0 $给定的vector $ x_ {l_h} $，在depth $ h $上的所有变量的值。众所周知，重建（比随机猜测更好）在$ h \ to \ infty $时，仅当$Δ<δ_c（d）$时。在本文中，我们研究了相互信息的行为以及$δ$略微临界时的误差概率。我们工作的创新是最近引入的“不太努力”渠道比较技术的应用。例如，我们能够使用纯粹的信息理论思想得出相变（$Δ<δ_c$）的正面部分（重建性）。这与先前的派生相反，后者明确分析了$ x_ {l_h} $（所谓的kesten-stigum绑定）的锤子重量的分布。
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 "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).
