Sequential importance sampling of binary sequences

摘要

Two sequential methods are described for sampling constrained binary sequences from partial solutions. The backward method computes elimination ideals over finite fields and constructs partial solutions that extend. The forward method uses numerical global optimization to determine which partial solutions extend. The methods are applied to restricted orderings, binary dynamics, and random graphs.