Abstract
This paper develops a unified and distributionally complete characterization of the discrete-time M/G/1 queue. Both the discrete-time Pollaczek-Khinchine formula for Bernoulli arrivals and the discrete Residual Lifetime Theorem are comprehensively addressed through a new proposed probability distribution, referred to as Infinite Mixture of Discrete Uniforms (IMDU), which provides an intuitive and mathematically consistent representation of the residual service time. For the waiting time distribution analysis, it is first shown that the idle period is identically distributed to the geometric interarrival time. Building on this identity, the Laplace Transform of the waiting-time distribution for Bernoulli arrivals with general service times is derived. Then, exact functional relationships between the moments of the waiting time and those of the discrete residual service time are obtained. Furthermore, using the distributional Little’s law, non-closed structural relation between the moments of the queue length and those of the waiting time is derived. The non-closedness is due to the staircase-like behavior of the expected number of arrivals in an ordinary renewal process. To make this relation tractable, the stepped-like function is approximated by a straight line whose slope and x-interception are determined minimizing the mean-square difference. Simulation and approximate analytical numerical results of the second (third) factorial moment of the queue length for deterministic, discrete uniform, and shifted Poisson service time show differences smaller than 0.242% (2.17%); in contrast to the substantially larger errors, up to 15.67% (42.4%), incurred by the Poisson arrival process approximation (x-interception at origin).

This publication has 14 references indexed in Scilit: