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)}**

**1 - P(F) \leq 1 - \frac{K}{L\epsilon^{2}P_{min}}**

where

Here, we will use Tchebychef inequality:

**P(|\frac{n_{A}}{n} - P(A)| \geq \epsilon) \leq \frac{P(A)[1-P(A)]}{n\epsilon^2}**

Then,

**
P(B_i) = P(|\frac{n_{a_{i}}}{L} - P_{U}(a_i)| > \epsilon P_{U}(a_i))
**

here, we can say that

**
P(B_i) \leq \frac{P_{U}(a_i)[1 - P_{U}(a_i)]}{L[\epsilon P_{U}(a_i)]^2}
**

Simplifying, we have

**
P(B_i) \leq \frac{1 - P_{U}(a_i)}{L \epsilon^{2}P_U(a_i)}
**

**
P(B_{i}) < \frac{1}{L \epsilon^{2}P_{min}}
**

Since

**
P(F) \leq \sum_{i=1}^{K}P(B_i) < \frac{K}{L \epsilon^2 P_{min}}
**

**
(1 - \frac{K}{L \epsilon^2 P_{min}}) . 2^{(1-\epsilon)LH(U)} < M \leq 2^{(1 + \epsilon)LH(U)}
**

**
1 = \sum_{\forall u} P_{U}(u) \geq M . 2 ^{-(1 + \epsilon)LH(U)}
**

since

This gives upper bound

**
M \leq 2 ^ {(1 + \epsilon)LH(U)}
**

Now we are going to prove the lower bound. Total probability of the

**
1 - P(F) \leq M . 2 ^ {-(1 + \epsilon)LH(U)}
**

using property-2, we know that

This gives the lower bound.

**
M > (1 - \frac{K}{L \epsilon^{2}P_{min}}) . 2 ^ {(1 - \epsilon)LH(U)}
**

Now, lets try to look at these results when

- each of these
**\epsilon-**typical sequences has probability equal to**2^{-LH(U)}**. - the total probability of these
**\epsilon-**typical sequences is very nearly 1 - when
**\textbf{L}**is large and**\epsilon**is small, there are roughly**2^{LH(U)}**amount of**\epsilon-**typical sequences**\textbf{u}**.

**Appendix**

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

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

** P(X=0) = a$ and $P(X=1) = 1 - a**

**
E[X] & = (1 - P(X=1)) \times 0 + P(X=1) \times 1 = P(X=1) \\ \\
&= (1 - a) \times 0 + a \times 1 \\
& = a \\
**

likewise, we can calculate the variance as following:

**
\mathrm{Var}[X] & = E[(X-\mu)^2] \\ \\
& = (1 - P(X=1)) \times (0 - P(X=1))^2 + P(X=1) \times (1 - P(X=1))^2\\
& = (1 - a) \times (0 - a)^2 + a \times (1 - a)^2 \\
& = (1 - a) \times (a^2 +a - a^2) \\
& = (1 - a) \times a
**