<p>I was following the textbook by Cover &amp; Thomas (2006): <a href="http://coltech.vnu.edu.vn/~thainp/books/Wiley_-_2006_-_Elements_of_Information_Theory_2nd_Ed.pdf" rel="nofollow"><em>Elements of Information Theory</em></a>. (hyperlink is not owned by me)</p>

<p>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):</p>

<p>$\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$.</p>

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

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

<blockquote>
  <p><strong>$$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})$$</strong></p>
</blockquote>

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

CC BY-SA 3.0
2015-06-29T23:12:49.267Z
I have seen this factorization done in other textbooks too, but wihtout any apparent justification.
Iconoclast
CC BY-SA 3.0
2015-06-30T08:12:00.100Z
Could you at least comment why you down voted the question?
Iconoclast
CC BY-SA 3.0
2015-06-30T12:32:20.130Z
Are you sure this question is appropriate for this site? What does it have to do with computation?
Tyson Williams
CC BY-SA 3.0
2015-06-30T13:04:10.553Z
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
CC BY-SA 3.0
2015-06-30T15:30:34.440Z
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
CC BY-SA 3.0
2015-07-02T02:35:58.647Z
Why do you think it's not justified by the fact that $\mathbf{X}_1(i)$ and $\mathbf{X}_2(1)$ are independent?
Peter Shor 
CC BY-SA 3.0
2015-07-02T02:53:51.337Z
In fact, I think that's exactly why it's justified; $\mathbf{Y}$ is obtained from $\mathbf{X}_1(1)$ and $\mathbf{X}_2(1)$, and so $\mathbf{X}_1(i)$ is independent of the pair of values $(\mathbf{X}_2(1), \mathbf{Y})$.
Peter Shor 
CC BY-SA 3.0
2015-07-02T20:29:29.633Z
Yes I think you are right.
Iconoclast
<it.information-theory>
"Elements of Information Theory": Some (basic) help needed here
Iconoclast
# "Elements of Information Theory": Some (basic) help needed here

(Asked by: username_0 on 2015-06-29)

I was following the textbook by Cover & Thomas (2006): [*Elements of Information Theory*](http://coltech.vnu.edu.vn/~thainp/books/Wiley_-_2006_-_Elements_of_Information_Theory_2nd_Ed.pdf). (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.

**Tags:** it.information-theory
> **Comments:**
> **username_0**: I have seen this factorization done in other textbooks too, but wihtout any apparent justification.  
> **username_0**: Could you at least comment why you down voted the question?  
> **username_1**: Are you sure this question is appropriate for this site? What does it have to do with computation?  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_2**: Why do you think it's not justified by the fact that $\mathbf{X}_1(i)$ and $\mathbf{X}_2(1)$ are independent?  
> **username_2**: In fact, I think that's exactly why it's justified; $\mathbf{Y}$ is obtained from $\mathbf{X}_1(1)$ and $\mathbf{X}_2(1)$, and so $\mathbf{X}_1(i)$ is independent of the pair of values $(\mathbf{X}_2(1), \mathbf{Y})$.  
> **username_0**: Yes I think you are right.  

---

## 0 answers

