Exam 1

Problem No. 1: Entropy Calculations

Let p(x, y) be given by:

                                          X
                                  Y
                                                   1       2
	                                            1     1/8    2/8

                                            2     4/8    1/8

(a) Compute  and .


	












(b) Compute .








(c) Compute 


	






(d) Justify any differences between  and . Note that this doesn't require that the answers to parts (a) - (c) are correct.

 is the joint entropy. Since  and  are not independent variables, contains information of Y. So the joint entropy of  and  will be the sum of the information of  and the information of  given the information of .





                                               H(X)                                                  H(Y)






Problem No. 2: Professional Golf

Jack Nicklaus and Tiger Woods decide to play a series of matches to decide who is the best golfer in the world (of course, everyone knows it is Arnold Palmer). Tiger Woods, being the Stanford graduate, recalls the information theory course he took from Prof. Cover and decides to put what he learned to good use.
In discussing the format of the match with Jack Nicklaus (who didn't do info theory), Mr. Woods obviously would like to choose a format that maximizes his chances of winning. It is given that the longer they play, the more Jack Nicklaus will tire (hence, the better the chance Tiger Woods has to win). Lets suppose the probability of Tiger Woods winning a match is , where  is the event that Tiger Woods wins, and n is the match number. Obviously, they wont play indefinitely, so let's assume .

(a) Using the concepts discussed in this course, determine what strategy Tiger Woods should use in deciding the number and format of matches to be played.

Tiger Woods should see that more number if matches are played with long duration so that Jack Nicklaus will get tired. From the probability of  if  then the probability that Tiger Woods wins is zero so Tiger Woods is sure to loose. When  there is equal probability of Tiger Woods and Jack Nicklaus to win but there are more chances of Jack Nicklaus winning the series as he is sure to win the first game. So playing two games is also not a good strategy for Tiger Woods. If  then the probability of Tiger Woods winning the series increases. So the minimum number of games Tiger Woods should play to win the series is 3. As  increases the chances of Tiger Woods winning the game increases. Also if  is the time taken for each match, the probability of Tiger Woods winning the games increases as  increases.

(b) if i want to bet on this match, obviously i would like to maximize my chances of winning. Using concepts discussed in this course develop and prove an optimal betting strategy. In other words, under what conditions should i bet?
	
The betting strategy should be obviously to win. If  then the probability that Jack Nicklaus wins the match is 1 so the betting should be on jack Nicklaus. if  there is equal chances of Jack Nicklaus and Tiger Woods winning the match so it is better not to bet on anyone in this match. if  the chances that Tiger Woods wins the match is more so the strategy is to bet on Tiger Woods. As discussed previously, as  increases the chances that Tiger Woods wins the game increases so after  the bet should always be on Tiger Woods. 

Problem No. 3:The Browsing Dog

A dog walks on the integers, possibly reversing direction at each step with probability . Let . the first step is equally likely to be positive or negative. A typical walk might look like this:





(a) Prove the chain rule of entropy.










Similarly for  elements,







(b) Find .


 when the dog reverses the direction

                 when the dog moves in the same direction

 		                                    

since there is equal probability in first step to be positive or negative .











(c) Find the entropy rate of the browsing dog.



	





                		

(d) What is the expected number of steps the dog takes before reversing the direction?

The dog must take atleast one step to establish the direction of travel from which it reverses. 	Let s be the number of steps taken before the dog reverses the direction,


	

where m is the dog going in the same direction and n is in the reverse direction



The expected value of steps is given by



	we know