Broadcasting on trees and the Ising model. (Q1884823): Difference between revisions

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