A Random Walk Approach to Broadcasting on Random Recursive Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914032197304320 |
|---|---|
| author | Althaus, Ernst Hartung, Lisa Steiner, Rebecca |
| author_facet | Althaus, Ernst Hartung, Lisa Steiner, Rebecca |
| contents | 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 were informed. We show a connection to random walks with memory effects and use this to develop a novel approach to analyse the majority estimator on random recursive trees. With this powerful approach, we study the entire group of very simple increasing trees as well as shape exchangeable trees together. This also extends Addario-Berry et al. (2022) who investigated this estimator for uniform and linear preferential attachment random recursive trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04385 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Random Walk Approach to Broadcasting on Random Recursive Trees Althaus, Ernst Hartung, Lisa Steiner, Rebecca Probability Discrete Mathematics 60C05, 82C41, 05C80 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 were informed. We show a connection to random walks with memory effects and use this to develop a novel approach to analyse the majority estimator on random recursive trees. With this powerful approach, we study the entire group of very simple increasing trees as well as shape exchangeable trees together. This also extends Addario-Berry et al. (2022) who investigated this estimator for uniform and linear preferential attachment random recursive trees. |
| title | A Random Walk Approach to Broadcasting on Random Recursive Trees |
| topic | Probability Discrete Mathematics 60C05, 82C41, 05C80 |
| url | https://arxiv.org/abs/2405.04385 |