Exercise 6.11 Consider the problem of filtering in HMMs (page 271).

(a) Give a formula for the probability of some variable Xj given future and past observations. 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. How can the factor needed by Xj−1 be computed without recomputing the message from Xj+1? [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) 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.]