  In this paper we consider $q$-state potential on general infinite trees with
a nearest-neighbor $p$-adic interactions given by a stochastic matrix. {We show
the uniqueness of the associated Markov chain ({\em splitting Gibbs measures})
under some sufficient conditions on the stochastic matrix.} Moreover, we find a
family of stochastic matrices for which there are at least two $p$-adic Markov
chains on an infinite tree (in particular, on a Cayley tree). When the $p$-adic
norm of $q$ is greater ({{\em resp.}} less) than the norm of any element of the
stochastic matrix then it is proved that the $p$-adic Markov chain is bounded
({{\em resp.}} is not bounded). Our method {uses} a classical boundary law
argument carefully adapted from the real case to the $p$-adic case, by a
systematic use of some nice peculiarities of the ultrametric ($p$-adic) norms.
