My question is related to the asymmetry of the Kullback-Leibler distance. I'm using the discrete definition of the Kullback-Leibler distance, so we have: $$ KL(p,q) = \sum_{s \in S} p(s) \log\left( \frac{p(s)}{q(s)}\right) $$ where $p$ and $q$ are probability distributions over a set $S$.
Assume I can generate an arbitrary number of independent and identically distributed samples, generated by either $p$ or $q$. Let $n$ denote the number of samples I generated. Based on the samples, I want to decide which probability distribution generated them. I arbitrarily take as null hypothesis that they were generated by $q$. Let $\alpha$ denote the probability of Type I error, and $\beta$ denote the probability of Type II error. Kullback proved that:
$n \text{KL}(p,q) \ge \beta \log \frac{\beta}{1-\alpha}+(1-\beta)\log \frac{1-\beta}{\alpha}$
Now pick $\alpha = \beta$. We can rewrite the inequality to:
$n \text{KL}(p,q) \ge (1-2\alpha)\log \frac{1-\alpha}{\alpha}$
If we now switch the null and alternative hypothesis, we get the very similar inequality:
$n \text{KL}(q,p) \ge (1-2\alpha)\log \frac{1-\alpha}{\alpha}$
(1) Now the first question: is it correct to say that the minimum number of samples $n$, required to decide whether the samples where generated using probability distribution $p$ or $q$, must adhere to:
$n \ge \max \left( \frac{(1-2\alpha)}{\text{KL}(q,p)}\log \frac{1-\alpha}{\alpha}, \frac{(1-2\alpha)}{\text{KL}(p,q)}\log \frac{1-\alpha}{\alpha} \right) \\ n \ge \frac{(1-2\alpha)}{\min \left( \text{KL}(q,p), \text{KL}(p,q) \right)}\log \frac{1-\alpha}{\alpha}$
when we assume that $\alpha = \beta$? In other words, to get the "best" possible estimate, are we allowed to take the minimum of the KL distance in both directions (and use this when estimating the number of samples needed)?
In a sense it seems we are actually creating a symmetric version of the KL distance by taking the minimum, which in this case is only "correct" because we assume $\alpha=\beta$.
(2) Extra question: is there a known hypothesis test which achieves the equality?
