Broadcasting in random recursive dags
- Briend, Simon ORCID UniDistance Suisse
- Devroye, Luc
- Lugosi, Gábor
-
2025
Published in:
- ESAIM: Probability and Statistics. - 2025
English
A uniform k -DAG generalizes the uniform random recursive tree by picking k parents uniformly at random from the existing nodes. It starts with k “roots”. Each of the k roots is assigned a bit. These bits are propagated by a noisy channel. The parents’ bits are flipped with probability p , and a majority vote is taken. When all nodes have received their bits, the k -DAG is shown without identifying the roots. The goal is to estimate the majority bit among the roots. We identify the threshold for p as a function of k below which the majority rule among all nodes yields an error c + o (1) with c < 1/2. Above the threshold the majority rule errs with probability 1/2 + o (1).
- Identifiers
-
- DOI 10.1051/ps/2025002
- URI https://pub.orcid.org/v3.0/0009-0009-8655-0532/work/183091430
- ARK ark:/51647/srd1336045
- Persistent URL
- https://n2t.net/ark:/51647/srd1336045
Statistics
Document views: 5
File downloads:
- Broadcasting-in-random-recursive-dags.pdf: 5