Markovian Binary Trees: An algorithmic approach.

The continuous-time Markovian Multitype Branching Process (ctMMTBP) (Athreya-1971; Harris-1963) are powerful stochastic models that describe the evolution of populations of individuals that reproduce and die independently of each other according to specific probability laws. They are playing an increasingly important role in models of population biology, including molecular biology, ecology, epidemiology, evolutionary theory, and in other scientific areas, such as particle physics, chemistry, and computer science. A special case of a ctMMTBP occurs when branch points are restricted to generate at most two new offspring in which case it is known as the binary branch point ctMMTBP, a process that was used in Kontoleon (2006) to model biological phenomena such as phylogenetic processes and macroevolution. In kontoleon-2006 the evolution of branches in tree histories was given an interpretation different from that which underlies the ctMMTBP. Under the ctMMBTP interpretation, a branch point can occur in which a branch of one type dies and a single branch of another type is born. In the interpretation of Kontoleon, this is thought of as a continuation of the same branch with a change of phase of some underlying modulating process. Such a transition is hidden from the point of view of the tree topology. There are two other types of branch points: (i) a binary branch point generating one new daughter and the continuation of the parent, and (ii) a terminating branch point. These are both observable from the point of view of the tree topology. This interpretation led to an alternative representation for this type of branching process called the Markovian Binary Tree (MBT). In this interpretation, the evolution of each branch is governed by a (Transient) Markovian Arrival Process (MAP). MAPs have two types of transitions: hidden and observable, which correspond to the hidden and observable events described above. In essence the binary branch point ctMMTBP was represented as a level-dependent Quasi-Birth-and-Death process. The Markovian Binary Tree representation of the ctMMTBP enables a field that is almost devoid of algorithmic approaches to become subject to the powerful techniques of matrix-analytic theory. In this thesis our object of study is the Markovian Binary Tree. We begin by giving an introduction to the world of branching processes in Chapter 1. We next introduce the theory of matrix analytic methods in Chapter 2 and 3. We commence by discussing the Phase-Type Distribution as a generalization of Exponential distribution, Poisson process, followed by the Phase-Type renewal process. The Phase-type renewal process is the generalization of the Poisson process to non-exponential inter-event distributions. We next discuss the Markovian Arrival Process (MAP). %The MAP is the generalization of the phase-type renewal process to include correlations. The MAP generates the dynamics of the MBT. The concept of the hidden and observable transitions of the MAP is used to alter the interpretations of particle transitions in the ctMMTBP and create the MBT interpretation. The level-independent Quasi-Birth-and-Death process (LIQBD) and level-dependent Quasi-Birth-and-Death process (LDQBD) are then introduced and we analyze the algorithm of Neuts, the algorithm U and the level-independent logarithmic reduction algorithm. The LDQBD process is the framework within which we represent the Markovian binary tree. In Chapter 4 we begin by representing the Markovian Binary Tree (MBT) as a level-dependent Quasi-Birth-and-Death process. We define the MBT and explore its alternative representation as a continuous-time Markovian Multitype Branching Process. Since the MBT is a ctMMTBP, more specifically, a binary-branch point ctMMTBP, we also write the basic branching process equations for the MBT. From these equations we obtain the equation for the probability of eventual extinction of the process. We then develop four algorithms to determine the probability of eventual extinction of the MBT process: the Depth, Order-1, Order-2 and Thicknesses algorithms. We also show that these give rise to second-order equations and we apply Newton's method for fixed-point equations. These algorithms are well defined and converge quadratically in the domain of interest. We compare the relative efficiency of eight iterative methods based on functional iteration, on the basis of the probabilistic interpretation of the successive iterations as well as on the basis of traditional rate of convergence analysis. We illustrate our findings through a few numerical examples. I chapter 5 we focus on transient measures, such as the distribution of the population size at a finite time, the distribution of the time until extinction, and the distribution of the total family size until a given time, as well as the total size until extinction. Our results mainly are formulated as differential equations for probability generating functions and expressions for the factorial moments and conclude by showing how they are applied to demography. Finally, in chapter 6 we analytically investigate the diffusion behavior of information in a Wireless Sensor Network (WSN) modeled as a two-dimensional spatial branching process. Our analysis permits the derivation of the extinction probability of information being diffused from a source node. Our model permits observing how the activity pattern of each node influences the probability of maintaining time-dependent information in the network