confusion related to higher order markov chain

Question

I was reading this book related to machine learning. It's given that for Mth order markov chain, the number of parameters = $K^{M-1}(K-1)$ where M is the order. I am not sure how this is derived.

For eg, lets say I have three states {Sunny, Cloudy, Rainy}. So at each time stamp I will look at the previous two states. So if I use the above formula, I will have 3*(2-1)*(3-1) = 6 which is less I guess. I should have the following parameters

P(Sunny|Cloudy,Rainy)
P(Sunny|Cloudy,Sunny)
P(Sunny|Cloudy,Cloudy)
P(Sunny|Rainy,Rainy)
P(Sunny|Rainy,Sunny)
P(Sunny|Rainy,Cloudy)
P(Sunny|Sunny,Rainy)
P(Sunny|Sunny,Sunny)
P(Sunny|Sunny,Cloudy)

and so on. It has lots of parameters isn't it higher than 6. I am bit confused. IT should be $K^{M}(K-1)$ I guess

Answer 1

I think you're right about the counting. For a Markov model of order $1$, with $K$ states, you need $K\times K$ parameters, minus $K$ parameters, since you have to consider the normalization of the conditional probabilities for each final state $K$; hence, $K\times K - K = K(K-1)$.

For order $M$, it generalizes to $K^{M+1} - K = K^M (K-1).$

See this post Number of parameters in a Markov chain, where a similar question has been posted. Is the formula you mention maybe a typo? Or perhaps a different nomenclature for "order"?