# algorithms – Distinguishability given black box access to the distribution

Consider two probability distributions $$D$$ and $$U$$, over $$n$$-bit strings, where $$U$$ is the uniform distribution. We are not given an explicit description of $$D$$: we are only given black-box access, ie, we are only given a sampling device that can sample from $$D$$. Consider a sample $$z in {0, 1}^{n}$$, taken from either $$D$$ or $$U$$. We want to know which one is the case: we consider polynomial-time algorithms that use the sampling device.

Intuitively, it seems obvious that the best polynomial-time algorithm that distinguishes which distribution the sample $$z$$ came from must have gotten that very $$z$$ as a sample at least once when running the sampling device. How do I mathematically formalize this statement?