36
$\begingroup$

Is there a way in R (a built-in function) to calculate the transition matrix for a Markov Chain from a set of observations?

For example, taking a data set like the following and calculate the first order transition matrix?

dat<-data.frame(replicate(20,sample(c("A", "B", "C","D"), size = 100, replace=TRUE)))
Improve this question
$\endgroup$
5
  • $\begingroup$ What is this matrix supposed to represent? One run of the Markov chain for each row (or column)? Or...? $\endgroup$
    – cardinal
    Apr 19, 2012 at 0:07
  • $\begingroup$ This being 100 samples of state sequences (20 of them). $\endgroup$
    – B_Miner
    Apr 19, 2012 at 0:16
  • $\begingroup$ Are you looking for probability estimates or just counts? $\endgroup$
    – cardinal
    Apr 19, 2012 at 0:48
  • $\begingroup$ Probability estimates. Using the observed sequences, what is the transition probability matrix (4x4 in this example). $\endgroup$
    – B_Miner
    Apr 19, 2012 at 0:52
  • $\begingroup$ You are looking for the Baum-Welch algorithm implemented in R. The first link in a simple google search produced the answer. You might find a better implementation in the following links... $\endgroup$
    – Gideon Kogan
    Jun 30, 2021 at 7:19

2 Answers 2

Reset to default
36
$\begingroup$

I am not immediately aware of a "built-in" function (e.g., in base or similar), but we can do this very easily and efficiently in a couple of lines of code.

Here is a function that takes a matrix (not a data frame) as an input and produces either the transition counts (prob=FALSE) or, by default (prob=TRUE), the estimated transition probabilities.

# Function to calculate first-order Markov transition matrix.
# Each *row* corresponds to a single run of the Markov chain
trans.matrix <- function(X, prob=T)
{
    tt <- table( c(X[,-ncol(X)]), c(X[,-1]) )
    if(prob) tt <- tt / rowSums(tt)
    tt
}

If you need to call it on a data frame you can always do

trans.matrix(as.matrix(dat))

If you're looking for some third-party package, then Rseek or the R search site may provide additional resources.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ +1 There are also several R packages, including HMM and RHMM that might be helpful. $\endgroup$
    – Wayne
    Apr 19, 2012 at 1:43
  • $\begingroup$ @Wayne: (+1) I have found the various HMM packages available in R to be very finicky in the past, particularly when it comes to fitting and I never found one I truly liked or trusted. Maybe the situation is better now. I would imagine they would get this right, though. If you know of such a solution, please submit it as an answer; I would be happy to up vote it! $\endgroup$
    – cardinal
    Apr 19, 2012 at 1:49
  • 2
    $\begingroup$ I tried, but with no success. This problem doesn't involve hidden states and the packages I found don't have any utility functions that would do anything less than full-blown HMM. (As a side note, the dat data frame that the OP gives as an example has columns of data, and do they want a transition matrix per column, or an overall transition matrix or can we just turn the matrix into a vector?) $\endgroup$
    – Wayne
    Apr 19, 2012 at 12:22
  • $\begingroup$ @Wayne: (+1) You raise a good point. I have assumed that each row is an independent run of the Markov chain and so we are seeking the transition probability estimates form these chains run in parallel. But, even if this were a chain that, say, wrapped from one end of a row down to the beginning of the next, the estimates would still be quite closer due to the Markov structure. $\endgroup$
    – cardinal
    Apr 19, 2012 at 13:12
  • 1
    $\begingroup$ @B_Miner: Yes, it does, as long as you can reasonably assume that each customer behaves independently of all others. Such models and many extensions are relatively common in analyzing user behavior, e.g., on repeated visits to a website, etc. $\endgroup$
    – cardinal
    Apr 19, 2012 at 16:34
38
$\begingroup$

I have just uploaded a new R package, markovchain, based on S4 programming style. Along with various methods to handle S4 markovchain objects it contains a function to fit a Markov chain from a sequence of states. Have a look at:

library(markovchain) 
sequence <- c("a", "b", "a", "a", "a", "a", "b", "a", "b", "a", 
              "b", "a", "a", "b", "b", "b", "a")
mcFit <- markovchainFit(data=sequence)

It could help.

Improve this answer
$\endgroup$
4
  • $\begingroup$ A very nice package! Will you be supporting higher-order Markov Chains? $\endgroup$
    – Wayne
    Feb 23, 2014 at 2:50
  • $\begingroup$ I have been asked for higher order Markov chain and another guy is writing some code. If you wish to partecipate in code developing send an email to mantainer address and we can discuss... $\endgroup$
    – Giorgio Spedicato
    Feb 23, 2014 at 21:58
  • $\begingroup$ Hi, what’s the difference between markovchainFit and the function posted above? Do they yield the same results? Thanks $\endgroup$
    – aaaaa
    Jun 13, 2018 at 22:09
  • 3
    $\begingroup$ @aaaaa, the $markovchainFit$ function should be faster since build in Rcpp and compiled within a package. Also it handles much more data formats. $\endgroup$
    – Giorgio Spedicato
    Aug 11, 2018 at 12:13

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