By Alexandre Papadopoulos, François Pachet, Pierre Roy, and Jason Sakellariou.
In Principles and Practice of Constraint Programming (CP 2015), Lecture Notes in Computer Science, vol. 9255, pp. 341–350, Springer, 2015.
Read the paper (PDF)
Publisher record
About the paper
How can a generator respect hard constraints while retaining the probabilities of the sequences allowed by those constraints? This paper gives an exact sampling method for Markov sequences subject to regular and unary constraints.
Abstract summary
The authors combine a Markov chain and finite automata in a chain-structured factor graph. Belief propagation computes the probabilities needed to draw exact conditional samples. The paper illustrates the approach with music and text generation, including metrical and syntactic constraints.
Related work
Sampling Markov Models under Binary Equality Constraints Is Hard · PDF (2016) examines the computational difficulty of exact sampling when distant positions are required to repeat. It also studies the sampling bias that can arise when a random walk is combined with constraint filtering.
See the Markov Constraints project for the earlier work. Exact Regular-Constrained Sampling for Variable-Order Markov Generation (NeurIPS 2026) extends this line of work to variable-order models.