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

An i.i.d. process is considered on a compact metric space . Its marginal distribution [pi] is unknown, but is assumed to lie in a moment class of the form, where {fi} are real-valued, continuous functions on , and {ci} are constants. The following conclusions are obtained: (i) For any probability distribution [mu] on , Sanov's rate-function for the empirical distributions of is equal to the Kullback-Leibler divergence D([mu][short parallel][pi]). The worst-case rate-function is identified as where f=(1,f1,...,fn)T, and is a compact, convex set. (ii) A stochastic approximation algorithm for computing L 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.