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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented May 19, 2016 at 12:22
  • $\begingroup$ I would say KL is always defined, just not always finite. $\endgroup$
    – Aryeh Kontorovich
    Commented May 24, 2016 at 22:16
  • $\begingroup$ Feel free to mark the answer correct if you agree with it :) $\endgroup$
    – Aryeh Kontorovich
    Commented Aug 17, 2016 at 14:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .