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.
