Skip to main content
MathOverflow

Return to Question

Fixing log mathop in lower bound
Source Link
user124784
user124784
  • 181
  • 6

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}|},$$$$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.

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.

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.

Added that $X$ is picked uniformly at random.
Source Link
user124784
user124784
  • 181
  • 6

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.

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

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.

Trying to improve explanation of problem setup.
Source Link
user124784
user124784
  • 181
  • 6

Problem description

Suppose we have ana finite alphabet $\mathcal{X}$, where for each letter $X' \in \mathcal{X}$ we have$X \in \mathcal{X}$ indexes into some corresponding distributionfixed set of distributions, $P_{X'} \in \mathcal{P}$$\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For example, you might like to think of each $P_{X'}$$P_{X}$ as a Gaussian with different means.

A letter $X \in \mathcal{X}$ is 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.

Problem description

Suppose we have an alphabet $\mathcal{X}$, where for each letter $X' \in \mathcal{X}$ we have some corresponding distribution $P_{X'} \in \mathcal{P}$. For example, you might like to think of each $P_{X'}$ as a Gaussian with different means.

A letter $X \in \mathcal{X}$ is 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.

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

Adding example for $P_X$ distributions
Source Link
user124784
user124784
  • 181
  • 6
Fixing error probability lower bound. Previously had probability of successful decoding
Source Link
user124784
user124784
  • 181
  • 6
Making KL divergence claim a bit more explicit
Source Link
user124784
user124784
  • 181
  • 6
Specifying iid and adding supporting notation
Source Link
user124784
user124784
  • 181
  • 6
Source Link
user124784
user124784
  • 181
  • 6