A Note On the Statistical Difference of Small Direct Products

by Leonid Reyzin
 
Abstract

We demonstrate that if two probability distributions D and E of sufficiently small min-entropy have statistical difference epsilon then the direct-product distributions Dl and El have statistical difference at least roughly epsilon\sqrt{l}, provided that l is sufficiently small, smaller than roughly 1/\epsilon4/3. Previously known bounds did not work for few repetitions l, requiring l>1/epsilon2.

This work appears as Boston University Computer Science Technical Report BUCS-TR-2004-032.