Consider the problem of filtering in HMMs (page 426).

(a) Give a formula for the probability of some variable Xj given future and past observations. You can base this on Equation (9.6) (page 426). This should involve obtaining a factor from the previous state and a factor from the next state and combining them to determine the posterior probability of Xk.

[Hint: Consider how VE, eliminating from the leftmost variable and eliminating from the rightmost variable, can be used to compute the posterior distribution for Xj.]

(b) Computing the probability of all of the variables can be done in time linear in the number of variables by not recomputing values that were already computed for other variables. Give an algorithm for this.

(c) Suppose you have computed the probability distribution for each state S1, ..., Sk, and then you get an observation for time k + 1. How can the posterior probability of each variable be updated in time linear in k? [Hint: You may need to store more than just the distribution over each Si.]