COS 402: Artificial Intelligence

Special late policy:  For the purpose of counting late days, Thanksgiving and the day after Thanksgiving will together be treated as a single late day.

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.  [15]  Let G be a connected, undirected graph with at least two vertices.  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 π(v) = d(v)/(2m).  Show that π is a stationary distribution for this random walk, i.e., that it sums to one when added over all vertices, and that it satisfies the stationarity equation (Eq. (14.10) of R&N).
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 (but of course, he has to stay on the board).  What is the stationary distribution π in this case?

2.  [15]  Alice, Beth, Carla, Donna and Emily are holding an election to choose the president of their club.  The candidates are Alice and Beth, both of whom will certainly vote for themselves.  In addition, Beth has the unwavering support of Carla.  However, Donna and Emily are indecisive swing voters who are constantly changing their minds: every day, each of them switches her support to the other candidate independently with probability 0.2; for instance, if Donna supports Alice on Monday, then on Tuesday, the chance that she still supports Alice is 0.8, and the chance that she switches to Beth is 0.2.

Everyday leading up to the election, Paul the Pollster takes a survey with a sample size of just one; in other words, he chooses one of the five voters at random and asks who she plans to vote for.  (The voters chosen on each day are selected independently so it is possible that the same voter is picked more than once.)  Given the results of these surveys, as well as the other information given above, we will be interested in inferring the state of the electorate at various points in time.

On Sunday, Donna mentions that she is supporting Alice, and Emily says she is planning to vote for Beth.  On Monday, Paul takes his one-sample survey and finds that the random voter he picked plans to vote for Alice.  On Tuesday, Paul takes another one-sample survey and again finds that the random voter he picked plans to vote for Alice.

1. Formulate this problem as a hidden Markov model.  What are the hidden states and what are the possible observations?  What is the probability of transitioning from every state to every other state?  What is the probability of each observation in each state?  (Although there are several ways of doing this, it is possible to use only three states in formulating your HMM.  Using fewer states may make the next parts of the problem easier.)
2. Given all of the information above, what is the chance that Alice has the support of a majority of the voters on Tuesday?
3. Given all of the information above, what is the chance that Alice had the support of a majority of the voters on Monday?
4. Given all of the information above, what is the chance that Alice will have the support of a majority of the voters on Wednesday?
5. Consider extending these ideas to an actual election with an electorate of millions of voters for which a polling organization takes a daily survey of several hundred voters.  Suppose the goal is to track the fraction of voters in favor of one of the candidates, call him Candidate O.  The surveys can only provide an estimate of the actual percentage.  What's more, every day, a small percentage of voters change their minds about who they will vote for.  Explain in words how a Kalman filter could be used here to track the fraction of voters in favor of Candidate O based on the polling results.  What assumptions would we be making in using a Kalman filter for this purpose?  In what ways are these assumptions realistic or unrealistic for this application?

3.  [10]  Exercise 15.1 in R&N.  (The "parameters" of a model refer to the numbers, usually probabilities, that define it.)

4.  [15]  Exercise 15.3 in R&N.  However, in part d, you can skip the last question ("How does this change...?").