Publication
Title
On the link between Markovian trees and tree-structured Markov chains
Author
Abstract
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 recurrence or transience of a scalar tree-structured M/G/1-type Markov chain and the criticality of a GMT.
Language
English
Source (journal)
European journal of operational research. - Amsterdam
Publication
Amsterdam : 2010
ISSN
0377-2217
Volume/pages
201 :3 (2010) , p. 791-798
ISI
000271261200014
Full text (Publisher's DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identifier
Creation 26.01.2010
Last edited 25.05.2022
To cite this reference