Journal article

On the link between Markovian trees and tree-structured Markov chains

Sophie Hautphenne, Benny Van Houdt

European Journal of Operational Research | ELSEVIER | Published : 2010


In this paper, we describe a link between Markovian binary trees (MBT) and tree-like quasi-birth-and-death processes (TLQBD) by associating a specific TLQBD to each MBT. The algorithms to compute the matrices Gk in the TLQBD then correspond to the algorithms calculating the extinction probability vector of the MBT. This parallelism leads to a new quadratic algorithm, based on the Newton iteration method, which converges to the extinction probability of an MBT. We also present a one-to-one correspondence between a general Markovian tree (GMT) and a scalar tree-structured M/G/1-type Markov chain. This allows us to prove the equivalence between the main result on the positive recurrence, null r..

View full abstract


Funding Acknowledgements

We thank the referees for their relevant comments, as well as Guy Latouche for some useful discussions, which helped to improve the presentation of the paper. The first author is an Aspirant of the Fonds National de la Recherche Scientifique (F.R.S.-F.N.R.S.), part of her research has been Supported by a F.R.I.A. Grant.