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?