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

• What does for each letter we have a corresponding distribution mean? A single letter has a probability, not a full distribution. Are you talking about multiple alphabets? What is the alphabet? Is it finite? Jan 27, 2020 at 21:42
• Sorry, it is a little unclear. I'll try to explain here and then improve the wording in the question. Roughly, the adversary produces some random samples that depend on the letters they chose. There is a single finite alphabet, $\mathcal{X}$. You can think of each $x \in \mathcal{X}$ as parameterizing a distribution $P(\cdot|x)$. The distributions can be arbitrary, though we will likely need to assume that all pairs of distributions have bounded KL divergence. You might like to think of the $P$ distributions as Gaussians with different means. Jan 27, 2020 at 21:48
• OK, and it also seems that you have $P(x|x)=0,$ for each of the conditional distributions, am I right? Jan 27, 2020 at 22:58
• I'm not sure I understand, but I think perhaps I didn't explain it clearly enough. The $P(\cdot|x)$ distributions could be defined as a density on the reals, while the alphabet itself is finite. The alphabet can be thought of as indexing into some fixed set of distributions $\{P_1,\ldots,P_{|\mathcal{X}|}\}$. Jan 27, 2020 at 23:03
• I was confused, I understand now, I think. Jan 27, 2020 at 23:32

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.

• Thanks! It is nice to see that you can get asymptotic results with total variation here. However, I want to emphasize that we should not consider this special case to be a general counter example. This same argument can be applied to the general $k = |\mathcal{X}| - 1$ setting, and lines up with my predicted error bound in the question. I am especially interested in settings where $k < |\mathcal{X}| - 1$ and a nonzero lower bound is expected (as proved with the data processing inequality). Jan 28, 2020 at 19:27
• @user124784, I have added some thoughts on the general case. I think in most cases you should expect a vanishing minimum probability of error. Jan 29, 2020 at 3:08
• Actually, I made some more comments. The general case seems to exactly reduce to the case $k = |\mathcal X|-1$. See my calculation before the example. Jan 29, 2020 at 6:53
• I'm pretty sure there is a mistake here. You have assumed that the $Y_i$'s are conditionally independent given X, but this is not the case. The adversary samples only a single set $S$ which is used for all $Y_i$ samples. My partial answer uses the data processing inequality to show that there will be a non-zero error --- no matter how large $n$ is we cannot exceed the information stored in $S$ on $X$. I will try to clarify this today by adopting your improved notation into the main question. Jan 29, 2020 at 13:04
• Yes, sorry I think my use of terminology was slightly off. I want to quantify the closeness to the bound for a given $n$. I'll have to do some related reading and see where I end up. Thanks for the help! If you have any other thoughts, please do let me know! Feb 3, 2020 at 3:18

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