Hitting probabilities of constrained random walks representing tandem networks

SEZER A. D.

Probability in the Engineering and Informational Sciences, 2025 (SCI-Expanded, Scopus) identifier identifier identifier

  • Publication Type: Article / Article
  • Publication Date: 2025
  • Doi Number: 10.1017/s0269964825100077
  • Journal Name: Probability in the Engineering and Informational Sciences
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, zbMATH, Civil Engineering Abstracts
  • Keywords: buffer overflow, constrained random walks, harmonic systems, hitting probabilities, large deviations, queueing systems, rare events, relative error analysis
  • Middle East Technical University Affiliated: Yes

Abstract

We develop anapproximation for the buffer overflow probability of a stable tandem network in dimensions three or more. The overflow event in terms of the constrained random walk representing the network is the following: the sum of the components of the process hits n before hitting 0. This is one of the most commonly studied rare events in the context of queueing systems and the constrained processes representing them. The approximation is valid for almost all initial points of the process and its relative error decays exponentially in n. The analysis is based on an affine transformation of the process and the problem; as n → ∞ the transformed process converges to an unstable constrained random walk. The approximation formula consists of the probability of the limit unstable process hitting a limit boundary in finite time. We give an explicit formula for this probability in terms of the utilization rates of the nodes of the network.