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 = { π : 〈 π , f i 〉 = c i , i = 1 , … , n } , where { f i } are real-valued, continuous functions on X , and { c i } are constants. The following conclusions are obtained: (i) y probability distribution μ on X , Sanov’s rate-function for the empirical distributions of X is equal to the Kullback–Leibler divergence D ( μ ∥ π ) . The worst-case rate-function is identified as L ( μ ) ≔ inf π ∈ P D ( μ ∥ π ) = sup λ ∈ R ( f , c ) 〈 μ , log ( λ T f ) 〉 , where f = ( 1 , f 1 , … , f n ) T , and R ( f , c ) ⊂ R n + 1 is a compact, convex set. hastic approximation algorithm for computing L is introduced based on samples of the process X . tion to the worst-case one-dimensional large-deviation problem is obtained through properties of extremal distributions, generalizing Markov’s canonical distributions. ations to robust hypothesis testing and to the theory of buffer overflows in queues are also developed.