EE 553, Fall 1996October 17, 1996EE 553EXAM 1This is a closed book, closed notes exam, scheduled to last 90 minutes. Calculatorsand computers are not allowed.NAME: ____________________________________Score:1. _____2. _____3. _____4. _____5. _____Total:1. (10 points) Prove that−0. 7 log 0. 7 − 0. 3 log 0. 3 − 0. 2 log 0. 2 − 0. 8 log 0. 8 < 2⎡⎣−0. 75 log 0. 75 − 0. 25 log 0. 25⎤⎦.You must do this without using a calculator (that is without computing any of the loga-rithms indicated), using the theoretical tools developed in this class. Try to giv e somedetails to convince me that you know what you are doing.2. (50 points) In many sporting events (such as the National League ChampionshipBaseball Series going on now inv olving our very own St. Louis Cardinals), the teamscompete in several games, with the first team winning K games declared the winner ofthe series. Note that this implies a maximum of 2K − 1 games. Such series are oftencalled a ‘‘best K out of 2K − 1 series.’’ For example, the Cardinals and Braves will playthe seventh game of their ‘‘best 4 out of 7 series’’ this evening.EE 553 -2- Exam 1For each of the parts of this question, assume that the outcomes of all games aredescribed by a ‘‘1’’ or a ‘‘0’’ depending on whether team one wins or loses. Assume thatthe outcomes of all games are independent and identically distributed withP(outcome=1) = p.a. For a best 2 out of 3 series, find a good lower bound on the average number of bitsneeded to describe the outcomes of all games played. Note that we are considering theset of outcomes of all games played in a series as the random variable.b. Suppose that p = 0.4. Find a Huffman code to describe the outcomes of all gamesplayed in a best 2 out of 3 series. Find the expected codeword length.c. We now change the random variable definition slightly. Suppose that at the end of aseries we only care how many games each team won in a best 2 out of 3 series. Thus, ifteam one wins the series, then team one wins two games and the other team wins eitherzero games or one game. The random variable describing the series is then the pair(l, m), where l denotes the number of games that team one wins and m denotes the num-ber of games the other team wins. Again, let P(outcome=1) = p. Suppose n independentseries are played. Find theεtypical set.d. Now suppose that you place bets on which team wins the series. Suppose that youfind a bookie who will pay uniform fair odds. For best 2 out of 3 series, determine theoptimal betting strategy and the resulting doubling rate.3. (15 points) Suppose that a rectangle in n dimensions has sides X1, X2,..., Xn,so that the volume (measure) of the interior of the rectangle isVn=ni=1Π Xi.Suppose that the lengths Xiare i.i.d. distributed according to pX(x). Find the doublingrate for the volume of the rectangles (as the dimension increases).4. (15 points) In many image processing problems, objects are described in termsof their boundaries. While this may not be the optimal strategy, in this problem we exam-ine the Kolmogorov complexity of such descriptions.An object is a closed and connected region in an image. An image is an m × marray of numbers; a location in the array is called a pixel; the number associated with apixel is called a pixel value. A boundary is a list of pixels that surround an object. Theboundary has the property that each pixel in the list is a neighbor of the previous pixeland the last pixel is a neighbor of the first pixel. A neighbor pixel is one of the four up,down, left, right pixels. An example of a boundary is given in the attached figure.a. Let n be the length of a boundary B (the length of the list of pixels). Find an upperbound on the Kolmogorov complexity of a boundary given n and given m (the size of thearray). Denote this complexity by K(B|n, m).b. Find an upper bound on the Kolmogorov complexity of a boundary given m, K(B|m).5. (10 points) One of the goals in developing models is to more accurately describethe statistics of empirically observed data. Often more complicated models are better inmany senses, including allowing greater data compression.Suppose that a set of data is available and one wants to model these data. A modelwill be called admissible if the typical set for that model includes the data set. Model 2 isbetter than model 1 if the typical set for model 2 is smaller than the typical set for model1 and model 2 is admissible. Since the typical set is smaller, a code developed usingEE 553 -3- Exam 1model 2 will require fewer bits on average than the code developed using model 1. Wenow explore an example of this.Suppose that the data set consists of n binary random vectors each of length m.There are three possible models explored. State whether each is admissible. Determinean ordering, including which is best. Justify your answers.Model 1: The bits are i.i.d. with probability 1/2 that each bit is 1.Model 2: The bits are i.i.d. with probability p that each bit is 1, where p is the empiricalav erage number of 1’s in the entire data set (count the number of 1’s out of all mn entriesin the vectors, and divide by mn).Model 3: Each random vector comes from a Markov chain, with stationary probability pthat each bit is 1 (where p is determined as in Model 2), and with transition probabilitiesdetermined according to the empirical transition probabilities. Let the resulting transitionmatrix beP =⎡⎢⎣rq1 − r1 − q⎤⎥⎦.Bonus: If by any chance you make it this far (I don’t think you will), argue that the anal-ysis in this problem is far from complete. In fact, for data compression the complexity ofthe model used must also be taken into account. If the model becomes too complex, itmay represent the data in the data set well, but not any data not already int he set. Analternative argument would be based on Kolmogorov complexity. There is a complexityof the data set given the model for the data and the complexity of the