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