COS 302: Introduction to Artificial Intelligence

Special late policy:  In counting late days, we will skip Thanksgiving day and the Friday after Thanksgiving.  In other words, homeworks turned in by 11:59pm on Wednesday, November 26 will count as two days late (as usual), but homeworks turned in by 11:59pm on Saturday, November 29 will count as only three days late.  As usual, no homeworks will be accepted more than five "days" late, which means they will not be accepted after Monday, December 1.

Written Exercises

Turn these in at the end of class or in room 001A Computer Science on or before the due date.  Approximate point values are given in parentheses.  Be sure to show your work and justify all of your answers.

There is no programming part to this assignment.

1.  (15)  Consider a two-bit register.  The register has four possible states: 00, 01, 10 and 11.  Initially, at time 0, the contents of the register is chosen at random to be one of these four states, each with equal probability.  At each time step, beginning at time 1, the register is randomly manipulated as follows: with probability 1/2, the register is left unchanged; with probability 1/4, the two bits of the register are exchanged (e.g., 01 becomes 10); and with probability 1/4, the right bit is flipped (e.g., 01 becomes 00).  After the register has been manipulated in this fashion, the left bit is observed.  Suppose that on the first three time steps, we observe 0, 0, 1.

1. Show how the register can be formulated as an HMM.  What is the probability of transitioning from every state to every other state?  What is the probability of observing each output (0 or 1) in each state?
2. Use the filtering algorithm to determine the probability of being in each state at time t after observing only the first t bits, for t=1,2,3.
3. Use the forward-backward algorithm to determine the probability of being in each state at time k given all three observed bits, for k=0,1,2,3.
4. What is the most likely sequence of states given all three observed bits?  (Be sure to include the initial state at time 0 in your sequence.)

2.  (10)  Exercise 15.1 in R&N.

3.  (15)  Exercise 15.3 in R&N.  However, you can skip the last question in part d.

4.  (10)  (This is a slight rephrasing of R&N Exercise 16.3.)  In class, we discussed the St. Petersburg paradox.   (The book uses a slight variant that doubles the payouts described in class.  To avoid confusion, please use the version defined in class in which 2^(n-1) dollars are paid if the first head appears on the nth toss.)  Bernoulli explained the paradox by suggesting that the utility of money is on a logarithmic scale (i.e., that the utility of having $n is a lg n + b).

1. Suppose you have $k and that you pay $x to play the game.  What is your expected utility at the end of the game?  Give a general formula, and also evaluate your formula numerically when x=k.
2. What is the most it would be "rational" to pay to play the game?  In other words, what is the largest value of x for which your expected utility of playing the game is at least as large as the utility you started out with?  If you can't solve for x in closed form, just give a general equation determining the answer.  Also give an exact numerical answer when x=k.