COS 402: Artificial Intelligence

Written Exercises

See instructions on the assignments page on how and when to turn these in.  Problems 1 and 3 will be worth around 10 points each; problems 2, 4 and 5 will be worth around 15 points each.  Be sure to show your work and justify all of your answers.

There is no programming part to this assignment.

1.  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.)

2.  Exercise 14.2 in R&N.

3.  Consider the burglar alarm example in R&N Figure 14.2 (and discussed extensively in class).  In R&N (page 505), it is shown that the probability of a burglary, given that both John and Mary call, is roughly 28.4%.  Suppose now 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".)

4.  (This is more or less a rephrasing of R&N Exercise 14.10a.)  In a Bayes net, prove that the conditional probability of a variable given the settings of all other variables is equal to its conditional probability given only the settings of those variables in its Markov blanket.   (Here is a hint.)

5. Let G be an undirected graph.  Consider a random walk on such a graph in which we begin at a designated start vertex, and proceed, at each time step, to traverse to a randomly selected neighbor of the current vertex.  In other words, at each time step, we traverse one of the edges (selected at random) that is incident to the vertex we currently occupy.  Let d(v) be the degree of vertex v, i.e., the number of edges that are incident to vertex v.  Let m be the total number of edges in the graph.

1. What is the transition probability function q(v --> v') for this random walk?
2. Let p(v) = d(v)/(2m).  Show that p is a stationary distribution for this random walk, i.e., that it satisfies the stationarity equation (R&N Eq. (14.9)).
3. Consider a chess king taking a random walk on an ordinary chess board.  At each time step, he can move one step in any direction, horizontally, vertically or diagonally.  What is the stationary distribution p in this case?