6.441-3 Different types of convergence, AEP & typical set

LECTURE 3 Convergence and AsymptoticEquipartition PropertyLast time: Convexity and concavity • Jensen’s inequality • Positivity of mutual information• Data processing theorem • Fano’s inequality • Lecture outline Types of convergence • Weak Law of Large Numbers • Strong Law of Large Numbers• Asymptotic Equipartition Property • Reading: Scts. 3.1-3.2. Types of convergenceRecall what a random variable is: a mappiin from its set of sample values Ω ontoR X :Ω �→ RξX(ξ)→In the cases we have been discussing, Ω = X and we map onto [0, 1] Types of convergenceSure convergence: a random sequence• X1,... converges surely to r.v. X if ∀ξ ∈Ω the sequence Xn(ξ) converges to X(ξ) as n →∞ Almost sure convergence (also called con₭ vergence with probability 1) the random sequence converges a.s. (w.p. 1) to X if the sequence X1(ξ),... converges to X(ξ) for all ξ except possibly on a set of Ω of probability 0 Mean-square convergence: X1,... con₭ verges in m.s. sense to r.v. X if limn→∞ EXn[|Xn − X|2] → 0 Convergence in probability: the sequence• converges in probability to X if ∀�> 0limn→∞ Pr[|Xn − X| >�] → 0 Convergence in distribution: the sequence • converges in distribution if the cumulatiiv distribution function Fn(x)= Pr(Xn ≤ x) satisfies limn→∞ Fn(x) FX(x) at all → x for which F is continuous. Relations among types of convergenceVenn diagram of relation: Weak Law of Large Numbers X1,X2,... i.i.d. finite mean µ and variance σ2 X1+ + XnMn = ··· n E[Mn]= • Var(Mn)= • σ2 Pr(|Mn − µ|≥ �) ≤ n�X 2 Weak Law of Large NumbersConsequence of Chebyshev’s inequality: Randdo variable X σ2= � (x − E[X])2PX(x)X x∈X σ2 X ≥ c 2 Pr(|X − E[X]|≥ c) σ2 Pr(|X − E[X]|≥ c) ≤ cX 2 1 Pr(|X − E[X]|≥ kσX) ≤ k2 Strong Law of Large NumbersTheorem: (SLLN) If Xi are IID, and EX[X] <||∞, then X1+ + XnMn = ··· EX[X], w.p.1. n → AEPIf X1, . . . , Xn are IID with distribution PX, then 1−log(PX1,...,Xn(x1, . . . , xn)) → H(X) in prob­ ability Notation: Xij =(Xi, . . . , Xj) (if i = 1, generaall omitted) Proof: create r.v. Y that takes the value yi = − log(PX(xi)) with probability PX(xi) (note that the value of Y is related to its probability distribution) we now apply the WLLN to Y AEP1 − n log(PXn(xn)) 1 n= � log(PX(xi))−ni=1 1 n= � yi n i=1 using the WLLN on Y n 1 �ni=1 yi EY [Y ] in probability → EY [Y ]= −EZ[log(PX(Z))] = H(X) for some r.v. Z identically distributed with X Consequences of the AEP: the typicalsetDefinition: A� (n) is a typical set with respect to PX(x) if it is the set of sequences in the set of all possible sequences xn n with∈Xprobability: 2−n(H(X)+�) ≤ PXn (xn) ≤ 2−n(H(X)−�) equivalently 1 H(X) − � ≤− n log(PXn (xn)) ≤ H(X)+ � As n increases, the bounds get closer togetther so we are considering a smaller range of probabilities We shall use the typical set to describe a set with characteristics that belong to the majority of elements in that set. Note: the variance of the entropy is finite� Consequences of the AEP: the typicalsetWhy is it typical? AEP says ∀�> 0, ∀δ> 0, ∃n0 such that ∀n>n0 Pr(A� (n)) ≥ 1 − δ (note: δ can be �) How big is the typical set? 1= � PXn (xn) xn∈X n � PXn (xn)≥ xn∈A(n) ≥ � 2−n(H(X)+�) xn� (n)∈A|� (n)|2−n(H(X)+�)= A⇒|A� (n)|≤ 2n(H(X)+�) � Pr(A� (n)) ≥ (1 − �) ⇒ 1 − � ≤ � (n) PXn (xn) xn∈A� ≤|A� (n)|2−n(H(X)−�) ⇒|A(n)|≥ 2n(H(X)−�)(1 − �) Visualize: Consequences of the AEP: using thetypical set for compressionDescription in typical set requires no more than n(H(X)+ �) + 1 bits (correction of 1 bit because of integrality) (n)C Description in atypical set A� requires no more than n log(|X |) + 1 bits Add another bit to indicate whether in A� (n) or not to get whole description Consequences of the AEP: using thetypical set for compressionLet l(xn) be the length of the binary de⊭ PXn (xn)(n(H(X)+ δ) + 2) scription of xn ∀� > 0, ∃n0 s.t. ∀n > n0, EXn[l(Xn)] = � PXn (x n) l(x n) + � PXn (x n) l(x n) xn∈Aδ (n) � xn∈Aδ (n)C (n)xn∈Aδ + � PXn (xn)(n log(|X |) + 2) (n)C xn∈Aδ = nH(X)+ n� +2 for δ small enough with respect to �so EXn[1l(Xn)] ≤ H(X)+� for n sufficientlyn large.Jointly typical sequences A� (n) is a typical set with respect to PX,Y (x, y) if it is the set of sequences in the set of all possible sequences (xn,ynn withn) ∈X ×Yprobability: 2−n(H(X)+�) ≤ PXn (xn) ≤ 2−n(H(X)−�) 2−n(H(Y )+�) ≤ PY n �yn� ≤ 2−n(H(Y )−�) 2−n(H(X,Y )+�) ≤ PXn,Y n �xn, y n� ≤ 2−n(H(X,Y )−�) for (Xn,Y n) sequences of length n IID ac­cording PXn,Y n(x,yn)= �in =1 PX,Y (xi, yi) Pr((Xn,Y n) ∈ A(�n)) 1as n →∞ → � Jointly typical sequencesUse the union bound Pr((Xn,Y n) �∈ A� (n))≤ Pr((Xn,Y n) �∈ A���� (n))+ Pr((Xn) �∈ A��(n)) + Pr((Yn) �∈ A��(n)) For A��� single typical sequence for pair, A�� for X and A� for Y each element in the RHS goes to 0 MIT OpenCourseWarehttp://ocw.mit.edu 6.441 Information Theory Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.