1

I have a set of 5000 strings of length 4, where each character in the string can be either A, B, C, or D.

  • 0-order Markov Chain (no dependency), makes a 4*1 array of columns A, B, C, D.

  • 1-order Markov Chain (pos j depends on previous pos i), makes a 4*4 matrix of rows Ai, Bi, Ci, Di; and columns of Aj, Bj, Cj, Dj.

  • 2-order Markov Chain (pos k depends on pos j and pos i), makes a 4*4*4 matrix of dimensions Ai, Bi, Ci, Di; Aj, Bj, Cj, Dj; and Ak, Bk, Ck, Dk [or this makes a 16*4 matrix of dimensions Aij, Bij, Cij, Dij; Ak, Bk, Ck, Dk].

  • 3-order Markov Chain (pos l depends on pos k, pos j, and pos i), makes a 4*4*4*4 matrix of dimensions Ai, Bi, Ci, Di; Aj, Bj, Cj, Dj; Ak, Bk, Ck, Dk; Al, Bl, Cl, Dl [or this makes a 64*4 matrix of dimensions Aijk, Bijk, Cijk, Dijk; Al, Bl, Cl, Dl].

What are the number of parameters for the 4 orders? I have a few ideas, but want to see what others think. Thank you for any advice!!

  • You already have the expressions `4*1`, `4*4`, `4*4*4`, and `4*4*4*4` in your question, so you're basically all the way there, aren't you? The only thing left is that the 1-order, 2-order, and 3-order also need 4 starting probabilities. – David Robinson Apr 20 '13 at 04:14
  • Maybe I am using the wrong terminology. What are the degree of freedom? For instance, in the 4*1 case, it would be 3 because if you have 3 numbers, the last number is fixed. I have difficulty extending this to multi-dimension arrays in this context. Thanks again. –  Apr 20 '13 at 04:27
  • The `4*1` case would only have `3` degrees of freedom if you consume one (say, by normalizing to make a probability distribution.) In the other scenarios, you will lose one degree of freedom for every distribution you choose to normalize. – phs Apr 20 '13 at 05:02

1 Answers1

0

As was pointed out in the comments, the answer is almost contained in the question. A general formula for the number of independent parameters that fully specify Markov model of k-th order with n possible states is n^k*(n-1) for n>1.

The derivation of this general formula is the same as detailed How does Morkov Chain works and what is memorylessness? for n=3 and k=2.

Specifically, if we take into account k previous steps (including the current one) to predict the next step, the transition matrix should allow for all possible permutations, therefore its dimensions are n^k by n^k. However, since for each state only n outcomes are possible, each row of this matrix only has n non-zero entries. Thus we have n*n^k non-zero entries of this transition matrix, and each column should sum up to 1. So, to obtain the answer for the number of independent parameters we need to subtract n^k from the number of non-zero entries.

This answer does not cover initial conditions, which you would not need if you are looking for a steady-state solution. If you are interested in the transient solution, you need to specify additional (n-1)*k parameters.

Community
  • 1
  • 1
PlutimusPaduster
  • 131
  • 6