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 $nrightarrow 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).$
Download