Belief propagation on a sparse random graph (Ising model). Messages iterate until convergence. Compare BP marginals with exact Gibbs values for small graphs. Visualize factor graph and message flow.
Belief propagation (Pearl 1988): exact on trees, approximate on graphs with cycles. Message: m_{i→j}(s_j) ∝ Σ_{s_i} exp(J_{ij}s_is_j/T) Π_{k≠j} m_{k→i}(s_i). Cavity method (Mézard-Parisi 1987): BP on random graphs — exact when cycles are long. Exact for SAT, coloring at threshold. Loopy BP fails when loops are short. Works for turbo codes, LDPC (Gallager 1963).