Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

With Mathematica 9, we have the addition of various processes, among which the discrete Markov process. Given a transition probability matrix m, such a process is defined as follows:

m = {{1/4, 1/4, 1/4, 1/4, 0, 0},
     {1/3, 0, 1/3, 1/3, 0, 0},
     {0, 1/2, 0, 1/4, 1/16, 3/16},
     {0, 0, 0, 1/2, 1/2, 0},
     {0, 0, 0, 0, 1/2, 1/2},
     {0, 0, 0, 0, 0, 1}

proc = DiscreteMarkovProcess[1, m];

g1 = Graph[proc]

Mathematica graphics

Various properties of a given Markov process can be found using the function MarkovProcessProperties. Probability can be used (among other things) to answer questions about the likelihood to end up in a certain state after a given number of steps.

However, I did not find a function that yields the path that is most likely to be taken between a given a starting and ending state. How would one find this path?

share|improve this question
Isn't that just what Viterbi's algorithm does? – nikie Feb 12 '13 at 8:22
@nikie I wasn't aware of that algorithm. Thanks. According to Wikipedia this is used for hidden markov models, but I feel that that implies it should be easily convertible to MM as well. The implementation will take a few more lines of code than the one given below, which I believe is already optimal. I may be wrong here, though. – Sjoerd C. de Vries Feb 12 '13 at 9:26
up vote 31 down vote accepted

This sounds very similar to a traveling salesman problem for which we have the built-in (as of v8) FindShortestPath function. However, this function minimizes the overall path length (which is the sum of all sub-paths), whereas we need a functions that maximizes the path probability (which is the product of the transition probabilities along the path).

Since maximizing a product is equivalent to minimizing the sum of the negated logarithms this is easy enough. In this case:

g2 = WeightedAdjacencyGraph[-Log[m]]

Mathematica graphics

sp2= FindShortestPath[g2, 1, 6]

{1, 4, 5, 6}

HighlightGraph[g1, sp2]

Mathematica graphics

The shortest path in terms of the original matrix weights would have been:

sp1 = FindShortestPath[g1, 1, 6]

{1, 3, 6}.

Test that the former is indeed more likely than the latter:

pathProbability[m_?MatrixQ, path_List] := Times @@ (m[[##]] & @@@ Partition[path, 2, 1])

pathProbability[m, #] & /@ {sp1, sp2}

{3/64, 1/16}


Since version 10 Mathematica has acquired tools for hidden Markov processes. The likeliest path can now be calculated by setting the starting and ending state to 100% emitting and all other states to hidden, non-emitting states. FindHiddenMarkovStates will now do the job for us using Viterbi decoding, though it doesn't really yield shorter or more elegant code. It's also a lot (by a factor of more than 10) slower.

hmm = HiddenMarkovProcess[1, m, {{1, 0, 0, 0, 0, 0}, None, None, None, None, {0, 0, 0, 0, 0, 1}}];
obs = {1, 6};
FindHiddenMarkovStates[obs, hmm]

{1, 4, 5, 6}

share|improve this answer
+1 You might in many cases be interested in all modal paths, not just one of them. (This is related to my recent question.) – whuber Feb 12 '13 at 4:14
@whuber Interesting. Do you happen to have a link to a paper with a readable introduction to this area? – Sjoerd C. de Vries Feb 12 '13 at 6:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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