Homework #4

Fall 2004

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