COS 402: Artificial Intelligence

Approximate point values are given in brackets. Be sure to show your work and justify all of your answers.  See the course home page for information on when and where to submit written exercises, and grading criteria.  A scanned copy of the exercises in R&N are available on e-reserves (log on to the COS402 site on blackboard, then click on "e-reserves").

1.  [10]  Exercise 7.24 in R&N.

2.  [15]  Exercise 13.18 in R&N.  Be sure to justify your answers.

3.  [10] There are three condemned prisoners A, B and C.  The governor has announced that one of the three, chosen at random, has been pardoned, but doesn't say which.  Prisoner A, realizing that he only has a 1/3 chance of having been pardoned and anxious to learn his fate, reasons with the warden as follows: "Please tell me the name of one of the other prisoners B or C who will be executed.  I already know that at least one of them will be executed so you will not be divulging any information."  The warden thinks for a minute and then asks how he should choose between B or C in case both are to be executed.  "In that case," A tells him, "simply flip a coin (when I'm not around) to choose randomly between the two."  Reluctantly, the warden agrees and the next day tells A that B will be executed.  On hearing this news, A smiles and thinks to himself, "What a fool this warden is to fall for my trick.  Now my chances of having been pardoned have increased from 1/3 to 1/2"  (since either A or C must have been pardoned).

1. Was A correct in his final assertion?  Use Bayes rule to compute the probability that A was pardoned given that the guard tells him that B will be executed.  (Note that this is not the same as the probability that A was pardoned given that B will be executed (i.e., was not pardoned).  This is because the event that "the guard tells A that B was not pardoned" is different from the event that "B was not pardoned".  This is a tricky problem so be careful to distinguish these two events.)
2. Suppose, in the event that the warden has to choose between B or C, that he chooses B with probability p (rather than 1/2 as above).  Now what is the probability that A was pardoned (in terms of p) given, as before, that the guard tells him that B will be executed?  (If you wish, you may answer part b first, and then answer part a by setting p=1/2.)

4.  [15] Exercise 14.11 in R&N.

5.  [10] Consider the burglar alarm example in R&N Figure 14.2 (and discussed extensively in class).  In R&N (pp. 523-4), it is shown that the probability of a burglary, given that both John and Mary call, is roughly 28.4%.  Suppose that you hear on the radio that there was an earthquake in your area.  Now what is the probability of a burglary (given that JohnCalls, MaryCalls and Earthquake are all equal to true)?  Has the probability of a burglary increased or decreased as a result of this new information?  Intuitively, why does this make sense?  (This phenomenon is called "explaining away".)