Consider the following problem: Given a collection of probability distributions (q_1,...,q_n) and a sample access to an unknown target distribution p, find which q_i is closest to p in total variation. Turns out that this problem in general is not tractable. However, we can output a q_i such that TV(q_i,p) <= \beta OPT + \epsilon. Here OPT is the TV between p and best candidate in our collection.

In this talk, we will see that the approximation factor \beta has to be at least 3.

PS: If you attended Klim Efrimenko's talk then he cited this result but did not go into the proof.