Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES
Download
index.pdf
Date
2018-09-01
Author
Sezer, Ali Devin
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
235
views
0
downloads
Cite This
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 Y are equal to each other. We prove that Pn-xn(1),x(n)(2)(tau < infinity) approximates p(n)(x(n)) with relative error exponentially decaying in n for x(n) = [n(x)], x is an element of R-+(2), 0 < x(1) + x(2) < 1, x (1) > 0. An affine transformation moving the origin to the point (n, 0) and letting n -> infinity connect the X and Y processes. We use a linear combination of basis functions constructed from single and conjugate points on a characteristic surface associated with X to derive a simple expression for P-y (tau < infinity) in terms of the utilization rates of the nodes. The proof that the relative error decays exponentially in n uses a sequence of subsolutions of a related HamiltonJacobi-Bellman equation on a manifold consisting of three copies of R-+(2) glued to each other along the constraining boundaries. We indicate how the ideas of the paper can be generalized to more general processes and other exit boundaries.
Subject Keywords
Large deviations
,
Constrained random walks
,
Buffer overlow
,
Queueing systems
,
Exit times
,
Harmonic systems
URI
https://hdl.handle.net/11511/31800
Journal
JOURNAL OF APPLIED PROBABILITY
DOI
https://doi.org/10.1017/jpr.2018.60
Collections
Graduate School of Applied Mathematics, Article
Suggestions
OpenMETU
Core
Excessive backlog probabilities of two parallel queues
Unlu, Kamil Demirberk; Sezer, Ali Devin (2020-10-01)
Let X be the constrained random walk on Z2 + with increments (1, 0), (-1, 0), (0, 1) and (0,-1); X represents, at arrivals and service completions, the lengths of two queues (or two stacks in computer science applications) working in parallel whose service and interarrival times are exponentially distributed with arrival rates.i and service rates mu i, i = 1, 2; we assume.i < mu i, i = 1, 2, i.e., X is assumed stable. Without loss of generality we assume.1 =.1/mu 1 similar to.2 =.2/mu 2. Let tn be the first...
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...
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 ...
Exit probabilities of markov modulated constrained random walks
Başoğlu Kabran, Fatma; Sezer, Ali Devin; Department of Financial Mathematics (2018)
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 l...
Factorization of Joint Probability Mass Functions into Parity Check Interactions
Bayramoglu, Muhammet Fatih; Yılmaz, Ali Özgür (2009-07-03)
We show that any joint probability mass function (PMF) can be expressed as a product of parity check factors an d factors of degree one with the help of some auxiliary variables, if the alphabet size is appropriate for defining a parity chec k equation. In other words, marginalization of a joint PMF is equivalent to a soft decoding task as long as a finite field can be constructed over the alphabet of the PMF. In factor graph terminology this claim means that a factor graph representing such a joint PMF alw...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
A. D. Sezer, “APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES,”
JOURNAL OF APPLIED PROBABILITY
, pp. 968–997, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31800.