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

An i.i.d. process X is considered on a compact metric space X. Its marginal distribution ππ is unknown, but is assumed to lie in a moment class of the form, P={π:〈π,fi〉=ci,i=1,…,n},P={π:〈π,fi〉=ci,i=1,…,n}, where {fi}{fi} are real-valued, continuous functions on X, and {ci}{ci} are constants. The following conclusions are obtained: (i)For any probability distribution μμ on X, Sanov’s rate-function for the empirical distributions of X is equal to the Kullback–Leibler divergence D(μ∥π)D(μ∥π). The worst-case rate-function is identified as L(μ)≔infπ∈PD(μ∥π)=supλ∈R(f,c)〈μ,log(λTf)〉, where f=(1,f1,…,fn)Tf=(1,f1,…,fn)T, and R(f,c)⊂Rn+1R(f,c)⊂Rn+1 is a compact, convex set.(ii)A stochastic approximation algorithm for computing LL is introduced based on samples of the process X.(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.