Jointly typical sequences

In this article, we discuss an extension of typical sets to jointly distributed random variables.

Definition

Let $(x^{n},y^{n})$ be an $n$-sequence of pairs drawn from the set ${\mathcal {X}}\times {\mathcal {Y}}$. For a fixed $\epsilon >0$, $(x^{n},y^{n})$ is said to be jointly typical with respect to random variables $X$ and $Y$ if the three conditions below are all satisfied:

• $|-{\frac {1}{n}}\log p(x^{n})-H(X)|<\epsilon$
• $|-{\frac {1}{n}}\log p(y^{n})-H(Y)|<\epsilon$
• $|-{\frac {1}{n}}\log p(x^{n},y^{n})-H(X,Y)|<\epsilon$

From the definition, we see that the notion of joint typicality is stronger than the previous formulation. If we only needed the sequence of pairs $(x_{i},y_{i})$ for $i=1,2,\cdots ,n$, we could simply invoke the Asymptotic Equipartition Property with the random variable $X$ replaced by $(X,Y)$. The first two properties further constrain the component sequences $(x_{1},x_{2},\cdots ,x_{n})$ and $(y_{1},y_{2},...,y_{n})$ beyond the earlier requirement of AEP. Altogether, these three properties guarantee us that sufficiently long sequences behave near their true joint and marginal distributions with very high probability.

Example: binary symmetric channel

For our example, we consider the sequence of input-output pairs $(x_{i},y_{i})$ of a binary symmetric channel (BSC). A BSC takes in inputs from the input alphabet ${\mathcal {X}}=\{0,1\}$ and produces outputs which also belong to the same alphabet ${\mathcal {Y}}=\{0,1\}$. If we write the joint distribution as $p(X,Y)=p(X)p(Y|X)$, we can generate the pairs by first generating a value $x_{i}$ using $p(X)$, and then drawing a value $y_{i}$ using the conditional distribution $p(Y|X=x_{i})$. For the BSC, $p(Y|X)=p_{e}$ if $Y\neq X$ and $p(Y|X)=1-p_{e}$ if $Y=X$, where $0\leq p_{e}\leq 1/2$ is called the crossover probability.

In our calculation, the input $X$ is assumed to be distributed such that $P(X=1)=2/3$, and the crossover probability is set to $p_{e}=1/10$. The typicality threshold is set at $\epsilon =0.01$. From $p(X)$ and $p(Y|X)$, we obtain the following joint distribution:

	$Y=0$	$Y=1$
$X=0$	3/10	1/30
$X=1$	1/15	3/5

The table below shows the probability of producing a jointly typical sequence as the blocklength increases.

$n$	$\mathbb {P} \left(X^{n}\in A_{\epsilon }^{(n)}\right)$
50	0
100	0.003050
500	0.155243
1000	0.317690
5000	0.703099
10000	0.818271
50000	0.982649

To produce the values in the table, we enumerate the relatively frequencies of pairs that will result in a typical sequence for a fixed $n$. In our example, you can think of this a "profile" consisting of four numbers, $(k_{00},k_{01},k_{10},k_{11})$, where $k_{ij}$ is the number of $(i,j)$ pairs in the sequence for $i,j\in \{0,1\}$. At $n=100$, there is only one such profile: $(k_{00},k_{01},k_{10},k_{11})=(30,3,7,60)$. Using the multinomial theorem, we can calculate the probability of this profile as

${\frac {100!}{30!3!7!60!}}(3/10)^{30}(1/30)^{3}(1/15)^{7}(3/5)^{60}\approx 0.003050$

For larger $n$, the number of profiles increases and concentrates the total probability weight near the underlying joint distribution $p(X,Y)$.

Important Properties

Fix $\epsilon >0$ can let $A_{\epsilon }^{(n)}$ be the typical set of pairs of $n$-sequences $X^{n}$ and $Y^{n}$.

• The probability of that an $n$-sequence drawn i.i.d using $p(X,Y)$ is $\epsilon$-typical approaches 1 for sufficiently large n.
• The number of elements in $A_{\epsilon }^{(n)}$ is at most $2^{n(H(X,Y)+\epsilon }$.
• If ${\tilde {X}}^{n}$ and ${\tilde {Y}}^{n}$ are independent but with the marginal probabilities $p(x^{n})$ and $p(y^{n})$, then for sufficiently large $n$, $(1-\epsilon )2^{-n(I(X;Y)+3\epsilon )}\leq \mathbb {P} (({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\epsilon }^{(n)})\leq 2^{-n(I(X;Y)-3\epsilon )}$

The first two properties are direct extensions of the typical set property for a single random variable $X$. Here, we simply replaced $X$ by $(X,Y)$.

The third property is more meaningful in the context of data transmission and is in fact used in the proof of Shannon's channel coding theorem. We can interpret $Y^{n}$ as the channel output corresponding to the channel input $X^{n}$. In most practical channels, $X^{n}$ and $Y^{n}$ are not independent. Under the lens of data transmission, ${\tilde {X}}^{n}$ can be interpreted as a codeword that does not correspond to the received codeword $Y^{n}$, i.e., it is a potential erroneous codeword. The bounds in the third property tells us that the "cleaner" a channel is (high $I(X;Y)$), the less likely we are to make the mistake that ${\tilde {X}}^{n}$ was used to transmit $Y^{n}$. With a clean channel, essentially we are saying that the transmitted and received codewords are "entangled," and the degree of entanglement gets stronger if we use longer blocklengths.