Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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

share|improve this question
add comment

1 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"?

share|improve this answer
    
(+1) Welcome to the site EduEyras. Curiously enough, that question was posted by the same user as this one! :) –  cardinal Dec 30 '12 at 16:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.