  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.
