TY - JOUR

T1 - Universal and composite hypothesis testing via mismatched divergence

AU - Unnikrishnan, Jayakrishnan

AU - Huang, Dayu

AU - Meyn, Sean P.

AU - Surana, Amit

AU - Veeravalli, Venugopal V.

N1 - Funding Information:
Manuscript received September 10, 2009; revised June 30, 2010; accepted July 13, 2010. Date of current version February 18, 2011. This research was supported in part by the NSF under grant CCF 07-29031 and by UTRC. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF or UTRC. Portions of the results presented here were published in abridged form in [1].

PY - 2011/3

Y1 - 2011/3

N2 - For the universal hypothesis testing problem, where the goal is to decide between the known null hypothesis distribution and some other unknown distribution, Hoeffding proposed a universal test in the nineteen sixties. Hoeffding's universal test statistic can be written in terms of KullbackLeibler (K-L) divergence between the empirical distribution of the observations and the null hypothesis distribution. In this paper a modification of Hoeffding's test is considered based on a relaxation of the K-L divergence, referred to as the mismatched divergence. The resulting mismatched test is shown to be a generalized likelihood-ratio test (GLRT) for the case where the alternate distribution lies in a parametric family of distributions characterized by a finite-dimensional parameter, i.e., it is a solution to the corresponding composite hypothesis testing problem. For certain choices of the alternate distribution, it is shown that both the Hoeffding test and the mismatched test have the same asymptotic performance in terms of error exponents. A consequence of this result is that the GLRT is optimal in differentiating a particular distribution from others in an exponential family. It is also shown that the mismatched test has a significant advantage over the Hoeffding test in terms of finite sample size performance for applications involving large alphabet distributions. This advantage is due to the difference in the asymptotic variances of the two test statistics under the null hypothesis.

AB - For the universal hypothesis testing problem, where the goal is to decide between the known null hypothesis distribution and some other unknown distribution, Hoeffding proposed a universal test in the nineteen sixties. Hoeffding's universal test statistic can be written in terms of KullbackLeibler (K-L) divergence between the empirical distribution of the observations and the null hypothesis distribution. In this paper a modification of Hoeffding's test is considered based on a relaxation of the K-L divergence, referred to as the mismatched divergence. The resulting mismatched test is shown to be a generalized likelihood-ratio test (GLRT) for the case where the alternate distribution lies in a parametric family of distributions characterized by a finite-dimensional parameter, i.e., it is a solution to the corresponding composite hypothesis testing problem. For certain choices of the alternate distribution, it is shown that both the Hoeffding test and the mismatched test have the same asymptotic performance in terms of error exponents. A consequence of this result is that the GLRT is optimal in differentiating a particular distribution from others in an exponential family. It is also shown that the mismatched test has a significant advantage over the Hoeffding test in terms of finite sample size performance for applications involving large alphabet distributions. This advantage is due to the difference in the asymptotic variances of the two test statistics under the null hypothesis.

KW - Generalized likelihood-ratio test

KW - KullbackLeibler (K-L) information

KW - hypothesis testing

KW - online detection

UR - http://www.scopus.com/inward/record.url?scp=79951922225&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79951922225&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2104670

DO - 10.1109/TIT.2011.2104670

M3 - Article

AN - SCOPUS:79951922225

SN - 0018-9448

VL - 57

SP - 1587

EP - 1603

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 3

M1 - 5714276

ER -