The following is a quote from my textbook, in a chapter discussing the Viterbi algorithm (Durbin, Richard, et al. Biological sequence analysis: probabilistic models of proteins and nucleic acids. 1st edition p56)

...The most probable path $π^∗$ can be found recursively. Suppose the probability $v_{k}\left(i\right)$ of the most probable path ending in state $k$ with observation $i$ is known for all the states $k$. Then these probabilities can be calculated for observation $x_{i+1}$ as $$v_{l}\left(i+1\right)=e_{l}\left(x_{i+1}\right)\underset{k}{\max}\left(v_{k}\left(i\right)a_{k,l}\right)$$

Context: The setting is a hidden Markov model, where $\pi_{i}$ is the hidden state at step $i$, and $x_{i}$ is the observation at step $i$. Irrelevant to the question but also worth noting: $e_{l}(x_{i})$ is the emission probability of observation $x_{i}$ given state $\pi_{l}$ and $a_{k,l}$ is the transfer probability from state $\pi_{k}$ to state $\pi_{l}$

Question: How should I interpret "the probability of the most probable path ending in state $k$ with observation $i$"? Is it $$(1)\ \ \ v_{k}\left(i\right)=\underset{\pi_{1},\ldots,\pi_{i-1}}{\max}\left(p\left(\pi_{1},\ldots,\pi_{i-1},\pi_{i}=k\mid x_{1},\ldots,x_{i}\right)\right)$$


$$(2)\ \ \ v_{k}\left(i\right)=\underset{\pi_{1},\ldots,\pi_{i-1}}{\max}\left(p\left(\pi_{1},\ldots,\pi_{i-1}\mid x_{1},\ldots,x_{i}, \pi_{i}=k\right)\right)$$


There are no conditions that have to be met by any variable (nothing like "the probability of the most probable path given that it ends in state k..."). So I would say joint. On the other hand, I don't really understand the notation: what do $x_i$ and $\pi_i$ mean? What you wrote seems to be speaking about the probability of the path having several characteristics as well as ending in state $k$ and observation $i$, which is a mistake (you are only asked about the probability of the path ending with some characteristics, yet you specified the characteristics of the whole path). I think you need something like $$v_k(i)=P(\pi^*\text{ ends at state k},\pi^*\text{ ends at observation i}).$$

I can't really write about the "most probable path" explicitly because you didn't mention what this path is the most probable of. If you define the notation, we might be able to help you better.

  • $\begingroup$ Thanks. I suppose part of the problem is that I am not sure about some of these things myself. Iv'e edited the question, hopefully it makes a bit more sense now. $\endgroup$ – D.M. Dec 11 '18 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.