A Random Walk Approach to Broadcasting on Random Recursive Trees

Abstract In the broadcasting problem on trees, a $$\{-1,1\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> -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.