turkmath.org

Let $X$ be the constrained random walk on $\mathbb{Z}_+^2$ having increments $(1,0)$, $(-1,1)$, and $(0,-1)$ with probabilities $\lambda$, $\mu_1$, and~$\mu_2$ representing the lengths of two tandem queues. $X$ is assumed stable and $\mu_1 \neq \mu_2$. Let $\tau_n$ be the first time when the sum of the components of $X$ equals $n$. Let $Y$ be the constrained random walk on $\mathbb{Z} \times \mathbb{Z}_+$ having increments $(-1,0)$, $(1,1)$, and $(0,-1)$ with probabilities $\lambda$, $\mu_1$, and $\mu_2$. Let $\tau$ be the first time that the components of $Y$ are equal to each other. We prove that $P_{n-x_n(1),x_n(2)}(\tau < \infty)$ approximates $p_{x_n}(\tau_n < \tau_0)$ with relative error {\em exponentially decaying} in $n$ for $x_n = \lfloor nx \rfloor,\, x \in \mathbb{R}^2,\, 0 < x(1) + x(2) < 1$, $x(1) >0$. An affine transformation moving the origin to the point $(n,0)$ and letting $n\rightarrow \infty$ connects the $X$ and $Y$ processes. We use a linearm combination of basis functions constructed from single and conjugate points on a characteristic surface associated with $X$ to derive a simple expression for$P_y(\tau < \infty)$ in terms of the ratios $\lambda/\mu_i.$ The proof that the relative error decays exponentially in $n$ uses an upper bound on the error probability and a lower bound on $p_n$ obtained via sub and super solutions of a related Hamilton-Jacobi-Bellman equation. We carry out a similar analysis also for the constrained random walk with increments $(1,0)$, $(-1,0)$, $(0,-1)$ and $(0,1)$ representing the lengths of two queues in parallel. Although the main ideas generalize from the tandem case there are also significant differences. We provide a comparison of these two cases.