How does the time complexity of exact inference in a Markov chain depend on the number of time steps?
  • The time complexity is linear, since the Markov property makes it possible to calculate probabilities for each time step directly from the previous step. This stands in contrast to variable elimination in general belief networks.

Valid HTML 4.0 Transitional