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 the book Pattern Recognition and Machine Learning by Bishop, which stated that for the first order Markov chain with K states, the number of parameters is K(K-1).

Why is that? I think it should have been just K-1, because if we have $p(x_n|x_{n-1})$ for n=2 to K that will only be K-1, correct?

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

To completely define a first-order Markov chain you have to know the transition probability $p(x_j|x_i)$ for $1 \leq i, j \leq K$. Your calculation ignores the possibility of transitioning from state 1 to state 3, for example.

Now, there are $K^2$ possible transitions from $x_i$ to $x_j$ with $1 \leq i, j \leq K$. But since $\sum_j p(x_j|x_i) = 1$ for each $i$, we only need to know $K-1$ of the transition probabilities for each $x_i$, and the last can be deduced from those. So there are in fact only $K(K-1)$ parameters.

share|improve this answer
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.