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?
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.
