1
$\begingroup$

For an $M^{th}$ order Markov chain, $P\left(X_n|X_{n-M}...X_{n-1}\right)$, what's the number of parameters required to know the conditionals? We have discrete variables each with $K$ states.

I think it should be $K^M\left(K-1\right)$, but some books mention $K^{M-1}\left(K-1\right)$.

$\endgroup$
  • $\begingroup$ can you share where you saw $K^{M-1}$? $\endgroup$ – gunes Jan 30 at 9:38
  • 1
    $\begingroup$ For each value of the $M$ previous realisations, of which there are $K^M$ different values, there are $K-1$ probabilities to define the transition. $\endgroup$ – Xi'an Jan 30 at 10:00
  • $\begingroup$ Bishop - Pattern Recognition .. 2006, page 609 $\endgroup$ – Ketan Jan 30 at 11:59
1
$\begingroup$

Other than Markov Chains, if you need to define a probability table for $P(X|Y)$, you'll have $(K_x-1)K_y$ degrees of freedom, where $K_x$ is the total number of states for the variable $X$, and $K_y$ is the total number of states for the variable $Y$, since when $Y$ is fixed, when $K_x-1$ probabilities are computed, the last one can be found from the remaining by just subtracting from $1$. This generalizes to the following: $$P(X_1,...,X_n|Y_1,Y_2,...Y_m)\rightarrow \left[\left(\prod_{i=1}^n{K_{X_i}}\right)-1\right]\prod_{i=1}^m{K_{Y_i}}$$ where for your case, it is $(K-1)K^M$.

There is a typo in Bishop's particular edition, as reported in here.

$\endgroup$

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.