Given a set of codewords $\boldsymbol{x}_i$ with $i=1,\cdots,2^{nR}$ where $R$ is the rate of the code. The codewords are transmitted over a Gaussian channel $Y = X + W$ with $X\sim\mathcal{N}(0,A^2)$ and $W\sim\mathcal{N}(0,\sigma^2)$, the decoding proceeds as follows:

Given $\mathbf{y}$, find all jointly typical sequences $\mathbf{x}_i$ such that $(\boldsymbol{x}_i,\boldsymbol{y}) \in A_\epsilon^{(n)}$, where $A_\epsilon^{(n)}$ is the jointly typical set \begin{align} A_\epsilon^{(n)} = \left\{(\boldsymbol{x},\boldsymbol{y}):\left|-\frac{1}{n}\log P\left(\boldsymbol{x},\boldsymbol{y}\right) - H(X,Y)\right|<\epsilon\right\}, \end{align} where $H(X,Y)=\frac{1}{2}\log((2\pi)^2|\boldsymbol{\Sigma}|) + 1$ is the joint entropy with $\boldsymbol{\Sigma}=\begin{bmatrix} A^2 + \sigma^2 & A^2\\ A^2 & A^2\end{bmatrix}$. If there is only one typical sequence, output that as the decoded codeword.

Suppose codeword $\boldsymbol{x}_1$ is transmitted. In Thomas Cover's book, the error probability of two independent sequences $\boldsymbol{x}_i$ and $\boldsymbol{y}$ being jointly typical has been shown by the typicality set argument to be \begin{align} P((\boldsymbol{x}_i,\boldsymbol{y}) \in A_\epsilon^{(n)}, i\neq 1) \leq 2^{-n(I(X,Y)-3\epsilon)} \end{align}

I want to specifically examine this result using concentration inequalities instead of the typicality set argument. But I ran into some trouble when I was deriving it as follows. Since $\boldsymbol{x}_1$ is transmitted, then for any $i\neq 1$, the decoding error is: \begin{align} P\left((\boldsymbol{x}_i,\boldsymbol{y})\in A_\epsilon^{(n)}\right) &= P\left(\left|-\frac{1}{n}\log P\left(\boldsymbol{x}_i,\boldsymbol{y}\right) - H(X,Y)\right|<\epsilon\right). \end{align} Clearly, when $\boldsymbol{x}_i$ is not $i=1$ while $\boldsymbol{y} = \boldsymbol{x}_1+\boldsymbol{w}$, we have \begin{align} P\left(\boldsymbol{x}_i,\boldsymbol{y}\right) = \frac{1}{(2\pi)^{n/2}{|\boldsymbol{\Sigma}'|}^{1/2}} \exp \left( - \frac{1}{2}\begin{bmatrix} \boldsymbol{y}^T & \boldsymbol{x}_i^T \end{bmatrix} {\boldsymbol{\Sigma}'}^{-1} \begin{bmatrix} \boldsymbol{y}\\ \boldsymbol{x}_i \end{bmatrix}\right) \end{align} and (since $\boldsymbol{x}_i$ is independent from $\boldsymbol{y}$ for $i\neq 1$) \begin{align} \boldsymbol{\Sigma}' = \begin{bmatrix} (A^2+\sigma^2)\mathbf{I}_{n\times n} & 0\\ 0 & A^2\mathbf{I}_{n\times n} \end{bmatrix}. \end{align} Therefore, \begin{align} -\frac{1}{n}\log P\left(\boldsymbol{x}_i,\boldsymbol{y}\right) - H(X,Y) &= \frac{1}{2n}\log((2\pi)^{2n} |\boldsymbol{\Sigma}'|) + \frac{1}{2n}\begin{bmatrix} \boldsymbol{y} \\ \boldsymbol{x}_i \end{bmatrix}^T {\boldsymbol{\Sigma}'}^{-1} \begin{bmatrix} \boldsymbol{y}\\ \boldsymbol{x}_i \end{bmatrix} - H(X,Y)\\ &= \frac{1}{2}\log\left(1+\frac{A^2}{\sigma^2}\right) - 1 + \frac{1}{2} \frac{\|\boldsymbol{y}\|^2}{n(A^2+\sigma^2)} + \frac{1}{2} \frac{\|\boldsymbol{x}_i\|^2}{nA^2}\\ &= \underbrace{\frac{1}{2}\log\left(1+\frac{A^2}{\sigma^2}\right)}_{= I(X;Y),\quad \textrm{mutual information between $X$ and $Y=X+W$}} - 1 + \frac{1}{2n} \chi_{2n}^2, \end{align} where $\chi_{2n}^2$ is a chi-squared random variable with $2n$ degrees of freedom. This comes from the fact that $\frac{\|\boldsymbol{y}\|^2}{(A^2+\sigma^2)}\sim\chi_n^2$ and $\frac{\|\boldsymbol{x}_i\|^2}{A^2}\sim\chi_n^2$. Therefore, \begin{align} &P\left(\left|-\frac{1}{n}\log P\left(\boldsymbol{x}_i,\boldsymbol{y}\right) - H(X,Y)\right|<\epsilon\right)\\ &= P\left(\frac{1}{2n} \chi_{2n}^2 -1 + I(X;Y) < \epsilon\right) -P\left(\frac{1}{2n} \chi_{2n}^2 -1 + I(X;Y) <- \epsilon\right)\\ &=P\left(\frac{1}{2n} \chi_{2n}^2 < 1+\epsilon - I(X;Y)\right) -P\left(\frac{1}{2n} \chi_{2n}^2 < 1-\epsilon - I(X;Y)\right)\\ &\leq \exp\left(-\frac{n}{2}\left(I(X;Y)-\epsilon\right)^2\right) - \exp\left(-\frac{n}{2}\left(I(X;Y)+\epsilon\right)^2\right) \end{align} The last equation also follows from the thread "What are the sharpest known tail bounds for $\chi_k^2$ distributed variables?" on here.

The bound I derived is very different, especially that the error exponent is now quadratic in the mutual information $I(X;Y)$, and there is a difference between two terms. Where did I go wrong?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.