Broadcasting in random recursive dags

¹ Department of Mathematics, Unidistance Suisse, 3900, Brigue, Switzerland.
² School of Computer Science McGill University Montreal, Canada.
³ Department of Economics and Business, Barcelona School of Economics, Pompeu Fabra University, ICREA, Pg. Lluís Companys 23, 08010 Barcelona, Spain.

^* Corresponding author: gabor.lugosi@gmail.com

Received: 24 February 2024
Accepted: 3 February 2025

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).