2009/03/17 by Marco Formentin, M. Formentin, Formentin, M. +2
Computer Science · Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis #math-ph #math.MP #math.PR #msc:60K35 #msc:82B20 #msc:82B44
paper · pdf · doi:10.48550/arxiv.0903.2962
10 pages
arxiv created 2010/01/18 · arxiv updated 2010/02/08
We give a criterion of the form Q(d)c(M)<1 for the non-reconstructability of tree-indexed q-state Markov chains obtained by broadcasting a signal from the root with a given transition matrix M. Here c(M) is an explicit function, which is convex over the set of M's with a given invariant distribution, that is defined in terms of a (q-1)-dimensional variational problem over symmetric entropies. Further Q(d) is the expected number of offspring on the Galton-Watson tree. This result is equivalent to proving the extremality of the free boundary condition-Gibbs measure within the corresponding Gibbs-simplex. Our theorem holds for possibly non-reversible M and its proof is based on a general Recursion Formula for expectations of a symmetrized relative entropy function, which invites their use as a Lyapunov function. In the case of the Potts model, the present theorem reproduces earlier results of the authors, with a simplified proof, in the case of the symmetric Ising model (where the argument becomes similar to the approach of Pemantle and Peres) the method produces the correct reconstruction threshold), in the case of the (strongly) asymmetric Ising model where the Kesten-Stigum bound is known to be not sharp the method provides improved numerical bounds.