  Consider a Markov chain on an infinite tree T=(V,E) rooted at \rho. In such a
chain, once the initial root state \sigma(\rho) is chosen, each vertex
iteratively chooses its state from the one of its parent by an application of a
Markov transition rule (and all such applications are independent). Let \mu_j
denote the resulting measure for \sigma(\rho)=j. The resulting measure \mu_j is
defined on configurations \sigma=(\sigma(x))_{x\in V}\in A^V, where A is some
finite set. Let \mu_j^n denote the restriction of \mu to the sigma-algebra
generated by the variables \sigma(x), where x is at distance exactly n from
\rho. Letting \alpha_n=max_{i,j\in A}d_{TV}(\mu_i^n,\mu_j^n), where d_{TV}
denotes total variation distance, we say that the reconstruction problem is
solvable if lim inf_{n\to\infty}\alpha_n>0. Reconstruction solvability roughly
means that the nth level of the tree contains a nonvanishing amount of
information on the root of the tree as n\to\infty. In this paper we study the
problem of robust reconstruction. Let \nu be a nondegenerate distribution on A
and \epsilon >0. Let \sigma be chosen according to \mu_j^n and \sigma' be
obtained from \sigma by letting for each node independently,
\sigma(v)=\sigma'(v) with probability 1-\epsilon and \sigma'(v) be an
independent sample from \nu otherwise. We denote by \mu_j^n[\nu,\epsilon ] the
resulting measure on \sigma'. The measure \mu_j^n[\nu,\epsilon ] is a
perturbation of the measure \mu_j^n.
