# “Elements of Information Theory”: Some (basic) help needed here

I was following the textbook by Cover & Thomas (2006): Elements of Information Theory. (hyperlink is not owned by me)

I have one question that has been irking for me some time. It is regarding that achievability of the Capacity region for multiple access channels (p530-531):

$\mathbf{X_1, X_2}$ are two i.i.d. random $n-$sequences (codes) drawn from a joint distribution $p(x_1, x_2)=p_1(x_1)p_2(x_2)$. These sequences correspond to two indepepndent information sources. These sequences are mapped to an output sequence $\mathbf{Y}$ by a discrete memoryless channel have transition probability mass function $p(y|x_1, x_2)$. Let $A_\epsilon^{(n)}$ the set of jointly-typical $\mathbf{(x_1, x_2, y)}$ sequences. The senders map their input alphabet set $\{1,2,...,2^{nR_1}\}\times\{1,2,...,2^{nR_2}\}$ to the code sequence pair $\mathbf{X_1}(i),\mathbf{X_2}(j)$. The decoder selects that pair $(i, j)$ for which $$(\mathbf{x_1}(i), \mathbf{x_2}(j), \mathbf{y}) \in A_\epsilon^{(n)}.$$ The goal is to bound the probability of error $P_e^{(n)}$ using this typical decoding strategy and eventually to show that it goes to zero as the blocklength $n\rightarrow \infty$.

To this end, define the following event:$$E_{ij}=\{(\mathbf{X_1}(i), \mathbf{X_2}(j), \mathbf{Y}) \in A_\epsilon^{(n)}\}$$

Suppose that the index $(1,1)$ was transmitted. The probability of error in this event is union bounded as$$P_e^{(n)} \leq P(E_{11}^c) + \sum_{i\neq1, j=1}P(E_{i1}) +\sum_{i=1, j \neq 1}P(E_{1j}) + \sum_{i\neq1, j\neq1}P(E_{ij})$$ Consider the second term, here is the problem:

$$P(E_{i1})=P\{(\mathbf{X_1}(i), \mathbf{X_2}(1), \mathbf{Y}) \in A_\epsilon^{(n)}\}=\sum_{(\mathbf{x_1},\mathbf{x_2},\mathbf{y})\in A_\epsilon^{(n)}}p(\mathbf{x_1})p(\mathbf{x_2},\mathbf{y})$$

This last factorization of the joint PDF is something i do not understand. The fact that the sequences $\mathbf{X_1}(i)$ and $\mathbf{X_2}(1)$ are independent is certainly not enough to justify it. I would appreciate if someone can shed a little light on it.

• I have seen this factorization done in other textbooks too, but wihtout any apparent justification. – Iconoclast Jun 29 '15 at 23:12
• Could you at least comment why you down voted the question? – Iconoclast Jun 30 '15 at 8:12
• Are you sure this question is appropriate for this site? What does it have to do with computation? – Tyson Williams Jun 30 '15 at 12:32
• Well it has to do with information theory and information theory is a tag at this site. The MAC channel is the dual to the distributed data compression problem. So maybe not computation but at least compression. – Iconoclast Jun 30 '15 at 13:04
• This site is for research questions in theoretical computer science not questions for which an appropriate tag exists. My guess is that this is why you were down voted. – Tyson Williams Jun 30 '15 at 15:30