DOC PREVIEW
WUSTL ESE 520 - ESE523Lect272013

This preview shows page 1-2-3-22-23-24-45-46-47 out of 47 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 47 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

ESE 523 Information Theory Lecture 27Outline: Today Chapter 11, the Method of TypesMethod of TypesMethod of TypesMethod of Types: Computing ProbabilitiesAside: Stirling’s Formula http://en.wikipedia.org/wiki/Stirling's_approximationSimple Approximation Application to Cardinality of Type ClassMethod of Types: The Size of a Type ClassMethod of Types: The Size of a Type ClassMethod of Types: The Probability of a Type ClassCommentsLecture 1: CombinatoricsCombinatorics : ExperimentsMatlab CodeMatlab CodeExample ResultLecture 22-23Brief Review of Lecture 21Computation of Probabilities Using the Method of TypesLarge Deviations Theory Sanov’s Theorem Proof of Sanov’s Theorem Sanov’s Theorem Applications Conditional Limit TheoremConditional Limit TheoremUniversal Source Coding Universal Source Coding: Proof Universal Source Coding Lecture 23: Hypothesis TestingHypothesis TestingHypothesis Testing: Neyman-Pearson LemmaProof of Neyman-Pearson LemmaBasis for Chernoff-Stein LemmaBasis for Chernoff-Stein LemmaDerivation of Optimal Distribution Chernoff-Stein LemmaChernoff InformationChernoff-Stein LemmaChernoff-Stein LemmaPythagorean-Type Inequality for Relative EntropyPythagorean-Type Inequality for Relative EntropyL1 Lower Bound on Relative EntropyL1 Lower Bound on Relative Entropy L1 Lower Bound on Relative Entropy Typical Sets: The Weak Law of Large Numbers (Again)Typical Sets: The Strong Law of Large Numbers Strongly Typical SetsNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 27 1ESE 523 Information TheoryLecture 27Joseph A. O’SullivanSamuel C. Sachs ProfessorElectrical and Systems EngineeringWashington University211 Urbauer Hall2120E Green Hall314-935-4173 [email protected] 12, 2013 J. A. O'Sullivan ESE 523 Lecture 272Outline: Today Chapter 11, the Method of Types Comment: Semester Schedule: possibly add lectures on  Optimization Theory Kolmogorov complexity Method of types Å relative frequencies of outcomes, type classes, combinatorics, strongly typical sequences Universal source coding Large deviation theory (Sanov’s thm, examples) Conditional limit theorem Hypothesis testing (Neyman-Pearson lemma) Chernoff-Stein lemmaNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 273Method of Types[]()121121Let 1, 2,... , , and ... . Then( | ) ( , ) the number of times occurs in , and(|) has entries ( ) , for each . Let, ,..., : 0, 1 , the pri nniimmi iixi n m xx xNa ax aNaPPa anpp p p pδ==∈= = ====∈⎧⎫=≥=⎨⎬⎩⎭∑∑xxxxxxX, XXP{}obability simplex., where is the set of types with denominator .For any type , the type class ( ) is the set of all vectors that havethat type() : .nnnnPnPTPTP P P∈∈∈=∈ =xxxPP PPXNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 274Method of Types{}11212( | ) ( , ) the number of times occurs in , (|)() , ( ) : . Then(|) ,!() .(|) (|) ( |)( | )! ( | )! ( | )! (1) (1).niinammmnNa ax aNaPa TP P PnNa nnnTPNa Na NaNa Na Nannδ=∈====∈==⎛⎞==⎜⎟⎝⎠≤+ =+∑∑xxxxxxxxx xxx xTheorem :ProoXXXP{}{}()( )23 0(|), 1,2,,. 2, 0,1 , 1 ( 1) .13, 0,1, 1 , ( 1) .2innNa n i mmnnnnmn≤≤=== =+<++==− = <+f: xExamples : XPXP…•Loose upper bound•Number of type classes isbounded by a polynomial in nNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 275Method of Types: Computing Probabilities The probability of a sequence with i.i.d. entries is determined by its type()() (||)(|) ()1(()log () Suppose that are i.i.d. with common distribution ( ). The probability of is() 2 . () ( ) () ()() 2 2inH P DP QnnNa nP aniia anPnP a Q anaXQxQQQxQa QaQ−+=∈ ∈−−∈=== ===∏∏ ∏∏xxxxxxTheorem :xxProof : xxXXX())log ( ) ( )log ( ) ( )log ( )() If , and if ( ), then () 2 . If ( ), then and ( || ) 0.aaPaPaPaPaQannnHQQTQQTQ P Q DP Q∈+−−∑∈∈=∈= =xx xxxxCorollary : xxProof : xXPNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 276Aside: Stirling’s Formulahttp://en.wikipedia.org/wiki/Stirling's_approximation Stirling’s formula Resulting approximation Upper and lower bounds proved by integrating lnx!lim 2!211ln ! ln ln 02nnnnnennnnnnennnn nnππ→∞=≈⎡⎤−+− →⎢⎥⎣⎦() ()()()111111ln 1 ( )1ln ! lnln ln lnln 1 ln ( 1) ln( 1) ( 1) 1ln ln 1 ( ) !kikkkikikkk okikixdx i xdxkkk i k k kik k ok k e=+==−+==<<−+< < + +− + +=−+⇒=∑∑∫∫∑∑Simple Approximation November 12, 2013 J. A. O'Sullivan ESE 523 Lecture 277http://en.wikipedia.org/wiki/File:Stirling%27s_Approximation.svgNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 278Application to Cardinality of Type Class()()ln 1 ( )121() ()1!!()!! !exp ln 1 ln ( )exp ln ( ) 2kk okmmiiiimnH P oniiikenTPkk kkknn k onnnkknonnn−+=+==⇒=⎛⎞⎡⎤⎛⎞=−−−+⎜⎟⎜⎟⎢⎥⎝⎠⎣⎦⎝⎠⎛⎞⎡⎤=− +=⎜⎟⎢⎥⎣⎦⎝⎠∑∑xNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 279Method of Types:The Size of a Type Class The normalized log-size of a type class is asymptotically equal to the entropy of the type() ()()() ()()() For any type ,12()2.(1) Upper bound1(()) () 21()2 () 2 .nnH P nH PnnnHPTP TPnH PnH PPTPnPTP PTPTP−∈∈−∈≤≤+≥= =≥⇒≤∑∑xxTheorem :Proof :xXPNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 2710Method of Types:The Size of a Type Class The normalized log-size of a type class is asymptotically equal to the entropy of the type()() ()() (||)1 For any type , 2 ( ) 2 .(1) Lower bound: 1()(())1()2 (1)max(()) For any type , max ( ( )) (nnnnnnH P nH PnnnQnHQ DQPnQQnnnQPTPnPPTQTQ n P TQPPTQP∈∈−+∈∈∈∈≤≤+===≤+∈=∑∑∑xTheorem :Proof :xLemma :XPXXPPPPP()()()). For any type , ( ( )) ( ) 2 .Combining these results, 1( 1) ()2 .nnHPnnH PTPP P TP TPnTP−−∈=≤+Lemma :XPNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 2711Method of Types:The Probability of a Type Class The normalized log-probability of a type class is asymptotically equal to minus the relative entropy between the type and the distribution()(||) (||)() (||) For any type , and any distribution ,12(())2.(1) (()) ()2nnD P Q n nD P QnH P DPQnPQQTPnQTP TP−−−+∈≤≤+=Theorem :Proof :XPNovember 12, 2013 J. A. O'Sullivan ESE 523 Lecture 2712Comments This proof already illustrates a central technique: The number of type classes is polynomial The size of a type class is exponentially large The probability of a type is exponentially


View Full Document

WUSTL ESE 520 - ESE523Lect272013

Download ESE523Lect272013
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ESE523Lect272013 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ESE523Lect272013 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?