A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees

Details A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees

2009-03-17

arxiv.org/abs/0903.2962v3

Mathematics

Probability

10 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491416