Worst-case large-deviation asymptotics with application to queueing and information theory

Abstract: An i.i.d. process is considered on a compact metric space . Its marginal distribution is unknown, but is assumed to lie in a moment class of the form, where are real-valued, continuous functions on , and are constants. The following conclusions are obtained: [(i)] For any probability distribution on , Sanov’s rate-function for the empirical distributions of is equal to the Kullback–Leibler divergence . The worst-case rate-function is identified as where , and is a compact, convex set. [(ii)] A stochastic approximation algorithm for computing is introduced based on samples of the process . [(iii)] A solution to the worst-case one-dimensional large-deviation problem is obtained through properties of extremal distributions, generalizing Markov’s canonical distributions. [(iv)] Applications to robust hypothesis testing and to the theory of buffer overflows in queues are also developed. [Copyright &y& Elsevier]