A Study of Quasi-Birth-Death Processes and Markovian Bitcoin Models

Abstract

In this dissertation we study a variety of continuous-time Markov chains (CTMCs) and present new formulas that can be used to find the stationary distribution and the Laplace transforms of the transition functions. Our first set of results involve a level-dependent Quasi-Birth-Death (QBD) processes. We study the distribution of the state and the associated running maximum level at a fixed time t. We present new expressions for the Laplace transforms of the transition functions containing this information. This work involves making use of a collection of R-matrices often found in matrix analytic literature. We also show how our methods can be used to study the joint distribution of the running minimum level and state of a level-dependent Markov process of M/G/1-type. Our next set of results are based on a homogeneous QBD proccess. These results involve first computing a new class of R and G-matrices that can be used to find the Laplace transforms of the transition functions associated with a homogeneous QBD process with finitely many levels. Our final set of results are based on two CTMCs studied in G\"obel et al. \cite{GobelKeelerKrzesinskiTaylor}, which were created to model the interactions between a small pool of miners and a larger collection of miners within the Bitcoin network. We use the random-product technique, introduced by Buckingham and Fralix \cite{BuckinghamFralix2015}, to find the stationary distribution of this model when all miners are honest and when the small pool of miners implement the Selfish Mining strategy introduced by Eyal and Sirer in \cite{EyalSirer}. We also study the Laplace transforms of the transition functions associated with these CTMCs and other performance measures such as the expected time it takes for a "fork" in the blockchain to be resolved.