tag:blogger.com,1999:blog-2811876938195306723.post799509455170158672..comments2023-07-07T01:27:13.382-07:00Comments on Absolutely Regular: 2 inequalitiesAryehhttp://www.blogger.com/profile/14913393383227385317noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-2811876938195306723.post-1333086858853404962009-04-26T01:22:00.000-07:002009-04-26T01:22:00.000-07:00Many thanks to Ryan and Prasad for the helpful poi...Many thanks to Ryan and Prasad for the helpful pointers!Aryehhttps://www.blogger.com/profile/14913393383227385317noreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-28287591945603056632009-04-25T16:55:00.000-07:002009-04-25T16:55:00.000-07:00For any two distributions P,Q on an arbitrary doma...For any two distributions P,Q on an arbitrary domain, with statistical distance d, the statistical distance between P^n, Q^n grows as O(\sqrt(n)H(P,Q)).<br /><br />where H(P,Q) is the Hellinger distance between distributions P,Q.<br /><br />This can be found in Lemmas 3.1,3.2 in the paper :<br /><br />Rounding Parallel Repetitions of Unique Games<br />http://www.cs.princeton.edu/~dsteurer/roundpar.pdfPrasadhttp://www.cs.washington.edu/homes/prasadnoreply@blogger.comtag:blogger.com,1999:blog-2811876938195306723.post-54792145742413555452009-04-24T08:34:00.000-07:002009-04-24T08:34:00.000-07:00Known, I would say. In fact, so long as p and q a...Known, I would say. In fact, so long as p and q are close and not too close to 0 and 1, then the total variation distance is O(sqrt(n)).<br /><br />See, e.g., Exercise 21 (with solution) here:<br /><br />http://www.stat.yale.edu/~pollard/Books/Asymptopia/Metrics.pdf<br /><br />(or some of the calculations here:<br />http://michaelnielsen.org/polymath1/index.php?title=Passing_between_measures<br />)Ryan O'Donnellhttps://www.blogger.com/profile/01760886084136827344noreply@blogger.com