I have a discrete distribution over the set \({1, \ldots, d}\) with a corresponding pmf P. Given a dataset with n i.i.d. samples from P, I compute the empirical distribution as Q. I want to bound from above and below \(E[\|P-Q\|_1]\). I would think that this is something well known, but I just can't seem to find a good reference. I tried using the DKW inequality (http://en.wikipedia.org/wiki/Dvoretzky–Kiefer–Wolfowitz_inequality) and then trying to apply Markov's inequality, but was unable to get anything from that.

This is not a homework question. I'd greatly appreciate any pointers/help.

This is not a homework question. I'd greatly appreciate any pointers/help.

Last edited: