# Why is computing the partition function expensive?

The joint distribution of a undirected graph can be factorized as a product of potential functions over the maximal cliques of an undirected graph.

$$p(\mathsf{x} \mid \theta) = \frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C)$$

• $$\mathsf{x_C}$$ is a set of variables in the clique $$C$$
• $$Z$$ normalizes the distribution and is called the partition function given by,

$$Z(\theta) \triangleq \sum_\mathsf{x} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C)$$

Why exactly is calculating $$Z(\theta)$$ expensive and how is this situation resolved? I'm a little confused about this.

• That $\sum\limits_\mathsf{x}$ suggests this could be a big calculation if there are many possible values of $\mathsf{x}$ Dec 14, 2022 at 10:03

A probability distribution needs to integrate to one.

$$1 = \int_{x_1 \in \omega_1} \int_{x_2 \in \omega_2} \dots \int_{x_N \in \omega_N} \frac {1} {Z(\theta)} \underbrace{\prod_C \psi_C (\mathsf{x_C} \mid \theta_C) }_{\text{this part is often known}}\,\text{d} x_1 \text{d} x_2 \dots \text{d} x_N$$

And often you know the expression $$\prod_C \psi_C (\mathsf{x_C} \mid \theta_C)$$ based on some theoretical grounds, but the normalisation constant $$Z(\theta)$$ is missing. We can multiply both sides of the equation above with $$Z(\theta)$$ giving

$$\begin{array}{} Z(\theta) &=& Z(\theta)\iiint_{{\bf x} \in \boldsymbol{\omega}} \frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C) \,\text{d} {\bf x} \\ &=&\iiint_{{\bf x} \in \boldsymbol{\omega}} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C) \,\text{d} {\bf x}\end{array}$$

and that integral is not so easy.

Luckily you don't always need to know $$Z(\theta)$$. For instance when we compute a probability (density) ratio for two different values $$\mathsf{x}$$ and $$\mathsf{x}^\prime$$

$$\frac{p(\mathsf{x} \mid \theta)}{p(\mathsf{x}^\prime \mid \theta)} = \frac{\frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C)}{\frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C}^\prime \mid \theta_C)} = \frac{ \prod_C \psi_C (\mathsf{x_C} \mid \theta_C)}{ \prod_C \psi_C (\mathsf{x_C}^\prime \mid \theta_C)}$$

This is used for instance in Markov chain monte carlo sampling methods.