Constructing a multi-order Markov chain transition matrix in Matlab

A first-order transition matrix of 6 states can be constructed very elegantly as follows

 x = [1 6 1 6 4 4 4 3 1 2 2 3 4 5 4 5 2 6 2 6 2 6]; % the Markov chain
 tm = full(sparse(x(1:end-1),x(2:end),1)) % the transition matrix.

So here is my problem, how do you construct a second-order transition matrix elegantly? The solution I came up with is as follows

 [si sj] = ndgrid(1:6);
 s2 = [si(:) sj(:)]; % combinations for 2 contiguous states
 tm2 = zeros([numel(si),6]); % initialize transition matrix
 for i = 3:numel(x) % construct transition matrix
   tm2(strmatch(num2str(x(i-2:i-1)),num2str(s2)),x(i))=...
   tm2(strmatch(num2str(x(i-2:i-1)),num2str(s2)),x(i))+1;
 end

Is there a one/two-liner, no-loop alternative?

Edit: I tried comparing my solution against Amro's with "x=round(5*rand([1,1000])+1);"

 % ted teng's solution
 Elapsed time is 2.225573 seconds.
 % Amro's solution
 Elapsed time is 0.042369 seconds.

What a difference! FYI, grp2idx is available online.

%# sequence of states x = [1 6 1 6 4 4 4 3 1 2 2 3 4 5 4 5 2 6 2 6 2 6]; N = max(x); %# extract contiguous sequences of 2 items from the above bigrams = cellstr(num2str( [x(1:end-2);x(2:end-1)]' )); %# all possible combinations of two symbols [X,Y] = ndgrid(1:N,1:N); xy = cellstr(num2str([X(:),Y(:)])); %# map bigrams to numbers starting from 1 [g,gn] = grp2idx([xy;bigrams]); s1 = g(N*N+1:end); %# items following the bigrams s2 = x(3:end); %# transition matrix tm = full( sparse(s1,s2,1,N*N,N) ); spy(tm)

Recommended topics

Hot tags