Exit probabilities of markov modulated constrained random walks

Download

index.pdf

Date

2018

Author

Başoğlu Kabran, Fatma

Metadata

Show full item record

Item Usage Stats

222
views

123
downloads

Let X be the constrained random walk on Z2+ with increments (0, 0), (1, 0), (−1, 1), (0, −1) whose jump probabilities are determined by the state of a finite state Markov chain M. X represents the lengths of two queues of customers (or packets, tasks, etc.) waiting for service from two servers working in tandem; the arrival of customers occur with rate λ(Mk), service takes place at rates μ1(Mk), and μ2(Mk) where Mk denotes the current state of the Markov chain M. We assume that the average arrival rate is less than the average service rates, i.e., X is assumed stable. Stability implies that X moves in cycles that restart each time it hits the origin. Let τn be the first time X hits the line ∂An={x:x(1)+x(2)=n}, i.e., when the sum of the queue lengths equals n for the first time ; if the queues share a common buffer, τn represents the time of a buffer overflow and pn = P(x,m)(τn < τ0) is the probability that a given cycle ends with a buffer overflow, i.e., system failure. Let Y be the same random walk as X but only constrained on∂2 = {y ∈ Z×Z+ : y(2) = 0} and its jump probabilities for the first component reversed. Let B = {y ∈ Z2 : y(1) = y ( 2 ) } and let τ be the first time Y hits B . For x ∈ R 2+ , with x (1) + x (2)<1 define xn = ⌊nx⌋ and let m ∈ M denote the initial point of the Markov chain M. We show that P((n−xn(1),xn(2)),m)(τ < ∞) approximates P((xn(1),xn(2)),m)(τn < τ0) with exponentially vanishing relative error when x(1) > 0. We then construct a class of harmonic functions for (Y,M) and use their linear combinations to develop approximate formulas for P(y,m)(τ < ∞). The construction is based on points on a characteristic surface associated with Y defined through the eigenvalues of a matrix whose components depend on the transition matrix of the modulating chain and the jump probabilities of Y . We indicate possible applications of our results and approach in finance and insurance.

Subject Keywords

Random walks (Mathematics)., Stochastic processes., Markov processes., Queuing theory.

URI

http://etd.lib.metu.edu.tr/upload/12622555/index.pdf
https://hdl.handle.net/11511/27773

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Approximation of excessive backlog probabilities of two parallel queues Ünlü, Kamil Demirberk; Sezer, Ali Devin (2018-07-25) Let X be the constrained random walk on Z 2 + with increments (1, 0), (−1, 0), (0, 1) and (0, −1) representing the lengths at service completion times of two queues with exponentially distributed interarrival and service times running in parallel. Denote the arrival and service rates by λ i , µ i , i = 1, 2; we assume λ i < µ i , i = 1, 2, i.e., X is assumed stable. Without loss of generality we assume ρ 1 ≥ ρ 2. Let τ n be the first time X hits the line ∂A n = {x ∈ Z 2 : x(1)+x(2) = n}, i.e., when the sum ...
APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES Sezer, Ali Devin (2018-09-01) 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...
Optimal Buffer Partitioning on a Multiuser Wireless Link Ozel, Omur; Uysal, Elif; GİRİCİ, TOLGA (2010-02-05) We consider a finite buffer shared by multiple packet queues. Throughput can be considerably improved by partitioning the buffer space among the queues judiciously, especially under a high load regime. We formulate optimal buffer partitioning as a resource allocation problem, the solution of which is found through a greedy incremental algorithm in polynomial time. The rest of the work is devoted to applying the optimal buffer allocation strategy in different scenarios modeling a wireless downlink. First, th...
Approximation of the exit probability of a stable Markov modulated constrained random walk Kabran, Fatma Basoglu; Sezer, Ali Devin (2020-06-01) Let X be the constrained randomwalk on Z(+)(2) having increments (1, 0), (- 1, 1), (0,- 1) with jump probabilities lambda(M-k), mu(1)(M-k), and mu(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 mu(1)(M-k), and mu(2)(M-k); the process M represents the random environment within which the system operates. We assume that the average arrival rate with respect to the stationary measur...
Exit probabilities of constrained simple random walks Ünlü, Kamil Demirberk; Sezer, Ali Devin; Department of Financial Mathematics (2018) Consider a nearest neighbor stable two dimensional random walk X constrained to remain on the positive orthant. X is assumed stable, i.e., its average increment points toward the origin. X represents the lengths of two queues (or two stacks in computer science applications) working in parallel. The probability pn that the sum of the components of this random walk reaches a high level n before the random walk returns to the origin is a natural performance measure, representing the probability of a buffer ove...

Citation Formats

F. Başoğlu Kabran, “Exit probabilities of markov modulated constrained random walks,” Ph.D. - Doctoral Program, Middle East Technical University, 2018.