Sampling Markov Models under Binary Equality Constraints Is Hard

By Stéphane Rivaud, François Pachet, and Pierre Roy.

Journées Francophones sur les Réseaux Bayésiens et les Modèles Graphiques Probabilistes (JFRB 2016), Clermont-Ferrand, France, June 2016.

Read the paper (PDF)

About the paper

Repeating a musical pattern can require notes at distant positions to be equal. This paper studies what happens when such equality constraints are imposed on sequences sampled from a Markov model.

Abstract summary

The authors establish a general hardness result for exact sampling under binary equality constraints. They also show experimentally that adding constraint filtering to a random walk can produce valid sequences while changing their probabilities substantially. Specific configurations of equalities remain tractable, and the paper illustrates one with chord-sequence generation.

Related work

See Markov Constraints for the broader research. Exact Sampling for Regular and Markov Constraints with Belief Propagation describes exact sampling for a class of regular constraints. Hidden Biases in Conditioning Autoregressive Models examines related questions about preserving probabilities when conditioning a generator.

Back to Publications