Briend, Simon Devroye, Luc Lugosi, Gábor 2025 <jats:p>A uniform <jats:italic>k</jats:italic>-DAG generalizes the uniform random recursive tree by picking <jats:italic>k</jats:italic> parents uniformly at random from the existing nodes. It starts with <jats:italic>k</jats:italic> “roots”. Each of the <jats:italic>k</jats:italic> roots is assigned a bit. These bits are propagated by a noisy channel. The parents’ bits are flipped with probability <jats:italic>p</jats:italic>, and a majority vote is taken. When all nodes have received their bits, the <jats:italic>k</jats:italic>-DAG is shown without identifying the roots. The goal is to estimate the majority bit among the roots. We identify the threshold for <jats:italic>p</jats:italic> as a function of <jats:italic>k</jats:italic> below which the majority rule among all nodes yields an error <jats:italic>c</jats:italic> + <jats:italic>o</jats:italic>(1) with <jats:italic>c</jats:italic> &lt; 1/2. Above the threshold the majority rule errs with probability 1/2 + <jats:italic>o</jats:italic>(1).</jats:p> application/pdf https://n2t.net/ark:/51647/srd1336045 https://sonar.unidistance.ch/global/documents/336045 https://sonar.unidistance.ch/documents/336045/files/Broadcasting-in-random-recursive-dags.pdf info:eu-repo/semantics/altIdentifier/doi/10.1051/ps/2025002 info:eu-repo/semantics/altIdentifier/ark/51647/srd1336045 info:eu-repo/semantics/openAccess ESAIM: Probability and Statistics. - 2025 Broadcasting in random recursive dags http://purl.org/coar/resource_type/c_6501