Inequalities for the L1 Deviation of the Empirical Distribution

Weissman, Tsachy ; Ordentlich, Erik ; Seroussi, Gadiel ; Verdu, Sergio ; Weinberger, Marcelo J.

HP Development Company

关键词: Sanov's theorem;    Pinsker's inequality;    large deviations;    L(subscript 1) distance;    divergence;    variational distance;    Chernoff bound;   

RP-ID  :  HPL-2003-97R1

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We derive bounds on the probability that the L(subscript 1) distance between the empirical distribution of a sequence of independent identically distributed random variables and the true distribution is more than a specified value. We also derive a generalization of Pinsker's inequality relating the L(subscript 1) distance to the divergence. 10 Pages