Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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

I have a full set of sequences (432 observations to be precise) of 4 states $A-D$: eg

$$Y=\left(\begin{array}{c c c c c c c} A& C& D&D & B & A &C\\ B& A& A&C & A&- &-\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ B& C& A&D & A & B & A\\ \end{array}\right)$$

EDIT: The observation sequences are of unequal lengths! Does this change anything?

Is there a way of calculating the transition matrix $$P_{ij}(Y_{t}=j|Y_{t-1}=i)$$ in Matlab or R or similar? I think the HMM package might help. Any thoughts?

eg: Estimating Markov chain probabilities

share|improve this question
You have $4$ states: $S=\{1:=A,2:=B,3:=C,4:=D\}$. Let $n_{ij}$ be the number of times the chain made a transition from state $i$ to state $j$, for $ij,=1,2,3,4$. Compute the $n_{ij}$'s from your sample and estimate the transition matrix $(p_{ij})$ by maximum likelihood using the estimates $\hat{p}_{ij}=n_{ij}/\sum_{j=1}^4 n_{ij}$. – Zen Sep 11 '12 at 16:29
These notes derive the MLE estimates: – Zen Sep 11 '12 at 16:30
Similar… – B_Miner Sep 11 '12 at 20:18
@B_Miner could you write your code in pseudo-code form for me? Or explain it in lay terms... However I see it works in my R console. – HCAI Sep 11 '12 at 21:41
I have a question: I understand your implementation and it lokks fine to me, but i was wondering why can't i simply use the Matlab hmmestimate function to compute the T matrix? Something like: states=[1,2,3,4] [T,E]= hmmestimate ( x, states); where T is the transition matrix i'm interested in. I'm new to Markov chains and HMM so I'd like to understand the difference between the two implementations (if there is any). – Any Nov 20 '13 at 11:53
up vote 10 down vote accepted

Please, check the comments above. Here is a quick implementation in R.

x <- c(1,2,1,1,3,4,4,1,2,4,1,4,3,4,4,4,3,1,3,2,3,3,3,4,2,2,3)
p <- matrix(nrow = 4, ncol = 4, 0)
for (t in 1:(length(x) - 1)) p[x[t], x[t + 1]] <- p[x[t], x[t + 1]] + 1
for (i in 1:4) p[i, ] <- p[i, ] / sum(p[i, ])


> p
          [,1]      [,2]      [,3]      [,4]
[1,] 0.1666667 0.3333333 0.3333333 0.1666667
[2,] 0.2000000 0.2000000 0.4000000 0.2000000
[3,] 0.1428571 0.1428571 0.2857143 0.4285714
[4,] 0.2500000 0.1250000 0.2500000 0.3750000

A (probably dumb) implementation in MATLAB (which I have never used, so I don't know if this is going to work. I've just googled "declare vector matrix MATLAB" to get the syntax):

x = [ 1, 2, 1, 1, 3, 4, 4, 1, 2, 4, 1, 4, 3, 4, 4, 4, 3, 1, 3, 2, 3, 3, 3, 4, 2, 2, 3 ]
n = length(x)-1
p = zeros(4,4)
for t = 1:n
  p(x(t), x(t + 1)) = p(x(t), x(t + 1)) + 1
for i = 1:4
  p(i, :) = p(i, :) / sum(p(i, :))

P.S. Does anyone know why R doesn't have a ++ like operator?

share|improve this answer
Looks great! I'm not sure what the 3rd line does in your code though (mainly because I'm familiar with Matlab). Any chance you could write it in matlab or pseudo-code? I'd be much obliged. – HCAI Sep 11 '12 at 17:22
The third line does this: the chain values are $x_1,\dots,x_n$. For $t=1,\dots,n-1$, increment $p_{x_t,x_{t+1}}$. – Zen Sep 11 '12 at 19:32
The fourth line normalizes each line of the matrix $(p_{ij})$. – Zen Sep 11 '12 at 19:34
Bare with my slowness here. I do appreciate the MATLAB code translation although I still can't see what it's attempting to do in your first for loop. The 3rd line from the original code is counting the number of times $x$ goes from state $x_i$ to state $x_j$? If you could say it in words I'd appreciate that a lot. Cheers – HCAI Sep 11 '12 at 20:35
No, $x$ is just one row. Don't concatenate because you will introduce "false" transitions: last state of one line $\to$ first state of the next line. You have to change the code to loop through the lines of your matrix and count the transitions. At the end, normalize each line of the transition matrix. – Zen Sep 15 '12 at 23:57

Here is my implementation in R

x <- c(1,2,1,1,3,4,4,1,2,4,1,4,3,4,4,4,3,1,3,2,3,3,3,4,2,2,3)
share|improve this answer
user32041's request (posted as an edit instead of a comment since he/she lacks reputation): How can I coerce the transitionMatrix of the markovchainFit result to a data.frame? – chl Oct 29 '13 at 14:33
You can convert to $data.frame$ using $as(mcX,"data.frame")$ – Giorgio Spedicato Nov 14 '13 at 23:23

protected by Community Sep 10 '15 at 8:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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