The Notebook

**Typicality**

**
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
**

**
1,0,1,0,1,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0
**

**
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
**

The first sequence is a all one sequence. The second one has 14 zeros and 6 ones, and the third is a all zero sequence.

Probability of occurrence of the sequences are:

**\frac{1}{4}^{20}$**, **\frac{1}{4}^{20}\times3^{14}**, **\frac{1}{4}^{20}\times3^{20}**

All zero and all one sequence are very unlikely to come out of this source because we have been given that:

**P_{U}(0) = \frac{3}{4},\:\: P_{U}(1) = \frac{1}{4}**

If we take large enough block size it is likely that we should get 0 three fourth of time, and we should get 1 one fourth of time.

If we had

The second sequence has 14 zeros and 6 ones. Roughly if we take large enough bits, I expect

Now, we will formally define what is a typical sequence and then we will show some properties of a typical sequence.

- Let
**\textbf{U}**denote an output sequence of length**\textbf{L}**emitted a K-ary DMS and**P_{U}(u)**is the output probability distribution. - Let
**$n_{ai}(u)**denotes the number of occurence of the letter**a_{i}**in the sequence**\textbf{u}** - Let
**\textbf{u} = [$u_{1}$, $u_{2}$, ..., $u_{L}**] denote possible values of, i.e.**u_{j} = \{{a_{1}, a_{2}, ..., a_{K}}\}**for**1 \leq j \leq L**.

**(1 - \epsilon)P_{u}(a_{i}) \leq \frac{n_{ai}(\textbf{u})}{L} \leq (1 + \epsilon) P_{u}(a_{i})$, $1 \leq i \leq K**

Please note

**Properties**

**2^{-(1+\epsilon)LH(U)} \leq P_{U}(\textbf{u}) \leq 2^{-(1-\epsilon)LH(U)}**

**P_{U}(\textbf{u}) = \prod\limits_{j=1}^L P_{U}(u_{j})**

So, since this is a K-ary source, it will emit

So, let us say

Consequently, we can write:

**P_{U}(\textbf{u}) = \prod_{j=1}^LP_{U}(u_{j}) = \prod_{i=1}^K[P_{U}(a_{i})]^{n_{ai}(\textbf{u})}**

Here, we can say that:

**P_{U}(\textbf{u}) = \prod_{i=1}^K[P_{U}(a_{i})]^{n_{ai}(\textbf{u})} = \prod_{i=1}^K[P_{U}(a_{i})]^{LP_{U}(a_{i})} \geq \prod_{i=1}^K[P_{U}(a_{i})]^{(1+\epsilon)LP_{U}(a_{i})}**

since raising a power of a number in between 0 and 1 (which is probability of

Equivalently (see logarithmic exchange part below),

**P_{U}(\textbf{u}) \geq \prod_{i=1}^K2^{(1+\epsilon)LP_{U}(a_{i})\log_{2}P_{U}(a_{i})}**

Simplifying we get,

**P_{U}(\textbf{u}) \geq 2^{(1+\epsilon) L \sum\limits_{i=1}^KP_{U}(a_{i})\log_{2}P_{U}(a_{i})}**

Hence,

**P_{U}(\textbf{u}) \geq 2^{-(1+\epsilon)LH(U)}**

Similar arguments can be used to prove

**P_{U}(\textbf{u}) \leq 2^{-(1-\epsilon)LH(U)}**

**Appendix**

** $b^{\log_{b}(x)} = x$**

** \log_{b}(x) = y \Leftrightarrow b^{y} = x**