On universal hypotheses testing via large deviations

A prototype problem in hypotheses testing is discussed. The problem of deciding whether an i.i.d. sequence of random variables has originated from a known source P₁ or an unknown source P₂ is considered. The exponential rate of decrease in type II probability of error under a constraint on the minimal rate of decrease in type I probability of error is chosen for a criterion of optimality. Using large deviations estimates, a decision rule that is based on the relative entropy of the empirical measure with respect to P₁ is proposed. In the case of discrete random variables, this approach yields weaker results than the combinatorial approach used by Hoeffding (1965). However, it enables the analysis to be extended to the general case of Rⁿ-valued random variables. Finally, the results are extended to the case where P₁ is an unknown parameter-dependent distribution that is known to belong to a set of distributions (P⁰₁, θ∈Θ)