Skip to main content
3 of 3
added 1 character in body
Clement C.
  • 1.4k
  • 1
  • 13
  • 37

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.

Clement C.
  • 1.4k
  • 1
  • 13
  • 37