statistics - Degree of Freedom of Markov Chains -

i have set of 5000 strings of length 4, each character in string can either a, b, c, or d.

• 0-order markov chain (no dependency), makes 4*1 array of columns a, b, c, d.

• 1-order markov chain (pos j depends on previous pos i), makes 4*4 matrix of rows ai, bi, ci, di; , columns of aj, bj, cj, dj.

• 2-order markov chain (pos k depends on pos j , pos i), makes 4*4*4 matrix of dimensions ai, bi, ci, di; aj, bj, cj, dj; , ak, bk, ck, dk [or makes 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, , pos i), makes 4*4*4*4 matrix of dimensions ai, bi, ci, di; aj, bj, cj, dj; ak, bk, ck, dk; al, bl, cl, dl [or makes 64*4 matrix of dimensions aijk, bijk, cijk, dijk; al, bl, cl, dl].

what number of parameters 4 orders? have few ideas, want see others think. thank advice!!

as pointed out in comments, answer contained in question. general formula number of independent parameters specify markov model of k-th order n possible states n^k*(n-1) n>1.

the derivation of general formula same detailed how morkov chain works , memorylessness? n=3 , k=2.

specifically, if take account k previous steps (including current one) predict next step, transition matrix should allow possible permutations, therefore dimensions n^k n^k. however, since each state n outcomes possible, each row of matrix has n non-zero entries. have n*n^k non-zero entries of transition matrix, , each column should sum 1. so, obtain answer number of independent parameters need subtract n^k number of non-zero entries.

this answer not cover initial conditions, not need if looking steady-state solution. if interested in transient solution, need specify additional (n-1)*k parameters.