论文标题
在随机递归树上广播
Broadcasting on random recursive trees
论文作者
论文摘要
当基础树是一棵随机的递归树时，我们研究广播问题。树的根有一个随机的位值分配。每个其他顶点的位值与概率$ 1-q $的父值相同，而概率$ q $的相反值，其中$ q \ in [0,1] $。广播问题包括在观察未标记的树时估计根位的值，以及与每个顶点相关的位值。在问题的更困难的版本中，观察到未标记的树，但只观察到叶子的位值。当底层树是统一的随机递归树时，在问题的两个变体中，我们都表征了$ q $的值，最佳重建方法的差异可能是符合$ 1/2 $的误差概率。我们还表明，错误的可能性是由恒定时间$ q $界定的。详细分析了两个简单的重建规则。其中一个是简单的多数投票，另一个是树的质心的位价值。大多数结果也扩展到线性优先附件树。
We study the broadcasting problem when the underlying tree is a random recursive tree. The root of the tree has a random bit value assigned. Every other vertex has the same bit value as its parent with probability $1-q$ and the opposite value with probability $q$, where $q \in [0,1]$. The broadcasting problem consists in estimating the value of the root bit upon observing the unlabeled tree, together with the bit value associated with every vertex. In a more difficult version of the problem, the unlabeled tree is observed but only the bit values of the leaves are observed. When the underlying tree is a uniform random recursive tree, in both variants of the problem we characterize the values of $q$ for which the optimal reconstruction method has a probability of error bounded away from $1/2$. We also show that the probability of error is bounded by a constant times $q$. Two simple reconstruction rules are analyzed in detail. One of them is the simple majority vote, the other is the bit value of the centroid of the tree. Most results are extended to linear preferential attachment trees as well.
