# Number of parameters in an Mth Order Markov Chain

For an $$M^{th}$$ order Markov chain, $$P\left(X_n|X_{n-M}...X_{n-1}\right)$$, what's the number of parameters required to know the conditionals? We have discrete variables each with $$K$$ states.

I think it should be $$K^M\left(K-1\right)$$, but some books mention $$K^{M-1}\left(K-1\right)$$.

• can you share where you saw $K^{M-1}$? – gunes Jan 30 at 9:38
• For each value of the $M$ previous realisations, of which there are $K^M$ different values, there are $K-1$ probabilities to define the transition. – Xi'an Jan 30 at 10:00
• Bishop - Pattern Recognition .. 2006, page 609 – Ketan Jan 30 at 11:59

Other than Markov Chains, if you need to define a probability table for $$P(X|Y)$$, you'll have $$(K_x-1)K_y$$ degrees of freedom, where $$K_x$$ is the total number of states for the variable $$X$$, and $$K_y$$ is the total number of states for the variable $$Y$$, since when $$Y$$ is fixed, when $$K_x-1$$ probabilities are computed, the last one can be found from the remaining by just subtracting from $$1$$. This generalizes to the following: $$P(X_1,...,X_n|Y_1,Y_2,...Y_m)\rightarrow \left[\left(\prod_{i=1}^n{K_{X_i}}\right)-1\right]\prod_{i=1}^m{K_{Y_i}}$$ where for your case, it is $$(K-1)K^M$$.