Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
up vote 4 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

Your Answer


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.