0.1 Background

Convergence of random variables

We include some background material for the course. Let us recall some notions of convergence of random variables (RV's).

• A sequence of RV's ${\left\{x_n\right\}}_{n\ge 1}$ converges in probability if $\forall ϵ\ge 0,{lim}_{n\to \infty }supPr\left(\right|x_n-\overline{x}|>ϵ)=0$ . We denote this by $x_n\stackrel{P.}{\to }\overline{x}$ .
• A sequence of RV's ${\left\{x_n\right\}}_{n\ge 1}$ converges to $\overline{x}$ with probability 1 if $Pr\{x_1,x_2,...:{lim}_{n\to \infty }{x}_n=\overline{x}\}=1$ . We denote this by $x_n\stackrel{w.p.1}{\to }\overline{x}$ or $x_n\stackrel{a.s.}{\to }\overline{x}$ .
• A sequence of RV's ${\left\{x_n\right\}}_{n\ge 1}$ converges to $\overline{x}$ in the ${\ell }_p$ sense if $E\left[\right|x_n-\overline{x}{|}^p]\to 0$ . We denote this by $x_n\stackrel{{\ell }_p}{\to }\overline{x}$ .

For example, for $p=2$ we have mean square convergence, $x_n\stackrel{m.s.}{\to }\overline{x}$ . For $p\ge 2$ ,

Therefore, $x_n\stackrel{{\ell }_p}{\to }\overline{x}$ yields $x_n\stackrel{{\ell }_{p-1}}{\to }\overline{x}$ . Note that for convergence in ${\ell }_1$ sense, we have

Typical sequences

The following material appears in most textbooks on information theory (c.f., Cover and Thomas  [link] and references therein). We include the highlights in orderto make these notes self contained, but skip some details and the proofs. Consider a sequence $x=x^n=(x_1,x_2,...,x_n)$ , where $x_i\in \alpha$ , $\alpha$ is the alphabet, and the cardinality of $\alpha$ is $r$ , i.e., $\left|\alpha \right|=r$ .

Definition 1 The type of $x$ consists of the empirical probabilities of symbols in $x$ ,

where $n_x\left(a\right)$ is the empirical symbol count , which is the the number of times that $a\in \alpha$ appears in $x$ .

Definition 2 The set of all possible types is defined as $P_n$ .

Definition 3 A type class $T_x$ contains all $x^{\text{'}}\in {\alpha }^n$ , such that $P_x$ = $P_{x^{\text{'}}}$ ,

Theorem 1 The cardinality of the set of all types satisfies $|P_n{|\le (n+1)}^{r-1}$ .

The proof is simple, and was given in class. We note in passing that this bound is loose, but it is good enough for our discussion.

Next, consider an i.i.d. source with the following prior,

We note in passing that i.i.d. sources are sometimes called memoryless. Let the entropy be

where we use base-two logarithms throughout. We are studying the entropy $H\left(P_x\right)$ in order to show that it is the fundamental performance limit in lossless compression. $\Sigma$ find me

We also define the divergence as

It is well known that the divergence is non-negative,

Moreover, $D(P\parallel Q)=0$ only if the distributions are identical.

Claim 1 The following relation holds,

The derivation is straightforward,

Seeing that the divergence is non-negative [link] , and zero only if the distributions are equal,we have $Q\left(x\right)\le P_x\left(x\right)$ . When $P_x=Q$ the divergence between them is zero, and we have that $P_x\left(x\right)=Q_x=2^{-nH\left(P_x\right)}$ .

The proof of the following theorem was discussed in class.

Theorem 2 The cardinality of the type class $T\left(P_x\right)$ obeys,

Having computed the probability of $x$ and cardinality of its type class, we can easily compute the probability of the type class.