  The aim of this short note is to draw attention to a method by which the
partition function and marginal probabilities for a certain class of random
fields on complete graphs can be computed in polynomial time. This class
includes Ising models with homogeneous pairwise potentials but arbitrary
(inhomogeneous) unary potentials. Similarly, the partition function and
marginal probabilities can be computed in polynomial time for random fields on
complete bipartite graphs, provided they have homogeneous pairwise potentials.
We expect that these tractable classes of large scale random fields can be very
useful for the evaluation of approximation algorithms by providing exact error
estimates.
