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.
 A: 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.
