Consider the special case where $|\mathcal X| = 2$ and $k=1$, that is, if you pick $P_1$ the adversary picks $P_2$ and generates a sample $Y^n = (Y_1,\dots,Y_n)$ drawn i.i.d. from $P_2$, and vice versa. Then your question turns into the minimal error in a (Bayesian) binary hypothesis test. By Le Cam's lemma: $$ \inf_{\psi} \mathbb P\big( \psi(Y^n) \neq X\big) = \frac12\big( 1 - \| P_1^{\otimes n} - P_2^{\otimes n}\|_{\text{TV}}\big) $$ If $P_1 \neq P_2$, we have $\| P_1^{\otimes n} - P_2^{\otimes n}\|_{\text{TV}} \to 1$ as $n \to \infty$, i.e., the two product distributions eventually separate and the minimum error probability goes to zero, i.e., you can do consistent hypothesis test. (You shouldn't expect a nonzero lower bound in the limit).
passerby51
- 1.7k
- 9
- 17