By François Pachet, Pierre Roy, and Gabriele Barbieri
François Pachet, Pierre Roy, and Gabriele Barbieri. “Finite-Length Markov Processes with Constraints.” Proceedings of IJCAI 2011, pp. 635–641.
About the paper
A musician may want several possible melodies in a learned style, all with a specified last note. This paper shows how to sample valid alternatives while keeping their relative probabilities under the original model.
Abstract in brief
For constraints within the model’s Markov scope, such as restrictions on individual notes or adjacent pairs in a first-order model, the method compiles the rules into a Markov chain whose transitions depend on the position. Constraint propagation removes impossible choices, and renormalization accounts for the probability of valid continuations. The authors illustrate the method with melody generation.
Related research
See the 2011 Markov Constraints journal paper and the NeurIPS 2026 paper on exact sampling under regular constraints.
Related projects
Markov Constraints