title: Constructing a multi-order Markov chain transition matrix in Matlab
body: <p>A first-order transition matrix of 6 states can be <a href="http://www.eng-tips.com/viewthread.cfm?qid=236532" rel="noreferrer">constructed very elegantly as</a> follows</p>
  
  <pre><code> 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.
  </code></pre>
  
  <p>So here is my problem, how do you construct a second-order transition matrix elegantly?
  The solution I came up with is as follows</p>
  
  <pre><code> [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
  </code></pre>
  
  <p>Is there a one/two-liner, no-loop alternative?</p>
  
  <p>--</p>
  
  <p>Edit:
  I tried comparing my solution against Amro's with "x=round(5*rand([1,1000])+1);"</p>
  
  <pre><code> % ted teng's solution
   Elapsed time is 2.225573 seconds.
   % Amro's solution
   Elapsed time is 0.042369 seconds. 
  </code></pre>
  
  <p>What a difference!
  FYI, <a href="http://staff.science.uva.nl/~shamoun/BAMBAS/IBSC_BAM/EUROBAM_2004/07%20spatial_prediction/scripts_and_data_for_excercises/grp2idx.m" rel="noreferrer">grp2idx</a> is available online.</p>