Approximation of the exit probability of a stable Markov modulated constrained random walk

DOI10.1007/S10479-020-03693-7zbMATH1492.60120OpenAlexW3040326075MaRDI QIDQ2115773FDOQ2115773

Authors Fatma Başoğlu Kabran, Ali Devin Sezer

Publication date 21 March 2022

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.06774

queueing systems rare events superharmonic functions Markov modulation affine transformation regime switch characteristic surface exit probabilities multidimensional constrained random walks

Mathematics Subject Classification ID

Large deviations (60F10) Sums of independent random variables; random walks (60G50) Stopping times; optimal stopping problems; gambling theory (60G40) Probabilistic potential theory (60J45)

Abstract: Let

X

be the constrained random walk on

{m a t h b b Z}_{+}^{2}

having increments

(1, 0)

,

(- 1, 1)

,

(0, - 1)

with jump probabilities

l a m b d a (M_{k})

,

m u_{1} (M_{k})

, and

m u_{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

l a m b d a (M_{k})

, and service rates

m u_{1} (M_{k})

, and

m u_{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

a u_{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

m a t h b b Z i m e s {m a t h b b Z}_{+}

having increments

(- 1, 0)

,

(1, 1)

,

(0, - 1)

with probabilities

l a m b d a (M_{k})

,

m u_{1} (M_{k})

, and

m u_{2} (M_{k})

. Let

a u

be the first time the components of

Y

are equal. For

x i n {m a t h b b R}_{+}^{2}

,

x (1) + x (2) < 1

,

x (1) > 0

, and

x_{n} = l f l o o r n x f l o o r

, we show that

P_{(n - x_{n} (1), x_{n} (2)), m)} (a u < i n f t y)

approximates

P_{(x_{n}, m)} (a u_{n} < a u_{0})

with exponentially vanishing relative error as

n i g h t a r r o w i n f t y

. 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)} (a u < i n f t y) .

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Approximation of the exit probability of a stable Markov modulated constrained random walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115773)