AVERAGING OVER FAST VARIABLES IN THE FLUID LIMIT FOR MARKOV CHAINS: APPLICATION TO THE SUPERMARKET MODEL WITH MEMORY

• 成果类型: Article
• 署名作者: Luczak, M. J.; Norris, J. R.
• 署名单位: University of London; University of Cambridge
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/12-AAP861
• 发表日期: 2013
• 页码: 957-986
• 关键词: shortest; network; QUEUE

摘要

We set out a general procedure which allows the approximation of certain Markov chains by the solutions of differential equations. The chains considered have some components which oscillate rapidly and randomly, while others are close to deterministic. The limiting dynamics are obtained by averaging the drift of the latter with respect to a local equilibrium distribution of the former. Some general estimates are proved under a uniform mixing condition on the fast variable which give explicit error probabilities for the fluid approximation. Mitzenmacher, Prabhakar and Shah [In Proc. 43rd Ann. Symp. Found. Comp. Sci. (2002) 799-808, IEEE] introduced a variant with memory of the join the shortest queue or supermarket model, and obtained a limit picture for the case of a stable system in which the number of queues and the total arrival rate are large. In this limit, the empirical distribution of queue sizes satisfies a differential equation, while the memory of the system oscillates rapidly and randomly. We illustrate our general fluid limit estimate by giving a proof of this limit picture.