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?


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.

  • $\begingroup$ How can we generalise this for an M-order Markov chain? $\endgroup$ – Aditi Narware Nov 22 '18 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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