1
$\begingroup$

A joint probability distribution over D variables where each variable has K states, requires $ K^D $ parameters.

How does the number of parameters needed reduce if the variables follow first order Markov chain?

For instance, considering a distribution over $ D = 100 $ binary variables if $ P(X_1, ...,X_{100}) $ the number of parameters needed is $2^{100} = 1.26e+30$. If first order Markov chain rule is applied the number of parameters is 199. Can someone explain how the value 199 is reached?

$\endgroup$
1
$\begingroup$

Since, for each value of $X_{t-1}$, a conditional distribution for $X_t$ needs to be specified, this means a $K-1$ vector to be chosen within the simplex. Equivalent to picking the $K(K-1)$ free terms in the transition matrix. Which is constant if one assumes a time-homogeneous Markov chain. Plus the marginal in $X_{1}$ also requires a $K-1$ vector in the simplex. Hence $$(K-1)(K+1)$$ free parameters.

Numerical application: when K=2, this means $1\times 3=3$ free parameters.

In case the Markov chain is not time-homogeneous, for each of the $(D-1)$ arrival times, a different $K(K-1)$ transition matrix may be defined, meaning $(D-1)K(K-1)$ free parameters, plus the marginal $K-1$ vector in the simplex. Or a total of$$(K-1)(1+(D-1)K)$$free parameters.

Numerical application: when K=2, D=100, this means $(2-1)\times(1+(100-1)*2)=199$ free parameters.

$\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.