Premium
Recursive reconstruction on periodic trees
Author(s) -
Mossel Elchanan
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199808)13:1<81::aid-rsa5>3.0.co;2-o
Subject(s) - root (linguistics) , tree (set theory) , bounded function , mathematics , set (abstract data type) , boundary (topology) , algorithm , discrete mathematics , root finding algorithm , combinatorics , value (mathematics) , computer science , statistics , mathematical analysis , philosophy , linguistics , programming language , physics , nonlinear system , quantum mechanics
A periodic tree T n consists of full n ‐level copies of a finite tree T . The tree T n is labeled by random bits. The root label is chosen randomly, and the probability of two adjacent vertices to have the same label is 1−ϵ. This model simulates noisy propagation of a bit from the root, and has significance both in communication theory and in biology. Our aim is to find an algorithm which decides for every set of values of the boundary bits of T , if the root is more probable to be 0 or 1. We want to use this algorithm recursively to reconstruct the value of the root of T n with a probability bounded away from ½ for all n . In this paper we find for all T , the values of ϵ for which such a reconstruction is possible. We then compare the ϵ values for recursive and nonrecursive algorithms. Finally, we discuss some problems concerning generalizations of this model. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 81–97, 1998