ON RANDOM WALKS AND STABLE GI/G/1 QUEUES.

Let X, X//1, X//2,. . . be independent and identically distributed random variables with E left brace X right brace less than 0, let S//0 equals O, S//n equals X//1 plus . . . plus X//n for n greater than equivalent to 1, and M equals sup left brace S//n, n greater than equivalent to 0 right brace . If r greater than 0 then a well-known result in random walk theory states 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 plus 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 left brace S//n, n greater than equivalent to 1 right brace . 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.