Bounding functions of Markov processes and the shortest queue problem. (English) Zbl 0707.60086

We prove a theorem which can be used to show that the expectation of a non-negative function of the state of a time-homogeneous Markov process is uniformly bounded in time. This is reminiscent of the classical theory of non-negative supermartingales, except that our analog of the supermartingale inequality need not hold almost surely. Consequently, the theorem is suitable for establishing the stability of systems that evolve in a stabilizing mode in most states, though from certain states they may jump to a less stable state. We use this theorem to show that ‘joining the shortest queue’ can bound the expected sum of the squares of the differences between all pairs among N queues, even under arbitrarily heavy traffic. (Author’s abstract).
It would be interesting to know the relation between condition (2.3) of the present paper and the extensions of Foster’s criterion [cf. R. L. Tweedie, ibid. 8, 737-771 (1976; Zbl 0361.60014)].
Reviewer: M.Schäl


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research


Zbl 0361.60014
Full Text: DOI Link