Given an HMM $(X_i, Y_i)$ where $X_i$ are the hidden states and $Y_i$ are the observables, the Viterbi algorithm finds the most likely sequence of hidden states $X_{1:n}$ given the sequence of observables $Y_{1:n}$, namely it finds the sequence $X_{1:n}$ which maximizes the conditional distribution $P(\{X_i\}|\{Y_i\}, \theta)$ where $\theta$ is the set of parameters defining the model. In particular, the Viterbi algorithm provides a pointwise estimate in that it requires knowledge of the model parameters $\theta$ (usually estimated from the data as ${\hat \theta}$, for example using the EM algorithm, or Baum-Welch for HMM) and in that it provides a single best estimate for the most likely state rather some posterior distribution. The Viterbi algorithm is fast because the full joint probability distribution of an HMM factorized into a tree structure, therefore the maximization problem can be cast in an efficient dynamic programming form comprising two phases:
- a forward pass, maximizing the forward probabilities $P(X_{1:i}, Y_{1:i}|\theta)$ and keeping track of the maximizing states for all possible paths;
- a backward tracking pass, reconstructing the maximizing sequence of states tracing back from $n$ to $1$.
MCMC offers a machinery to move away from a pointwise estimate (frequentist) approach as given above and make inference in an HMM in a Bayesian way, providing instead estimates for for the posterior distributions of all variables in the model, including the set of parameter $\theta$. Typically this is done by introducing priors and defining conditional probabilities for all parameters, and then running a Gibbs sampler.
Details can be easily found around the web, see for example this nice tutorial from Rabiner and this recent article from Rydén comparing EM and MCMC approaches for HMM.
