The geometry of M/D/1 queues and large deviation

摘要

Since an M/D/1 queue is represented by a Markov chain, we can consider the set of all the M/D/1 queues as a subset of Markov chains. A geometric structure is induced from the geometric structure of the set of Markov chains, which forms an exponential family. In this paper, we show that in the large deviation of the tail probability of the queue length of an M/D/1, the rate function and a twisted Markov chain, etc., are represented in terms of the geometry. Moreover, in the importance sampling (IS) simulation for the M/D/1 queue, we elucidate the geometric relation between the underlying distribution and a simulation distribution, and evaluate the variance of an IS estimate by geometric quantities.