Broadcasting on random recursive trees

DOI10.1214/21-AAP1686MaRDI QIDQ2117452zbMATH OpenOpenAlexFDO

Authors Louigi Addario-Berry, Gábor Lugosi, Vasiliki Velona, Luc Devroye

Publication date 21 March 2022

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.11787

zbMATH Keywords

preferential attachmentrandom treesbroadcasting problemuniform attachment

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05)

Abstract: We study the broadcasting problem when the underlying tree is a random recursive tree. The root of the tree has a random bit value assigned. Every other vertex has the same bit value as its parent with probability $1-q$ and the opposite value with probability $q$, where $qin[0,1]$. The broadcasting problem consists in estimating the value of the root bit upon observing the unlabeled tree, together with the bit value associated with every vertex. In a more difficult version of the problem, the unlabeled tree is observed but only the bit values of the leaves are observed. When the underlying tree is a uniform random recursive tree, in both variants of the problem we characterize the values of $q$ for which the optimal reconstruction method has a probability of error bounded away from $1/2$. We also show that the probability of error is bounded by a constant times $q$. Two simple reconstruction rules are analyzed in detail. One of them is the simple majority vote, the other is the bit value of the centroid of the tree. Most results are extended to linear preferential attachment trees as well.

Recommendations

• Broadcasting on trees and the Ising model.
• scientific article; zbMATH DE number 1380585
• Robust reconstruction on trees is determined by the second eigenvalue.
• scientific article; zbMATH DE number 2046068
• Reconstruction on trees and spin glass transition

Cites work

• scientific article; zbMATH DE number 1744100 (Why is no real title available?)
• scientific article; zbMATH DE number 3272753 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• An Efron-Stein inequality for nonsymmetric statistics
• An Estimate for Concentration Functions
• Applications of the theory of records in the study of random trees
• Belief propagation, robust reconstruction and optimal recovery of block models
• Broadcasting on Random Directed Acyclic Graphs
• Broadcasting on trees and the Ising model.
• Concentration inequalities. A nonasymptotic theory of independence
• Discrete minimax estimation with trees
• Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture
• Finding Adam in random growing trees
• Finding the seed of uniform attachment trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Logarithmic combinatorial structures: A probabilistic approach
• On the centroid of increasing trees
• Optimal phylogenetic reconstruction
• Phase transitions in phylogeny
• Pólya urns via the contraction method
• Random Trees
• Reconstruction for the Potts model
• Reconstruction on trees and spin glass transition
• Reconstruction on trees: Beating the second eigenvalue
• Robust reconstruction on trees is determined by the second eigenvalue.
• Rumors in a Network: Who's the Culprit?
• Scaling limits and influence of the seed graph in preferential attachment trees
• The generalized Polya's urn design for sequential medical trials
• The height of increasing trees
• The jackknife estimate of variance
• The recovery of the root of a tree

Cited in

(8)

• An asymptotic study of a recursion occurring in the analysis of an algorithm on broadcast communication
• Tree evolution processes for bucket increasing trees
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Inference in balanced community modulated recursive trees
• Broadcasting‐induced colorings of preferential attachment trees
• Broadcasting on Random Directed Acyclic Graphs
• Broadcasting on trees and the Ising model.
• scientific article; zbMATH DE number 6843211 (Why is no real title available?)

This page was built for publication: Broadcasting on random recursive trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117452)