Hitting probabilities of constrained random walks representing tandem networks

Abstract: Let

X

be the constrained random walk on

m a t h b b Z_{+}^{d}

d > 2

, having increments

e_{1}

,

- e_{i} + e_{i + 1}

i = 1, 2, 3, ..., d - 1

and

- e_{d}

with probabilities

l a m b d a

,

m u_{1}

,

m u_{2}

,...,

m u_{d}

, where

e_{1}, e_{2}, .., e_{d}

are the standard basis vectors. The process

X

is assumed stable, i.e.,

l a m b d a < m u_{i}

for all

i = 1, 2, 3, ..., d .

Let

a u_{n}

be the first time the sum of the components of

X

equals

n

. We derive approximation formulas for the probability

{m a t h b b P}_{x} (a u_{n} < a u_{0})

. For

and a sequence of initial points

x_{n} / n i g h t a r r o w x

we show that the relative error of the approximation decays exponentially in

n

. The approximation formula is of the form

{m a t h b b P}_{y} (a u < i n f t y)

where

a u

is the first time the sum of the components of a limit process

Y

is

0

;

Y

is the process

X

as observed from a point on the exit boundary except that it is unconstrained in its first component (in particular

Y

is an unstable process);

Y

and

{m a t h b b P}_{y} (a u < i n f t y)

arise naturally as the limit of an affine transformation of

X

and the probability

{m a t h b b P}_{x} (a u_{n} < a u_{0}) .

The analysis of the relative error is based on a new construction of supermartingales. We derive an explicit formula for

{m a t h b b P}_{y} (a u < i n f t y)

in terms of the ratios

l a m b d a / m u_{i}

which is based on the concepts of harmonic systems and their solutions and conjugate points on a characteristic surface associated with the process

Y

; the derivation of the formula assumes

m u_{i} e q m u_{j}

for

i e q j .

This page was built for publication: Hitting probabilities of constrained random walks representing tandem networks