On Random Walks and Stable GI/G/1 Queues

Abstract

Let X, X1, X2, … be independent and identically distributed random variables with E{X} < 0, let S0 ≡ 0, Sn = X1 + ⋯ + Xn for n ≥ 1, and M = sup(Sn, n ≥ 0). If r > 0 then a well-known result in random walk theory slates that M has a finite moment of order r if and only if the positive part of X has a finite moment of order r + 1. Utilizing the intimate relationship between random walks and single server queues, this paper presents a new and simple proof for this basic result. Identities involving the distribution functions and the integer moments of M and X are then derived by simple, probabilistic arguments. Bounds are then obtained for the expected values of some important variables associated with the random walk (Sn, n ≥ 1). All of these random-walk results are applied to the stable queue GI/G/1, and some standard queueing results are subsequently obtained in an effortless manner.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 19 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.