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

DOI10.1007/S10479-020-03693-7zbMATH Open1492.60120arXiv1909.06774OpenAlexW3040326075MaRDI QIDQ2115773FDOQ2115773

Fatma Başoğlu Kabran, Ali Devin Sezer

Publication date: 21 March 2022

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

Abstract: Let $X$ be the constrained random walk on ${mathbbZ}_{+}^2$ having increments $(1,0)$, $(-1,1)$, $(0,-1)$ with jump probabilities $lambda(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 $lambda(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 $mathbbZimes{mathbbZ}_{+}$ having increments $(-1,0)$, $(1,1)$, $(0,-1)$ with probabilities $lambda(M_k)$, $m{u}_1(M_k)$, and $m{u}_2(M_k)$. Let $au$ be the first time the components of $Y$ are equal. For $xin{mathbbR}_{+}^2$, $x(1)+x(2)<1$, $x(1)>0$, and $x_n=lfloornxfloor$, we show that $P_{(n-x_n(1),x_n(2)),m)}(au<infty)$ approximates $P_{(x_n,m)}(a{u}_n<a{u}_0)$ with exponentially vanishing relative error as $nightarrowinfty$. 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)}(au<infty).$

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

zbMATH Keywords

queueing systemsrare eventssuperharmonic functionsMarkov modulationaffine transformationregime switchcharacteristic surfaceexit probabilitiesmultidimensional 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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability
• Matrices
• Importance sampling algorithms for first passage time probabilities in the infinite server queue
• Importance Sampling, Large Deviations, and Differential Games
• A Fast Cross-Entropy Method for Estimating Buffer Overflows in Queueing Networks
• Splitting for rare event simulation: A large deviation approach to design and analysis
• Optimal Sampling of Overflow Paths in Jackson Networks
• The design and analysis of a generalized RESTART/DPR algorithm for rare event simulation
• Large deviations of a modified Jackson network: stability and rough asymptotics
• Large deviations for Markov chains in the positive quadrant
• Importance sampling for sums of random variables with regularly varying tails
• Importance sampling for Jackson networks
• Analysis of an importance sampling estimator for tandem queues
• Markov-modulated queueing systems
• A quick simulation method for excessive backlogs in networks of queues
• Dynamic importance sampling for queueing networks
• Optimally efficient estimation of the statistics of rare events in queueing networks
• Efficient simulation of a tandem Jackson network
• Efficient simulation of buffer overflow probabilities in jackson networks with feedback
• Analysis of state-independent importance-sampling measures for the two-node tandem queue
• Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks
• Importance sampling for a Markov modulated queuing network
• Colliding stacks: A large deviations analysis
• Probabilistic analysis of some distributed algorithms
• Martin boundary of a killed random walk on a quadrant
• Large deviations of Jackson networks.
• An Analysis of a Memory Allocation Scheme for Implementing Stacks
• Generalized analytic functions
• Large deviations analysis for distributed algorithms in an ergodic Markovian environment
• Asymptotically optimal importance sampling for Jackson networks with a tree topology
• Asymptotics of first passage times for random walk in an orthant
• Efficient Simulation of Light-Tailed Sums: an Old-Folk Song Sung to a Faster New Tune...
• Excessive backlog probabilities of two parallel queues
• Approximation of excessive backlog probabilities of two tandem queues

Cited In (1)

• Exit problem for Ornstein-Uhlenbeck processes: a random walk approach

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)