A Random Walk Approach to Broadcasting on Random Recursive Trees

Ernst Althaus, Lisa Hartung, Rebecca Steiner

In the broadcasting problem on trees, a $\{-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…