Subject: Statistically distinguishing two random sources

From: [email-masked] (David A. Wagner)
Date: Tue, 21 Mar 1995 20:12:32 GMT

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.]