Cavity method

Definition

Let $G = (V, E)$ be a finite graph, and let $\mathcal{X}$ be a finite set. For each edge $\set{i, j} \in E$, let $\psi_{ij} \colon \mathcal{X} \times \mathcal{X} \to (0, \infty)$. For each vertex $i \in V$, let $\phi_i \colon \mathcal{X} \to (0, \infty)$. Let $\mu$ be the Gibbs measure on $\mathcal{X}^V$ with $\mu(x) \propto \prod_{\set{i,j} \in E} \psi_{ij}(x_i, x_j) \prod_{i \in V} \phi_i(x_i)$. Let $\set{i, j}$ be an edge, and let $G_{ij}$ be the graph $G$ with this edge removed. The cavity distribution $\nu_{i \to j}$ is the marginal law of $x_i$ under the Gibbs measure of $G_{ij}$. Write $\partial i$ for the set of neighbours of $i$. The cavity equations are $$\nu_{i \to j}(x_i) = \frac{1}{z_{i \to j}} \, \phi_i(x_i) \prod_{k \in \partial i \setminus \set{j}} \sum_{x_k \in \mathcal{X}} \psi_{ik}(x_i, x_k) \, \nu_{k \to i}(x_k),$$ where $z_{i \to j}$ makes $\nu_{i \to j}$ a probability measure on $\mathcal{X}$. The cavity method is the following procedure for a large graph. It assumes that the cavity distributions satisfy the cavity equations up to a small error. It solves these equations and computes the marginals and the free energy of $\mu$ from the solution.