## 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.

2more comments