Markov chains on trees: Almost lower and upper directed cases

The transition matrix of a Markov chain (Xk,k≥0) on a finite or infinite rooted tree is said to be almost upper-directed if, given Xk, the node Xk+1 is either a descendant of Xk or the parent of Xk. It is said to be almost lower-directed if given Xk, Xk+1 is either an ancestor of Xk or a child of Xk. These models include nearest neighbor Markov chains on trees. Under an irreducibility assumption, we show that every almost upper-directed transition matrix on infinite (locally finite) trees has some invariant measures. An invariant measure π is expressed thanks to a determinantal formula. We give general explicit criteria for recurrence and positive recurrence. An efficient algorithm (the leaf addition algorithm) of independent interest allows π to be computed on many trees, without resorting to linear algebra considerations. Flajolet, in a series of papers (starting from [12]), provided some relations between continuous fractions, generating functions of weighted Mötzkin paths, and used them in connection with the analysis of birth and death processes. These fruitful representations made it possible to establish many formulae for continuous fractions. Analogous considerations appear here: this type of study can be extended to weighted paths on trees, whose generating functions can also be expressed, this time in terms of multicontinuous fractions.