A Random Walk Approach to Broadcasting on Random Recursive Trees
Abstract
Abstract In the broadcasting problem on trees, a $$\{-1,1\}$$ { - 1 , 1 } -message originating in an unknown node is passed along the tree with a certain error probability q . The goal is to estimate the original message without knowing the order in which the nodes were informed. We show a connection to random walks with memory effects and use this to develop a novel approach to analyze the majority estimator on random recursive trees. With this powerful approach, and a Pólya urn representation, we study the entire group of very simple increasing trees as well as shape exchangeable trees together. This also extends Addario-Berry et al. [8] who investigated this estimator for uniform and linear preferential attachment random recursive trees.
Fields of Study & Subjects
Algorithms and Data Compression
Stochastic processes and statistical mechanics
Cellular Automata and Applications
Publication details
- Journal / source
- Journal of Theoretical Probability
- Publisher
- Springer Science and Business Media LLC
- Volume
- 39
- Issue
- 3
- Publication date
- 30 June 2026
- Language
- EN