Abstract
Parameterized families of finite-state Markov random fields (equivalently, undirected graphical models) with hard constraints (in which certain configurations are forbidden) arise in a variety of applications including communication networks and statistical physics. The standard maximum likelihood method for estimating parameters from a single sample is computationally intractable for such models. We describe an alternative algorithm that is amenable to computation tractable and also establish its asymptotic consistency. The proofs entail applications of the method of exchangeable pairs as well as combinatorial arguments.