0
$\begingroup$

I am reading Information Theory, Inference and Learning Algorithms by David MacKay. It is available free of charge online: http://www.inference.org.uk/mackay/itila/book.html (official site, not pirated copy).

My question is to solve Exercise 25.1. It is marked as one of the easier ones. I think I'm just missing some fundamental understanding. Assistance would be enormously appreciated!

I quote the desired section, slightly paraphrased for abbreviation. It is from Section 25.1 on Page 324 (Page 336 of my pdf).


A codeword $t$ is selected from a code with codewords which form a subset of $\{0,1\}^N$ and transmitted over a noisy channel and $y$ is received. We have $$ P(t \mid y) = P(y \mid t) P(t) / P(y) $$ by Bayes's theorem. Assume that he channel is memoryless. Thus $$ P(y \mid t) = \prod_{n=1}^N P(y_n \mid t_n). $$

For example, if the channel is a Gaussian channel with transmissions $\pm x$ and additive noise of standard deviation $\sigma$, then the probability density of the received signal $y_n$ in the two cases $t_n \in \{0,1\}$ are given as follows: $$ \begin{aligned} P(y_n \mid t_n = 1) &= (2 \pi \sigma^2)^{-1/2} \exp\bigl( - (y_n - x)^2 / (2 \sigma^2) \bigr); \\ P(y_n \mid t_n = 0) &= (2 \pi \sigma^2)^{-1/2} \exp\bigl( - (y_n + x)^2 / (2 \sigma^2) \bigr). \end{aligned} $$ [Here we are interpreting $t_n = 0$ as "send $-x$" and $t_n = 1$ as "send $+x$" (plus noise).] From the point of view of decoding, all that matters is the likelihood ratio: $$ \frac {P(y_n \mid t_n = 1)} {P(y_n \mid t_n = 0)} = \exp\biggl( \frac{2 x y_n}{\sigma^2} \biggr). $$

Exercise. Show that from the point of view of decoding a Gaussian channel is equivalent to a time-varying binary symmetric channel with a known noise level $f_n$ which depends on $n$.

For further reference, Section 11.2 (Page 179 of book and 191 of my pdf) discusses inferring the input from a Gaussian channel. It's not so helpful for this, though. I do not see what is time-varying about this.


PS Multiple different SE networks seemed appropriate for this: maths, cstheory, stats. I picked this one but if a mod wants to move it, no objection from me.

$\endgroup$
8
  • $\begingroup$ You have done the work. From the decoder POV, there are only four possible cases; two of which constitute correct detection of $\pm x$, and two result in error, i.e., a binary symmetric channel. The probabilities change over $n$, so it is time variant. You already have the results. :) $\endgroup$
    – Arash
    Jan 18 '21 at 16:04
  • $\begingroup$ Thanks, @Arash, for your response. I am happy with the binary symmetric part. The bit that I don't see is why it's time-varying It seems to me that one always uses the same Normal distribution and thus always has the same likelihood ratio... there is no real $n$-dependence in the final formula: just replace $y_n$ with some other generic letter. Oh, is here $y_n$ supposed to be some given data, not a function? The book (and statisticians in general, I feel) is incredibly sloppy regarding this notation and it confuses me often! $\endgroup$
    – Sam OT
    Jan 18 '21 at 16:16
  • $\begingroup$ Tell you what, I'll write my own answer to the question, then would you confirm if it's correct? :-) $\endgroup$
    – Sam OT
    Jan 18 '21 at 16:17
  • $\begingroup$ Ok @Arash, I have written an answer. Perhaps you would be willing to check it for me? I'm not really sure how to convert the likelihood ratio to the noise... $\endgroup$
    – Sam OT
    Jan 18 '21 at 16:27
  • $\begingroup$ The optimum decision making is based on MAP (maximum a posteriori probability) which requires the a priori knowledge. In order to fully characterize the equivalent binary symmetric channel, that prior knowledge ($P(y|t)$) should be taken into account, which improves over $n$, i.e., the more you have samples, the more precisely you can evaluate the prior. In that sense, receiver's understanding of the binary channel (not the Gaussian channel) is time-variant. Right now, you are using a Maximum Likelihood, which is a technique inherently ignorant of the prior probability. That's how I c it:) $\endgroup$
    – Arash
    Jan 18 '21 at 21:26
1
$\begingroup$

You are right. It is not time-variant. I just checked MacKay's Example 25.1 and in that configuration, such an assertion is wrong. I just paraphrase what you have already established:

