From dawagner@tucson.princeton.edu Tue Mar 21 15:23:47 EST 1995
Article: 33479 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Subject: Statistically distinguishing two random sources
Message-ID: <1995Mar21.201232.22137@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Princeton University
Date: Tue, 21 Mar 1995 20:12:32 GMT
Lines: 15

I'm sure this must be completely solved already somewhere...

I have two memoryless random sources outputting b-bit chunks:
one has the uniform distribution on {0,1}^b, and the other
has some known distribution.  I flip a coin, pick one of the
two sources, and give you lots of outputs from that source.
Assume you know the distribution of both sources, and think
of b as small -- maybe 5 or 10.

Roughly how many outputs do you need to distinguish the two
sources with high probability?  (in terms of their distributions)
What algorithm would you use to actually do this?

[I guess I'm looking for some sort of measure of the distance
between the two random sources.]