Exercise 1.1 (Jointly typical sets). Let pXY be any joint distribution on X ˆY. For any 0 and positive integer n, define the jointly typical set q “ !
where µxnynpa,bq is the number of locations i P t1,2,...,nu for which xi “ a and yi “ b.
Let Xn,Y n be jointly distributed such that Xi,Yi „ pXY for all i whereas pXi,Yiq is independent of all other pXj,Yjq for all j ‰ i.
1. Prove that limnÑ8 Prrp qs “ 0
2. Show that for all g : X ˆ Y Ñ R and all pxn,yn T pnq pXY q,
q
3. Use the above to obtain upper and lower bounds on | .
Exercise 1.2 (Implementing compression). The shared folder contains files with characters randomly drawn from the set ta,b,c,d,eu. You must write a program to compress and decompress this file.
1. Write a program to compute the empirical type of the file, i.e., the fraction of occurrence of various symbols in the file. Also compute the entropy.
2. Using the above type, design the Shannon, Huffman and Shannon-Fano-Elias codes for this file. You can compute these on paper. Show all the steps.
3. Use the designed codes to compress the attached file.
1-1
1-2 Homework 1:
4. Decode the compressed file, and verify that you get back the original file
5. Find the length of the compressed sequence, and compare this with the entropy.
Exercise 1.3. Repeat the same as in Problem 2 for the corresponding file in the folder for problem 3.
