Let $X$ be the constrained random walk on ${mathbb Z}_+^2$ taking the steps $(1,0)$, $(-1,1)$ and $(0,-1)$ with probabilities $lambda < (mu_1 eq mu_2)$; in particular, $X$ is assumed stable. Let $tau_n$ be the first time $X$ hits $partial A_n = {x:x(1)+x(2) = n }$ For $x in {mathbb Z}_+^2, x(1) + x(2) < n$, the probability $p_n(x)= P_x( tau_n < tau_0)$ is a key performance measure for the queueing system represented by $X$. Let $Y$ be the constrained random walk on ${mathbb Z} times {mathbb Z}_+$ with increments $(-1,0)$, $(1,1)$ and $(0,-1)$. Let $tau$ be the first time that the components of $Y$ equal each other. We derive the following explicit formula for $P_y(tau < infty)$: [ P_y(tau < infty) = W(y)= rho_2^{y(1)-y(2)} + frac{mu_2 - lambda}{mu_2 - mu_1} rho_1^{ y(1)-y(2)} rho_1^{y(2)} + frac{mu_2-lambda}{mu_1 -mu_2} rho_2^{y(1)-y(2)} rho_1^{y(2)}, ] where, $rho_i = lambda/mu_i$, $i=1,2$, $y in {mathbb Z}times{ mathbb Z}_+$, $y(1) > y(2)$, and show that $W(n-x_n(1),x_n(2))$ approximates $p_n(x_n)$ 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$. The steps of our analysis: 1) with an affine transformation, move the origin $(0,0)$ to $(n,0)$ on $partial A_n$; let $n earrow infty$ to remove the constraint on the $x(2)$ axis; this step gives the limit {em unstable} /{em transient} constrained random walk $Y$ and reduces $P_{x}(tau_n < tau_0)$ to $P_y(tau < infty)$; 2) construct a basis of harmonic functions of $Y$ and use it to apply the superposition principle to compute $P_y(tau < infty).$ The construction involves the use of conjugate points on a characteristic surface associated with the walk $X$. The proof that the relative error decays exponentially uses a sequence of subsolutions of a related HJB equation on a manifold.
Download