Model Complexity for higher order markov model

Question

I do not understand why is there an increase in parameters when moving from first to second order markov model

For example considering a feature space of (a - z)

For first order markov model, the parameters would be (a - z)

However, for second order (a - zz)

However, i would assume the number of combinations to be the same?

Not sure if this is the right place to ask this question. Basically what i am asking is why is there an increase in parameters if the order level increases

Answer 1

If you have a state space $\mathcal{X}$ of cardinality $N$, then a first-order Markov chain requires $N$ probability mass functions with with $N$ mass points each. Equivalently, this first-order Markov chain can be described by a $N\times N$ transition probability matrix. Hence, there are $N(N-1)$ parameters (the probability mass function sums to one).

If you have a second-order Markov chain, then there are $N^2$ possible state tuples for the past state on which the probability mass functions are conditioned. Hence, there are $N^2$ probability mass functions with $N$ mass points each. Hence, there are $N^2(N-1)$ parameters.