Hide/Show Apps


Let X be the constrained random walk on Z(+)(2) having increments (1, 0), (-1, 1), and (0, -1) with respective probabilities A lambda,mu 1, and mu 2 representing the lengths of two tandem queues. We assume that X is stable and mu 1 not equal 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 Z x 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 Pn-xn(1),x(n)(2)(tau < infinity) approximates p(n)(x(n)) with relative error exponentially decaying in n for x(n) = [n(x)], x is an element of 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 -> infinity connect the X and Y processes. We use a linear 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 < infinity) in terms of the utilization rates of the nodes. The proof that the relative error decays exponentially in n uses a sequence of subsolutions of a related HamiltonJacobi-Bellman equation on a manifold consisting of three copies of R-+(2) glued to each other along the constraining boundaries. We indicate how the ideas of the paper can be generalized to more general processes and other exit boundaries.