Return to Question

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)$ with $\epsilon=|p_j-q_j|$

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|$

Suppose we know two sets of binary 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$.

It seems one can choose $i=arg max_i |p_i-q_i|$, and sample $r_i$ many times. Is this the best strategy? Is adaptivity helpful?

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)$ with $\epsilon=|p_j-q_j|$