  Consider a low temperature stochastic Ising model in the phase coexistence
regime with Markov semigroup $P_t$. A fundamental and still largely open
problem is the understanding of the long time behavior of $\d_\h P_t$ when the
initial configuration $\h$ is sampled from a highly disordered state $\nu$
(e.g. a product Bernoulli measure or a high temperature Gibbs measure).
Exploiting recent progresses in the analysis of the mixing time of Monte Carlo
Markov chains for discrete spin models on a regular $b$-ary tree $\Tree^b$, we
tackle the above problem for the Ising and hard core gas (independent sets)
models on $\Tree^b$. If $\nu$ is a biased product Bernoulli law then, under
various assumptions on the bias and on the thermodynamic parameters, we prove
$\nu$-almost sure weak convergence of $\d_\h P_t$ to an extremal Gibbs measure
(pure phase) and show that the limit is approached at least as fast as a
stretched exponential of the time $t$. In the context of randomized algorithms
and if one considers the Glauber dynamics on a large, finite tree, our results
prove fast local relaxation to equilibrium on time scales much smaller than the
true mixing time, provided that the starting point of the chain is not taken as
the worst one but it is rather sampled from a suitable distribution.
