Title
On the link between Markovian trees and tree-structured Markov chains On the link between Markovian trees and tree-structured Markov chains
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Amsterdam ,
Subject
Computer. Automation
Source (journal)
European journal of operational research. - Amsterdam
Volume/pages
201(2010) :3 , p. 791-798
ISSN
0377-2217
ISI
000271261200014
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000271261200014&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000271261200014&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000271261200014&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle