Lower bounding decoding error in a noisy adversarial channel Problem description
Suppose we have a finite alphabet $\mathcal{X}$, where each letter $X \in \mathcal{X}$ indexes into some fixed set of distributions, $\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For example, you might like to think of each $P_{X}$ as Gaussian with different means.
A letter $X \in \mathcal{X}$ is picked uniformly at random and sent across a channel, in which an adversary picks $k$ random letters in $\mathcal{X}$ (excluding the true $X$) to form a set $U = \{ X_1, \ldots, X_k\}$, and sends on $N$ random samples, drawn i.i.d. from the mixture distribution $\bar{P}_U = \frac{1}{K}(P_{X_1} + \ldots + P_{X_k})$, denoted $Y_1,\ldots,Y_N$ (or $Y^N$ collectively). What is the minimum probability of error that the decoding receiver can achieve?
Target solution
As $n \rightarrow \infty$, we would expect the probability of error to be lower-bounded by $1 - \frac{1}{|\mathcal{X}| - K}$, but I'm having a hard time proving that this is the case. Ideally, we would find a tight non-asymptotic bound.
My attempt at a proof
It feels like this should be a simple application of Fano's inequality. Given an estimator $\hat{X}$ for $X$, we have,
$$P(\hat{X} \neq X) \geq 1 - \frac{I(X;Y^N) + 1}{\log |\mathcal{X}|},$$
where $I(X;Y^N)$ denotes the mutual information between $X$ and $Y^N$. I haven't been able to do better than using $I(X;Y^N) \leq nI(X; Y)$, and bounding the mutual information in terms of the maximum pair-wise KL divergence, $\max_{X,X' \in \mathcal{X}}\mathrm{KL}(P_{X}\Vert P_{X'})$. Unfortunately, this lower-bounds the error by zero as $n$ grows sufficiently large.
 A: 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).

For the general case, it is enough to consider how small $\mathbb P(\psi(U) \neq X)$ can be made, where $\psi : \binom{[m]}{k} \to [m]$. That is, we want the optimal decision rule
$$
\psi^* = \arg\min_\psi \mathbb P(\psi(U) \neq X).
$$
Here $\binom{[m]}{k}$ is the set of all subsets of $[m] = \{1,2,\dots,m\}$ of size $k$.
This is a Bayesian decision problem, with a 0-1 loss. It is well-known that the optimal rule minimizes the posterior risk (see Lehaman and Casella, Theorem 1.1. in Chap 4, p.228), i.e.
\begin{align}
\psi^*(u) &= \arg \min_{j \in [m]} \mathbb P( j \neq X\mid U= u) \\
&= \arg \max_{j \in [m]} \mathbb P( j = X\mid U= u) \\
\end{align}
We have
\begin{align*}
\mathbb P( j = X\mid U= u) =
\begin{cases}
\frac{1}{m-k} & j \notin u \\
0 & j \in u.
\end{cases}
\end{align*}
For any $u$, an optimal decision rule can pick any $j \notin u$ to maximize the posterior risk (the rule is not unique). Let $j(u)$ be the smallest element not in $u$. Then $\psi^*(u) = j(u)$ is an optimal rule. For this rule, we have
$$
\mathbb P(\psi^*(u) = X \mid U = u) = \frac{1}{m-k}.
$$
Taking the expectation (and using smoothing), it follows that
$$
\mathbb P(\psi^*(U) = X) = \frac{1}{m-k}.
$$
Thus,
$$
\mathbb P(\psi(U) \neq X) \ge \mathbb P(\psi^*(U) \neq X) = 1-\frac1{m-k}.
$$

To see why the above is enough, note that the error based on $Y^n$ is bounded by the problem where we have access to both $Y^n$ and $U$:
$$
\min_\phi \mathbb P(\phi(Y^n) \neq X) \ge \min_{\widetilde\psi} \mathbb P(\widetilde\psi(Y^n,U) \neq X).
$$
The optimal solution of the latter problem is again the minimizer of the posterior loss
\begin{align*}
\widetilde\psi^*(Y^n,U) &= \arg\min_{j \in [m]} \mathbb P(  j \neq X \mid Y^n, U) \\
&=\arg\min_{j \in [m]} \mathbb P(  j \neq X \mid U)
\end{align*}
where the second line is by the Markov property. It follows that the  problem with access to $Y^n$ and $U$ has the same solution as the case where we only observe $U$ and 
$$
 \min_{\widetilde\psi}  \mathbb P\big(\widetilde \psi(Y^n,U) \neq X\big) = \min_\psi \mathbb P\big( \psi(U) \neq X\big) =1-\frac{1}{m-k}.
$$

The above argument in fact shows that whenever $X \to U \to Y^n$ (i.e., $X$ is independent of $Y^n$ given $U$), then
$$
\min_{\phi} \mathbb P \big(\phi(Y^n) \neq X\big) \ge \min_{\psi} \mathbb P \big(\psi(U) \neq X\big),
$$
which seems to be Bayesian decision-theoretic version of the data processing inequality.
A: I managed to get a partial solution to this.
Note that the described procedure forms a Markov chain $X \rightarrow U \rightarrow Y^n$. Thus, by the data processing inequality, we must have,
$$I(X;Y^n) \leq I(X; U).$$
The latter has no dependence on $n$, and can be computed in closed form. I believe we have,
$$I(X; U) = \log \frac{|\mathcal{X}|}{|\mathcal{X}| - k}.$$
This doesn't quite match what I expected in the lower bound, due to the log-factors.
In any case, I would like to capture this behavior through a dependence on $n$. I would expect the data processing inequality to be tight in the limit of $n \rightarrow \infty$ (under some reasonable assumption on the $P$s).
