1 1. Today’s outline a. Asymptotic Equipartition Property (A.E.P.) b. Typical sets c. Application to data compression 2. Review of last lecture Notions: • )/;(),;(),/(),( zyxIyxIyxHxH • ∑=xxqxpxpqpD)()(log)()//( which is measure of the inefficiency of assuming that the distribution of x is q(x) when the true distribution is p(x). • Markov chain: ZYX→→ or equivalently yzyxzyxppp///,= Results: • 0)//(≥qpD with equality when )()( xqxp= • 0)//();(,≥=yxyxpppDyxI • )();()()/( xHyxIxHyxH≤−= • chain rule: ∑=≤niinxHxxH11)(),...,( • If ZYX→→ then );();( yxIzxI≤ • If XYXˆ→→ then Fano’s inequality: xeyxHPXXΩ−≥=≠log1)/()ˆPr( 2.1. Review of Fano’s inequality We give two examples which show that Fano’s inequality can be either weak or tight. 6.441 Transmission of Information Feb. 16, 2006 Lecture 4 Lecturer: Madhu Sudan Scribe: Costas Pelekanakis (gas)2 2.1.1. Example 1 x is uniformly distributed over the set of binary n-tuples and y takes values from the set of binary n/2-tuples. I claim no matter distribution I pick for y, 2/)/( nyxH≥. We have: 2/)()/()();();();()()/(2/2loglog)(2loglog)(2/22nyHxyHyHyxIyxInyxIxHyxHnyHnxHnynx≤≤−=−=−===Ω≤==Ω= Thus, 2/)/( nyxH≥. Fano’s inequality yields (assuming big n): 5.02/log1)/(=≈Ω−≥nnyxHPxe A better bound on Pe in this case is: nnnnPP221)error(22)decodingcorrect (2/2/−≥⇒≤ In this example Fano’s inequality is very weak! 2.1.2. Example 2 x,y are distributed as follows: with probability p, x=y, and x,y are uniformly distributed over the set of binary m-tuples and with probability 1-p, x is uniformly distributed over the set of binary n-tuples and y is a constant. This is the picture of an erasure channel. The best strategy would decode as follows: observe y and assume that this is what it was sent. Obviously pPe= in this case. Fano’s inequality yields: pnnpPnpnpxyxHpconstyxHpyxHe≈−⋅≥⋅=+⋅==⋅−+=⋅=10)/()1()/()/( 3. Typical sets We want to answer the following question: if x1,...,xn are iid and xi ~ p(x), i=1...n, what is the probability of the sequence ),...,(1 nxx to occur an n goes large? This will lead us to divide3 the set of the sequences into two sets, the typical set, which contains the “highly likely to occur” sequences and the non-typical set which contains all the other sequences. We will use the law of large numbers to answer the above question. 3.1. A.E.P. Lemma If x1,...,xn are i.i.d. according to p(x) then )()...(log1xHnxxpn→− in probability. In other words: for every ε>0, δ>0 there exists nο(δ,ε) such that for every n>nο(δ,ε) the δεε−≥+≤−≤− 1})()...(log)(Pr{1xHnxxpxHn. (Actually δ goes to 0 as exp(-nε2)). Proof: Note that ),...,(1 nxxp is the probability of observing the sequence ),...,(1 nxx. We have that xi are iid so: ∑====niiniinxpnxpnxxpn111)(log1)(log1)...(log1C Let us call a new r.v. )(logiixpz −=. The zi’s are also i.i.d. and )(][ xHzE=. Applying the law of large numbers we have: )(][1)(log111xHzEznxpnLLNniinii=→=−∑∑== Rewriting the above result we note that the probability to observe a sample sequence ),...,(1 nxx is bounded as: ))((1))((2),...,(2εε−−+−≤≤xHnnxHnxxp . This motivates the definition of the typical set. Ωn Actual universe of typical sequences4 3.2. Definition: Typical set }2),...,(2|),...,{())((1))((1)(εεε−−+−≤≤=xHnnxHnnnxxpxxA 3.3. Typical set theorem i) δε−≥1}Pr{)(nA ii) ))(()(2εε+≤xHnnA iii) ))(()(2)1(εεδ−−≥xHnnA Proof: i) A.E.P. Lemma ii) ))(()())(()()(22}Pr{1εεεεε++−≤⇒⋅≥≥xHnnxHnnnAAA iii) ))(()()())(()(2)1(1}Pr{2εεεεεδδ−−−⋅−≥⇒−≥≥⋅xHnnnxHnnAAA 3.4. Example Let −=1/20 w.p.11/20 p. w.110/9 . w.p0z We expect the typical sequences ),...,(1 nzz to contain )'1(109ε±n “zeros”, )'1(201ε±n “ones” and )'1(201ε±n “minus ones”. Furthermore, )')(()(2εε±≈zHnnA 4. Application: Data compression Compression is a mapping (function) of a higher dimensional space onto a lower one. Suppose we want to map the set Ωx of binary n-tuples to the set Ωy of the binary m-tuples with m«n. Obviously, the mapping is not “1-1” so errors will occur during decoding. We divide Ωx into two sets: the )(nAεand its complement. We are computing the following quantity:5 )(2))(()(11)(1)()(x2222})),...,max(Pr{(}decoder of image ),...,( and ),...,Pr{(}correctly/ decodingPr{}\ correctly/ decodingPr{}correctly decodingPr{nnmxHnmnnynnnnnAAxxxxAxxAAεεεεεεδεδδδδ+≤⋅+=∈Ω+≤∈∈+=+Ω=−−444444 3444444 21 )(nAε Ωx={0,1}n Ωy={0,1}m Encode