math.PR
Approximation of the Exit Probability of a Stable Markov Modulated Constrained Random Walk. Let X be the constrained random walk on mathbb Z 2 having increments (1,0) , ( 1,1) , (0, 1) with jump probabilities lambda(M k) , mu 1(M k) , and mu 2(M k) where M is an irreducible aperiodic finite state Markov chain. The process X represents the lengths of two tandem queues with arrival rate lambda(M k) , and service rates mu 1(M k) , and mu 2(M k) . We assume that the average arrival rate with respect to the stationary measure of M is less than the average service rates, i.e., X is assumed stable. Let tau n be the first time when the sum of the components of X equals n for the first time. Let Y be the random walk on mathbb Z times mathbb Z having increments ( 1,0) , (1,1) , (0, 1) with probabilities lambda(M k) , mu 1(M k) , and mu 2(M k) . Let tau be the first time the components of Y are equal. For x in mathbb R 2 , x(1) x(2) 1 , x(1) 0 , and x n lfloor nx rfloor , we show that P (n x n(1),x n(2)),m) ( tau infty) approximates P (x n,m) ( tau n tau 0) with exponentially vanishing relative error as n rightarrow infty . For the analysis we define a characteristic matrix in terms of the jump probabilities of (X,M). The 0 level set of the characteristic polynomial of this matrix defines the characteristic surface conjugate points on this surface and the associated eigenvectors of the characteristic matrix are used to define (sub super) harmonic functions which play a fundamental role both in our analysis and the computation approximation of P (y,m) ( tau infty).