Assume that at instance $n$, the transmitter sends $s_n=+x$ for $t_n=1$, and $s_n=-x$ for $t_n=0$. The receiver gets $y_n=s_n+\nu$, where $\nu \sim \mathcal{N}(0, \sigma^2)$, so, $y_n \sim \mathcal{N}(s_n, \sigma^2)$. The ML decoder is simply: $$ \exp\left(\frac{2xy_n}{\sigma^2}\right) \overset{+x}{\underset{-x}{\gtrless}} 1 \Longrightarrow y_n \overset{t_n=1}{\underset{t_n=0}{\gtrless}} 0 $$

that is, it decides based on the sign of $y_n$. Now, $$\begin{align*} \Pr\{\text{Error}|t_n=1\} & = \Pr\{y_n<0|t_n=1\}=\Pr\{y_n<0|s_n=+x\} = Q\left(\frac{x}{\sigma}\right) \\ \Pr\{\text{Correct}|t_n=1\} & = \Pr\{y_n>0|t_n=1\}=\Pr\{y_n>0|s_n=+x\} = 1-Q\left(\frac{x}{\sigma}\right) \\ \Pr\{\text{Error}|t_n=0\} & = \Pr\{y_n>0|t_n=0\}=\Pr\{y_n>0|s_n=-x\} = Q\left(\frac{x}{\sigma}\right) \\ \Pr\{\text{Correct}|t_n=0\} & = \Pr\{y_n<0|t_n=0\}=\Pr\{y_n<0|s_n=-x\} = 1-Q\left(\frac{x}{\sigma}\right) \\ \end{align*}$$

which describes a time-invariant binary symmetric channel.

$\endgroup$
5
  • $\begingroup$ Set $x := 1 =: \sigma^2$. Assume a uniform prior on $t$. Suppose I see $y_1 = 1/1000$. I decode it to $s_1 = +x$, ie $t_1 = 1$ but know that it's basically 50:50 whether this is correct or not. Suppose I see $y_2 = 10000000$. I again decode this to $s_2 = +x$, ie $t_2 = 1$. I now know that the odds that I'm right is roughly $e^{20000000} : 1$---ie almost certain. I think MacKay is saying, "look at your full sequence $y = (y_1, ..., y_N)$; now what is the error probability?" This is calculating $\Pr(\text{error} \mid y_n)$, rather than $\Pr(\text{error} \mid t_n)$. This way it is time varying $\endgroup$
    – Sam OT
    Jan 19 '21 at 12:42
  • $\begingroup$ I thought that too. Then again I read the MacKay's text, and I'm afraid it was just plain wrong. I don't know much, but that's what I thought. $\endgroup$
    – Arash
    Jan 19 '21 at 14:06
  • $\begingroup$ Hmm :/ -- my impression from his book in general suggests that he did mean that the sequence $y$ is observed, giving rise to the time-inhomogeneity that I suggest. But it certainly is far from clear. Perhaps this is another section to go in your "evidence for why the book is bad" collection! $\endgroup$
    – Sam OT
    Jan 19 '21 at 14:32
  • $\begingroup$ Perhaps! But seriously, I prefer Thomas Cover's Elements of Information Theory, except for the 2nd chapter, which I prefer Robert Ash's. Also Mehryar Mohri's Foundations of Machine Learning, specially chapters 2, 3, 12, 13, and Appendix E, which gives a boost to information theory in ML literature. $\endgroup$
    – Arash
    Jan 23 '21 at 1:03
  • $\begingroup$ Thank you for the suggestions. I was mostly reading for the introduction to Neural Networks. I'm more than 300 pages in, just about to get to the NN part! I always saw CT as more of a reference. A bit long to read Cover to Cover (pun intended!). I'll certainly check out the other book you reference, thanks! $\endgroup$
    – Sam OT
    Jan 23 '21 at 9:29
0
$\begingroup$

Arash presents one possibility. Here is another. It gives a completely different conclusion. MacKay's text appears ambiguous to which is intended.


Although it looks like a variable, here $y = (y_n)_{n \in [N]}$ is a single given realisation---the expression $$ \frac {P(y_n \mid t_n = 1)} {P(y_n \mid t_n = 0)} = \exp\biggl( \frac{2 x y_n}{\sigma^2} \biggr) $$ is not to be thought of as expressing a function of $y_n$. Rather, let $q_n(b) := P(y_n \mid t_n = b)$---this is a function of the bit $b \in \{0,1\}$. The likelihood ratio is saying that $$ \frac{q_n(1)}{q_n(0)} = \exp( 2 x y_n / \sigma^2 ). $$ Thus it is a binary symmetric channel with time-varying flip-probability. Converting this into the flip parameter $f_n$ requires knowledge of the prior. For example, if the prior is uniform, then I think $$ \frac{1 - f_n}{f_n} = \frac{q_n(1)}{q_n(0)}, \quad\text{ie}\quad f_n = \frac1{1 + q_n(1)/q_n(0)}. $$ I could be mistaken with this final claim, however.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.