Solutions for Test 1

Problem No. 1
(a)

(b)


(c)

(d)  

Joint entropy is the entropy of one random variable plus the conditional entropy
of the other random variable given the first random variable.







Problem No. 2
(a)


Table 1  Probability of Wins
P(A)	Match,n
0	1
0.5	2
0.67	3
0.75	4
0.8	5
0.83	6
0.86	7
0.88	8


Playing three matches would not be a good choice because Tiger can not win the
first match and the second match could equally go either way.  Tiger would not want
the game to end up in a tie; therefore, we rule out the possibility of playing four 
matches.  In five matches, Tiger is favored to win three matches, and he chances of 
winning increases with each succesive match.  Tiger should play at least five 
matches in order to maximize his wins.

(b)




Table 2    Entropy
X	H(X)
1	0
2	1
3	.918
4	.811
5	.722
6	.650
7	.592
8	.544


H(1) - Don't bet.  You know that you will lose.
H(2) - Don't bet.  You have no idea whether or not you will win.
H(3) - Uncertainty is high.
H(4) - Uncertainty is high.

If you are betting on each match, then bet only when uncertainty of Tiger winning
is fairly low.  Therefore, we need to draw a line at some point.  When uncertianty
is below this threshold, we bet knowing that are chances of winning is fairly high
compared to the chances of winning when entropy is above this threshold.  In our
example, we choose .650 to be our threshold.  When entropy is .650 or below, we
our certain that we have a high probability of winning.









Problem No. 3

(a)



(b)





However, the dogs next step depends only on his previous two steps.  The previous
step gives us the direction in which the dog is traveling, and the step before the 
previous tells us whether or not the dog changed directions.  This gives us a second
order Markov chain.



H(X0) = 0       There is no uncertainty about the dog's starting position.
H(X1|X0) = 1  The dog's first step is equally likely to be positive or negative.



After the first step, there are n-1 steps left.  The entropy is based on whether the 
dog continues forward with a probability of 0.9 or reverses direction with a 
probability of 0.1.

Thus,



(c)



= H(0.1,0.9) = 0.1 log (1/0.1) + 0.9 log (1/0.9) = 0.469  bits

(d)



p = probability of forward step = 0.9
q = probability of reverse step  = 0.1
q = 1 - p

In s steps, the dog takes s-1 forward steps and 1 reverse step.  Therefore, the
probability of the dog walking forward and then reversing is:








Starting from zero, the expected number of steps before reversing direction is 11.