Broadcasting on trees and the Ising model.
type: Item
instance of: scholarly article
title: Broadcasting on trees and the Ising model.
zbMATH Open document ID: 1052.60076
author: Yuval Peres
author: Leonard J. Schulman
author: W. Evans
author: Claire Kenyon
published in: The Annals of Applied Probability
publication date: 2004-10-27T00:00:00Z
review text: The authors consider the following process. At the root \(\rho\) of a tree \(T\) there is a binary random variable (spin) taking its values with equal probabilities. This bit is then propagated through the tree as follows: each vertex receives the bit from its parent unchanged with probability \((1-\varepsilon)\) and changed with probability \(\varepsilon\in (0, 1/2]\). The events on different edges are statistically independent. Let \(W\) be a subset of the set of vertices of \(T\). For such \(W\), let the set of the bits arrived at each element of \(W\) be given. Then one tries to reconstruct the original bit on the base of this information. Clearly the probability to do this correctly is at least \(1/2\); denote this probability by \((1+\Delta)/2\), where \(\Delta = \Delta (T, W, \varepsilon)\). The main results of the paper are upper and lower bounds for such \(\Delta(T, W, \varepsilon)\). If the tree is infinite, the bounds yield the following: \(\lim_{n\rightarrow +\infty} \Delta(T, T_n \varepsilon) > 0\) if \(\varepsilon < \varepsilon_c\) and \(\lim_{n\rightarrow +\infty} \Delta(T, T_n \varepsilon) = 0\) if \(\varepsilon > \varepsilon_c\). Here \(T_n\) is the set of the vertices of \(T\) of \(n\)th level. For regular trees, the problem of determining \(\varepsilon_c\) was solved by \textit{P. M. Bleher, J. Ruiz} and \textit{V. A. Zagrebnov} [J. Stat. Phys. 79, 473--482 (1995; Zbl 1081.82515)].
reviewed by: Yuri Kozitsky
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 68M10
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 82B20
zbMATH DE Number: 2110909
zbMATH Keywords: Percolation
zbMATH Keywords: spin
zbMATH Keywords: Ising model
zbMATH Keywords: electrical network
zbMATH Keywords: noisy computation
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1019487349
OpenAlex ID: W1996199671
Wikidata QID: Q105965927
cites work: Unpredictable paths and percolation
cites work: On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
cites work: Graph homomorphisms and phase transitions
cites work: Taxonomy with confidence
cites work: Q4023085
cites work: Q3706275
cites work: Gibbs measures and phase transitions
cites work: Q4358810
cites work: Nearest-neighbor walks with low predictability profile and percolation in \(2+\varepsilon\) dimensions
cites work: On the maximum tolerable noise for reliable computation by formulas
cites work: Remarks on the limiting Gibbs states on a (d+1)-tree
cites work: On the extremality of the disordered state for the Ising model on the Bethe lattice
cites work: Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
cites work: The Ising model and percolation on trees and tree-like graphs
cites work: Random walks and percolation on trees
cites work: Random walks, capacity and percolation on trees
cites work: A branching process showing a phase transition
cites work: Q4705320
cites work: Reconstruction on trees: Beating the second eigenvalue
cites work: Domination between trees and application to an explosion problem
cites work: Critical random walk in random environment on trees
cites work: Reliable computation by formulas in the presence of noise
cites work: Gibbs States on Countable Sets
cites work: Markov random fields on an infinite tree
cites work: Five surprising properties of parsimoniously colored trees
cites work: Theory of statistical inference and information. Transl. from the Slovak by the author
DOI: 10.1214/AOAP/1019487349
Recommended article: Q4705320
Recommended article: Broadcasting on random recursive trees
Recommended article: Reconstruction on trees: Beating the second eigenvalue
Recommended article: Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels
Recommended article: Robust reconstruction on trees is determined by the second eigenvalue.
Recommended article: Percolation on a k-Ary Tree
Recommended article: Reconstruction for the Potts model
description: scientific article; zbMATH DE number 2110909