Convergence of random variables

• In probability (convergence in probability): $P(|X_n-X|\leq\epsilon)\rightarrow 1$
• In mean square: $E(X_n-X)^2\rightarrow 0$
• With probability 1 (almost surely convergence): $P(\lim_{n\rightarrow\infty}X_n=X)=1$
• (2)$\rightarrow$(1), (3)$\rightarrow$(1)
• Law of Large Numbers: $X_1,\cdots,X_n\sim p(x)$
  • Strong: $P(\lim_{n\rightarrow\infty} \overline X_n=E(X_1))=1$
  • Weak: $\overline X_n\rightarrow E(X_1)$ in probability

Asymptotic Equipartition Property

• AEP: $X_1,X_2,\cdots X_n$ are i.i.d. $\sim p(x)$, then $-\frac{1}{n}\log p(X_1,X_2,\cdots, X_n)\rightarrow H(X)$
  • $2^{-nH(X)+\epsilon}\leq p(X_1,X_2,\cdots,X_n)\leq 2^{-n(H(X)-\epsilon)}$
• typical set $A_\epsilon^{(n)}$ is the set of sequences $(x_1,\cdots, x_n)\in\mathcal{X}^n$ with property $2^{-nH(X)+\epsilon}\leq p(X_1,X_2,\cdots,X_n)\leq 2^{-n(H(X)-\epsilon)}$
  • $P(A_\epsilon^{(n)})\geq 1-\epsilon$ for $n$ sufficiently large (The typical set has probability nearly 1)
  • $|A_\epsilon^{(n)}|\leq 2^{n(H(X)+\epsilon)}$ (All elements are nearly qeuiprobable)
  • $|A_\epsilon^{(n)}|\geq (1-\epsilon)2^{n(H(X)-\epsilon)}$ (elements nearly $2^{nH}$)
• High Probability Set: $B_\delta^{(n)}\subset\mathcal{X}^n$ be the smallest set with $P(B_\delta^{(n)})\geq 1-\delta$
  • if $P(B_\delta^{(n)})\geq 1-\delta$, then $\frac{1}{n}\log|B_\delta^{(n)}|>H-\delta’$ for n sufficiently large
• Data Compression
  • Encode: $E(\frac{1}{n}l(X^n))\leq H(X)+\epsilon$
    • $n\log|\mathcal{X}|+1+1$ for $(A_\epsilon^{(n)})^c$
    • $n(H+\epsilon)+1+1$ for $A_\epsilon^{(n)}$
  • For any scheme with rate $r<H(X),P_e\rightarrow 1$

Joint Typicality

Jointly typical sequences $A_\epsilon^{(n)}$

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

$X^n\in A_\epsilon^{(n)}, Y^n\in A_\epsilon^{(n)}$ cannot imply $(X^n, Y^n)\in A_\epsilon^{(n)}$

Three Properties:

• $Pr((X^n,Y^n)\in A_\epsilon^{(n)})\rightarrow 1$ as $n\rightarrow \infty$
• $|A_\epsilon^{(n)}|\leq 2^{n(H(X,Y)+\epsilon)}$
• If $(\widetilde{X}^n, \widetilde{Y}^n)\sim p(x^n)p(y^n)$, then $(1-\epsilon)2^{-n(I(X,Y)+3\epsilon)} \leq Pr((\widetilde{X}^n, \widetilde{Y}^n)\in A_\epsilon^{(n)})\leq 2^{n(I(X,Y)-3\epsilon)}$

The probability of joint AEP: $2^{-nI(X;Y)}=\frac{2^{nH(X,Y)}}{2^{nH(X)}2^{nH(Y)}}$