Broadcasting in random recursive dags

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Briend, Simon
• dc.contributor.author Devroye, Luc
• dc.contributor.author Lugosi, Gábor
• dc.date.accessioned 2025-06-17T16:07:48Z
• dc.date.available 2025-06-17T16:07:48Z
• dc.date.issued 2025
• dc.date.updated 2025-06-17T16:07:47Z
• dc.description.abstract 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).
• dc.description.sponsorship Simon Briend acknowledges the support of Région Ile de France. Gábor Lugosi acknowledges the support of Ayudas Fundación BBVA a Proyectos de Investigación Científica 2021 and the Spanish Ministry of Economy and Competitiveness grant PID2022-138268NB-I00, financed by MCIN/AEI/10.13039/501100011033, FSE+MTM2015-67304-P, and FEDER, EU.
• dc.format.mimetype application/pdf
• dc.identifier.citation Briend S, Devroye L, Lugosi G. Broadcasting in random recursive dags. ESAIM Probab Stat. 2025;29:184-203. DOI: 10.1051/ps/2025002
• dc.identifier.doi http://dx.doi.org/10.1051/ps/2025002
• dc.identifier.issn 1292-8100
• dc.identifier.uri http://hdl.handle.net/10230/70708
• dc.language.iso eng
• dc.publisher EDP Sciences
• dc.relation.ispartof ESAIM: probability and statistics. 2025;29:184-203
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PID2022-138268NB-I00
• dc.rights This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri http://creativecommons.org/licenses/by/4.0/
• dc.subject.keyword Broadcasting problema
• dc.subject.keyword Random recursive dags
• dc.subject.keyword Network archaeology
• dc.title Broadcasting in random recursive dags
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion