Deviation Matrix For G1/M/1-type Markov Chains

Abstract:GI/M/1-type Markov chains are an important class of stochastic models, which have a lot of applications, especillay in queuing theory. Deviation matrix is an important topic in the context of Markov chains, which is closely related with ergodic convergence rates, Poisson equation, perturbation analysis, asymptotic variance, and others. Therefore, the study of GI/M/1-type Markov chains has important theoretical significance.This thesis is composed of three main contents. First, we investigate the deviation matrix for discrete-time GI/M/1-type Markov chains in terms of the matrix-analytic methods. We convert continuous-time GI/M/1-type Markov chains into discrete-time GI/M/1-type Markov chains based on the uniformization technique, then obtain the parallel results. Secondly, we revisit the link between the deviation matrix and asymptotic variance. We derive the explicit expressions of the deviation matrix and asymptotic variance for discrete-time birth-death processes. Third, we apply the results to the A.B. CLARKE tandem queue and calculate the stationary distribution and the asymptotic variance of the queue length.