Abstract:The broadcasting problem on trees concerns the transmission of binary information along the edges of a tree. In the formulation studied here, each vertex carries one of two colours, and along every edge the colour is transmitted with error probability $q$. The central question is whether the root colour can be reconstructed from the observed colours of all vertices in the tree, but crucially, without knowing which vertex is the root. We study the problem of reconstructing the root colour in a broadcasting process on random trees, focusing on the majority rule estimator. We introduce a novel and adaptable martingale approach for analysing the colour imbalance. This method provides a simpler and more powerful alternative to existing techniques. Our martingale approach unifies the analysis of the different tree models and leads to linear upper bounds for the error probability of the majority rule estimator in each case. This shows that, for a broad class of random tree models, the error probability of the majority rule admits a linear upper bound in $q$.
From: Vitali Wachtel [view email]
[v1]
Mon, 22 Jun 2026 07:39:12 UTC (12 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。