A Random Walk Approach to Broadcasting on Random Recursive Trees

Link to Join MS Teams Talk

This talk will be broadcast at 13:30 BST / 14:30 CEST / 15:30 EEST, June 25th, 2025 on MS Teams only.

Meeting ID: 393 527 089 878
Passcode: dsm7py

Abstract

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 original message without knowing the order in which the nodes received the information. When using majority estimation, we establish connections to both Pólya urns and random walks with memory effects. We apply these approaches to study the error probability of the majority estimator and to identify an infeasibility regime on the entire group of very simple increasing trees as well as shape exchangeable trees, including majority estimation based solely on the leaf values. This extends the work of Addario-Berry et al. (2022), who investigated this estimator for uniform and linear preferential attachment random recursive trees.

About Rebecca

Rebecca is currently a third-year PhD student at the University of Mainz under the supervision of Lisa Hartung and Ernst Althaus, working on stochastic processes and interacting particle systems. In particular, she studies how self-reinforcing effects can influence the large-scale behavior of random systems.