Consider the following problem: Given a set of probability distributions (p_1,p_2) and a sample access to an unknown target distribution p, find which hypothesis (p_1 or p_2) is closer to p in total variation (TV). In general this is not possible. However, we can output a p_i (from p_1 or p_2) such that TV(p_i,p) <= \beta OPT + \epsilon. Here OPT is the TV between p and the best candidate in our set. We will show a simple test for which \beta = 3 (which is in fact optimal). Time permitting, we will also see that if we are allowed to output a distribution not from the set (p_1, p_2), then we can get \beta = 2.
