Counting DOF according to a probabilistic graphical model (MRF, BN)

Question

Given the graphical model of a probability distribution, either a Markov Random field (MRF) or a Bayesian Net (BN), how does one count the maximal number of degrees of freedom for all probability functions compatible with (i.e. with at least the set of indepencies encoded in) the graphical model?

For example, consider the MRF of three random variables $X_1 \leftrightarrow X_2 \leftrightarrow X_3$, where each $X_i \in S_i$ can take one of $D_i = |S_i|$ possible values. Here are two constructive attempts at counting the number of degrees of freedom $\#\mathrm{DOF}$, which disagree with eachother. Each time, we count the maximal number of degrees of freedom in each conditional probability and sum them up:

• $P(X_1,X_2,X_3) = P(X_1) P(X_2|X_1) P(X_3|X_2)$ gives $\# \mathrm{DOF} = D_1 + D_1 D_2 + D_3 D_2$
• $P(X_1,X_2,X_3) = P(X_2) P(X_1|X_2) P(X_3|X_2)$ gives $\# \mathrm{DOF} = D_2 + D_1 D_2 + D_3 D_2$

Why do the two disagree? Is $\#\mathrm{DOF}$ ill-defined, or do the two decompositions not correctly encode the exact same set of independencies from the graphical model?

Answer 1

The calculation of both $\# \mathrm{DOF}$ is wrong, since the number of degrees of freedom is further reduced by normalization. The correct expressions which do account for normalization (subtracting 1 degree of freedom for each distribution) are respectively:

• $\# \mathrm{DOF} = (D_1 - 1) + D_1 ( D_2 - 1 ) + D_2 ( D_3 - 1 )$
• $\# \mathrm{DOF} = (D_2 - 1) + D_2 ( D_1 - 1 ) + D_2 ( D_3 - 1 )$

Contrary to the above, these two are both equivalent to $D_2 ( D_1 + D_3 ) - 1$. Curiously, the difference in $\# \mathrm{DOF}$ between the non-normalized and the normalized version apparently depends on the chosen decomposition.