3
$\begingroup$

Suppose we know two sets of distributions $A=\{p_1,p_2,\cdots,p_k\}$ and $B=\{q_1,q_2,\cdots,q_k\}$. We are given $C=\{r_1,r_2,\cdots,r_k\}$ such that $r_i=p_i$ for all $i$ or $r_i=q_i$ for all $i$.

We can choose any $1\leq i \leq k$, and get a sample of $r_i$. The goal is to determine which case it is with high probability, says $2/3$ use as few queries as possible.

It seems one can choose $j=\arg \max_i |p_i-q_i|$, and sample $r_i$ many times with $|p_i-q_i|$ denotes the total variance.

Is the number of queries $\Theta(1/\epsilon^2)$ with $\epsilon=|p_j-q_j|$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

One quick remark: the upper bound will be $$ O\left(\min_j \frac{1}{H^2(p_j,q_j)}\right) $$ where $H$ is the Hellinger distance, not TV (we have $H^2\lesssim TV \lesssim H$). The sample complexity of simple hypothesis testing is captured by Hellinger, not total variation.

I suspect this is tight on an instance-per-instance basis as well, but don't have a proof. Rather, I don't have a proof for adaptive algorithms (those which can choose which $i$ to query, based on previously received samples): for non-adaptive algorithms (which choose ahead of time how many samples to ask from each $i$), then I believe I can prove the lower bound, using elementary properties of Hellinger distance.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Incidentally, the above does not require anything about the distributions being "binary") $\endgroup$
    – Clement C.
    Commented Aug 12, 2022 at 6:50
  • $\begingroup$ Thank you very much! May I have a reference for the upper bound? $\endgroup$
    – gondolf
    Commented Aug 12, 2022 at 7:08
  • $\begingroup$ @gondolf I don't have a simple reference, so I'll be lazy and point to this note I wrote myself: github.com/ccanonne/probabilitydistributiontoolbox/blob/master/… (pdf) $\endgroup$
    – Clement C.
    Commented Aug 12, 2022 at 7:10
  • 1
    $\begingroup$ Thanks! That is very nice. $\endgroup$
    – gondolf
    Commented Aug 12, 2022 at 7:14

You must log in to answer this question.

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