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.



Lower bounding decoding error in a noisy adversarial channel
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](https://www.dcpehvpm.org/E-Content/Stat/E%20L%20Lehaman.pdf)), 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.


