Gubner, John A.; Gopinath, B.; Varadhan, S. R. S. Bounding functions of Markov processes and the shortest queue problem. (English) Zbl 0707.60086 Adv. Appl. Probab. 21, No. 4, 842-860 (1989). 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 Cited in 1 Review MSC: 60K25 Queueing theory (aspects of probability theory) 90B22 Queues and service in operations research Keywords:Lyapunov function; parallel queues; supermartingales Citations:Zbl 0361.60014 × Cite Format Result Cite Review PDF Full Text: DOI Link