# Calculate Transition Matrix (Markov) in R

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)))

-
What is this matrix supposed to represent? One run of the Markov chain for each row (or column)? Or...? –  cardinal Apr 19 '12 at 0:07
This being 100 samples of state sequences (20 of them). –  B_Miner Apr 19 '12 at 0:16
Are you looking for probability estimates or just counts? –  cardinal Apr 19 '12 at 0:48
Probability estimates. Using the observed sequences, what is the transition probability matrix (4x4 in this example). –  B_Miner Apr 19 '12 at 0:52

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.

-
+1 There are also several R packages, including HMM and RHMM that might be helpful. –  Wayne Apr 19 '12 at 1:43
@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! –  cardinal Apr 19 '12 at 1:49
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?) –  Wayne Apr 19 '12 at 12:22
@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. –  cardinal Apr 19 '12 at 13:12
@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. –  cardinal Apr 19 '12 at 16:34

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.

-
A very nice package! Will you be supporting higher-order Markov Chains? –  Wayne Feb 23 at 2:50
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... –  Giorgio Spedicato Feb 23 at 21:58