#hidden-semi-markov-model

Question 1: Single choice

A process stays in each of its $k$ states for a random duration $d \in \{1, \dots, M\}$ and then jumps to a different state, so it is turned into an HMM whose states are pairs $(x, t)$ : the current state and the time spent in it so far. Run naively on these $kM$ states, the forward algorithm costs $O(N k^2 M^2)$ for $N$ time steps, but it can be done in $O(N(k^2 + kM))$ . What makes the saving possible?

Each $(x, t)$ only moves to $(x, t + 1)$ or some $(x', 1)$ , with a factored switch probability1
Emissions depend only on $x$ , so the elapsed time $t$ can be dropped from the state2
Durations are at most $M$ , so each forward message has only $M$ non-zero entries3
Replacing the sums over states by maxima, as Viterbi does, is cheaper4

#hidden-semi-markov-model

Timed test