3
$\begingroup$

Given two discrete distributions $P$ and $Q$, with computable total variation distance $d_{TV}(P,Q)=||P - Q||_1$, is there a precise bound for $d_{TV}(P^n,Q^n)=||P^n - Q^n||_1$, as need to estimate the power of an optimal test for multiple samples? Moreover, is is possible to exactly compute $d_{TV}(P^n,Q^n)=||P^n - Q^n||_1$ without enumerating all combinations?

The best bound that I could find is based on the Chernoff Information The complexity of distinguishing distributions

$\endgroup$

1 Answer 1

1
$\begingroup$

There is no exact formula for computing $d_{TV}(P^n,Q^n)$ in terms of $d_{TV}(P,Q)$ alone. Consider the example $P=(0,1)$, $Q=(0.1,0.9)$, $P'=(0.2,0.8)$. Then $d_{TV}(P,Q)=d_{TV}(P',Q)=0.2$, but $$ 0.38 = d_{TV}(P^2,Q^2) \neq d_{TV}({P'}^2,Q^2) = 0.34 .$$ For an upper bound, you can use Pinsker's inequality: $$ d_{TV}(P^n,Q^n)^2/2 \le n \min(KL(P||Q),KL(Q||P), $$ where KL is the Kullback-Leibler divergence, which is defined in your linked article.

$\endgroup$
3
  • $\begingroup$ Thanks a lot for the answer. Are there any other known upper bounds that I could look into, as the KL distance is not always defined... $\endgroup$
    – user91882
    May 19, 2016 at 12:22
  • $\begingroup$ I would say KL is always defined, just not always finite. $\endgroup$ May 24, 2016 at 22:16
  • $\begingroup$ Feel free to mark the answer correct if you agree with it :) $\endgroup$ Aug 17, 2016 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.